Kombináció

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. december 3-án felülvizsgált verziótól ; az ellenőrzések 2 szerkesztést igényelnek .

A kombinatorikában a by kombináció az -elem halmazból kiválasztott elemek halmaza , amelyben az elemek sorrendjét nem veszik figyelembe. $n$ $k$ $k$ $n$

Ennek megfelelően azok a kombinációk, amelyek csak az elemek sorrendjében (de nem összetételükben) különböznek egymástól, azonosnak számítanak – a kombinációk így különböznek az elhelyezésektől . Így például egy 6 elemű 1 ( ) halmazból származó 3 elemű 2 és 3 kombinációk ( (nem szigorú) részhalmazok , amelyekhez ) megegyeznek (miközben az elrendezések eltérőek lennének), és ugyanazokból az 1 elemekből állnak. $k=3$ $n=6$

Általánosságban elmondható, hogy egy -elem halmaz összes lehetséges elemű részhalmazának száma a Pascal-háromszög -edik átlójának és -edik sorának metszéspontjában van . [egy] $k$ $n$ $k$ $n$

Kombinációk száma

A kombinációk száma $n$ $k$ egyenlő binomiális együtthatóval

{n \choose k}=C_{n}^{k}={\frac {n!}{k!\left(nk\right)!}}).

A számkombinációk sorozatának fix generáló függvényéhez , , … az $n$ ${\tbinom {n}{0))$ ${\tbinom {n}{1))$ ${\tbinom {n}{2))$

\sum _{k=0}^{n}{\binom {n}{k}}x^{k}=(1+x)^{n}.

A kombinációs számok kétdimenziós generáló függvénye az

\sum _{n=0}^{\infty }\sum _{k=0}^{n}{\binom {n}{k}}x^{k}y^{n}=\sum _{ n=0}^{\infty }(1+x)^{n}y^{n}={\frac {1}{1-y-xy}}.

Kombinációk ismétlésekkel

A tól ig ismétlődésekkel rendelkező kombináció egy olyan -elem halmaz az -elem halmazból, amelyben minden elem többször is részt vehet, de amelyben a sorrendet nem veszik figyelembe ( multiset ). Konkrétan a monoton , nem csökkenő függvények száma halmazról halmazra megegyezik a től ig ismétlődő kombinációk számával . $n$ $k$ $k$ $n$ ${\megjelenítési stílus \{1,2,\pontok ,k\))$ $\{1,2,\pontok,n\}$ $n$ $k$

Azonos binomiális együtthatóval ismétlődő kombinációk száma $n$ $k$

{\overline {C_{n}^{k}}}=C_{(n)}^{k}=\left(\!\!{\binom {n}{k}}\!\! \right)={\binom {n+k-1}{n-1}}={\binom {n+k-1}{k}}=(-1)^{k}{\binom {-n }{k}}={\frac {(n+k-1)!}{k!\cdot (n-1)!}}.

Bizonyíték

Legyenek objektumok típusai, és az azonos típusú objektumok megkülönböztethetetlenek. Legyen minden típusból korlátlan számú (vagy kellően nagy, legalább ) számú objektum. Ebből a választékból fogunk tárgyakat kiválasztani; a kijelölés tartalmazhat azonos típusú objektumokat, a kijelölés sorrendje nem számít. Jelölje a kiválasztott -edik típusú objektumok számával, , . Akkor . De ennek az egyenletnek a megoldásainak száma könnyen kiszámítható a "golyók és válaszfalak" segítségével: minden megoldás megfelel a golyók és válaszfalak egymás utáni elrendezésének úgy, hogy a -edik és -edik partíció között pontosan golyók legyenek. De pontosan az ilyen megállapodásokat kellett bizonyítani. ■ $n$ $k$ $k$ $x_{j}$ $j$ $x_{j}\geq 0$ $j=1,2,\pontok ,n$ $x_{1}+x_{2}+\pontok +x_{n}=k$ $k$ $n-1$ $(j-1)$ $j$ $x_{j}$ ${\tbinom {n+k-1}{k))$

Fix esetén a by -tól származó ismétlődésekkel rendelkező kombinációk számának generáló függvénye egyenlő $n$ $n$ $k$

\sum _{k=0}^{\infty }\left[(-1)^{k}{-n \choose k}\right]x^{k}=(1-x)^{ -n}.

Az ismétlődő kombinációk számának kétdimenziós generáló függvénye az

\sum _{n=0}^{\infty }\sum _{k=0}^{\infty }(-1)^{k}{-n \choose k}x^{k}y^{n }=\sum _{n=0}^{\infty }(1-x)^{-n}y^{n}={\frac {1-x}{1-xy}}.

Lásd még

Jegyzetek

↑ A nagy francia csodálatos háromszöge. . Letöltve: 2010. április 20. Az eredetiből archiválva : 2010. április 21.. (határozatlan)

Linkek

R. Stanley. Enumeratív kombinatorika. - M .: Mir, 1990.