Pravidlo dělení (kombinatorika) - Rule of division (combinatorics)

v kombinatorika, pravidlo rozdělení je princip počítání. Uvádí se, že existují n/d způsoby provedení úkolu, pokud to lze provést pomocí postupu, který lze provést v systému Windows n způsoby a pro každý způsob w, přesně d z n způsoby odpovídají způsobu w. Stručně řečeno, pravidlo dělení je běžným způsobem, jak ignorovat „nedůležité“ rozdíly při počítání věcí.[1]

Aplikováno na sady

Pokud jde o množinu: „Pokud je konečná množina A je spojení n párových disjunktních podmnožin každé s d prvky n = |A|/d."[1]

Jako funkce

Pravidlo dělení formulované z hlediska funkcí: „Pokud F je funkce z A na B kde A a B jsou konečné množiny, a to pro každou hodnotu y ∈ B existují přesně d hodnoty X ∈ A takhle F (X) = y (v takovém případě to říkáme F je d-to-one), pak |B| = |A|/d."[1]

Příklady

Vizuální znázornění pro příklad kulatého stolu

Příklad 1

- Kolik různých způsobů existuje k usazení čtyř lidí kolem kruhového stolu, kde jsou dvě místa považována za stejná, když má každý stejný levý soused a stejný pravý soused?

Abychom toto cvičení vyřešili, musíme nejprve vybrat náhodné místo a přiřadit ho osobě 1, zbytek míst bude označen v číselném pořadí ve směru hodinových ručiček kolem stolu. K dispozici jsou 4 místa k výběru, když vybereme první místo, 3 pro druhé, 2 pro třetí a jen 1 možnost zbývá pro poslední. Tak tam jsou 4! = 24 možných způsobů, jak je usadit. Jelikož však uvažujeme pouze o jiném uspořádání, když nemají stejné sousedy nalevo a napravo, záleží jen na 1 ze 4 možností výběru sedadla.
Protože existují 4 způsoby, jak zvolit sedadlo 1, podle pravidla dělení (n/d) existují 24/4 = 6 různé uspořádání sedadel pro 4 osoby kolem stolu.

Příklad 2

- Máme celkem 6 barevných cihel, 4 z nich jsou červené a 2 jsou bílé, kolik způsobů je můžeme uspořádat?

Pokud by všechny cihly měly stejnou barvu, byl by celkový počet způsobů jejich uspořádání 6! = 720, ale protože nemají stejnou barvu, vypočítali bychom to takto:
4 červené cihly mají 4! = 24 ujednání
2 bílé cihly mají 2! = 2 ujednání
Celkem uspořádání 4 červených a 2 bílých cihel 6!/4!2! = 15.

Viz také

Poznámky

  1. ^ A b C Rosen 2012, str. 385-386

Reference

  • Rosen, Kenneth H (2012). Diskrétní matematika a její aplikace. McGraw-Hill Education. ISBN  978-0077418939.

Další čtení