Hvězdy a tyče (kombinatorika) - Stars and bars (combinatorics)

V kontextu kombinatorická matematika, hvězdy a pruhy je grafická pomůcka pro odvození jistých kombinační věty. To bylo propagováno William Feller ve své klasické knize o pravděpodobnost. Může být použit k řešení mnoha jednoduchých počítání problémů, například kolik způsobů existuje n nerozeznatelné koule do k rozlišitelné koše.^[1]

Výroky vět

Metoda hvězd a tyčí je často zavedena konkrétně k prokázání následujících dvou vět elementární kombinatoriky.

Věta jedna

Pro jakýkoli pár kladná celá čísla n a k, počet k-n-tice z pozitivní celá čísla, jejichž součet je n se rovná počtu (k - 1) -prvkové podmnožiny sady s n - 1 prvků.

Obě tato čísla jsou dána znakem binomický koeficient ${displaystyle extstyle {n-1 vyberte k-1}}$. Například když n = 3 a k = 2, n-tice počítané větou jsou (2, 1) a (1, 2) a existují ${displaystyle {binom {3-1} {2-1}} = 2}$ z nich.

Věta dvě

Pro jakoukoli dvojici kladných celých čísel n a k, počet k-n-tice z nezáporné celá čísla, jejichž součet je n se rovná počtu multisety z mohutnost k - 1 převzato ze sady velikostí n + 1.

Obě čísla jsou dána znakem multiset číslo ${displaystyle left (! {binom {n + 1} {k-1}}! ight)}$, nebo ekvivalentně podle binomického koeficientu ${displaystyle {binom {n + k-1} {k-1}} = {binom {n + k-1} {n}}}$ nebo vícenásobné číslo ${displaystyle {ig (}! {binom {k} {n}}! {ig)}}$. Například když n = 3 a k = 2, n-tice počítané větou jsou (3, 0), (2, 1), (1, 2) a (0, 3) a existují ${displaystyle left (! {binom {3 + 1} {2-1}}! ight) = 4}$ z nich.

Důkazy metodou hvězd a pruhů

Věta jedna

Předpokládejme, že existují n objekty (představované hvězdy; v níže uvedeném příkladu n = 7) do které se umístí k koše (v příkladu k = 3), takže všechny koše obsahují alespoň jeden objekt. Koše jsou rozlišitelné (řekněme, že jsou očíslovány od 1 do k) ale n hvězdičky nejsou (konfigurace se tedy liší pouze znakem počet hvězd v každém zásobníku). Konfiguraci tedy představuje a k-tuple kladných celých čísel, jako ve větě věty. Místo toho, abyste hvězdy umístili do košů, začněte tím, že umístíte hvězdy na řádek:

kde hvězdy pro první koš budou vzaty zleva, následované hvězdami pro druhý koš atd. Konfigurace bude tedy určena, jakmile bude známo, která je první hvězda směřující do druhého zásobníku a první hvězda směřující do třetího zásobníku atd. To lze označit umístěním k − 1 oddělující pruhy na místech mezi dvě hvězdy. Vzhledem k tomu, že žádný koš nesmí být prázdný, může mezi danou dvojicí hvězd být maximálně jeden pruh:

Zobrazit n hvězdy jako pevné objekty definující n − 1 mezery mezi hvězdami, v každé z nich může nebo nemusí být jedna lišta (přepážka koše). Konfigurace se získá výběrem k − 1 těchto mezer ve skutečnosti obsahuje lištu; proto existují ${displaystyle {binom {n-1} {k-1}}}$ možné konfigurace (viz kombinace ).

Věta dvě

V tomto případě se reprezentace n-tice jako posloupnosti hvězd a pruhů, přičemž pruhy dělí hvězdy na koše, nemění. Oslabené omezení nezápornosti (namísto pozitivity) znamená, že jeden může umístit více pruhů mezi dvě hvězdy, stejně jako umístění pruhů před první hvězdou nebo za poslední hvězdou. Tak například, když n = 7 a k = 5, n-tice (4, 0, 1, 2, 0) může být reprezentována následujícím diagramem.

Tím se vytvoří a osobní korespondence mezi n-ticemi požadované formy a výběry s nahrazením k − 1 mezery z n + 1 dostupné mezery nebo ekvivalentně (k − 1)-živel multisady čerpané ze sady velikostí n + 1. Podle definice se takové objekty počítají podle vícenásobného čísla ${displaystyle left (! {binom {n + 1} {k-1}}! ight)}$.

Chcete-li vidět, že tyto objekty jsou také počítány binomickým koeficientem ${displaystyle {binom {n + k-1} {n}}}$, pozorujte, že požadovaná uspořádání sestávají z n + k − 1 předměty (n hvězdy a k − 1 pruhy). Výběr pozic pro hvězdy odchází přesně k − 1 zbývající místa pro k − 1 pruhy. To znamená, že výběr pozic pro hvězdy určuje celé uspořádání, takže uspořádání je určeno pomocí ${displaystyle {binom {n + k-1} {n}}}$ výběry. Všimněte si, že ${displaystyle {binom {n + k-1} {n}} = {binom {n + k-1} {k-1}}}$, odrážející skutečnost, že by bylo možné určit uspořádání také výběrem pozic pro k − 1 pruhy.

Příklady

Li n = 5, k = 4 a sada velikosti k je {a, b, c, d}, pak ★ | ★★★ || ★ by představovalo multiset {a, b, b, b, d} nebo 4-tici (1, 3, 0, 1). Reprezentace jakékoli multiset pro tento příklad by použít n = 5 hvězdiček a k - 1 = 3 pruhy.

Mnoho elementárních slovní úlohy v kombinatorice jsou vyřešeny výše uvedenými větami. Pokud si například přejete spočítat počet způsobů, jak rozdělit sedm nerozeznatelných jednodolarových mincí mezi Amber, Ben a Curtis, aby každý z nich získal alespoň jeden dolar, lze pozorovat, že distribuce jsou v zásadě ekvivalentní n-tice tří pozitivních celá čísla, jejichž součet je 7. (Zde je první položkou v n-tici počet mincí udělených Amber atd.) Tedy hvězdy a pruhy platí pro n = 7 a k = 3, a jsou ${displaystyle extstyle {7-1 vyberte 3-1} = 15}$ způsoby distribuce mincí.

Viz také

• Dvanáctkrát
• Oddíl (teorie čísel)

Reference

Další čtení

• Pitman, Jim (1993). Pravděpodobnost. Berlín: Springer-Verlag. ISBN  0-387-97974-3.
• Weisstein, Eric W. „Multichoose“. Mathworld - webový zdroj Wolfram. Citováno 18. listopadu 2012.