Combinaţie

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 3 decembrie 2021; verificările necesită 2 modificări .

În combinatorică , o combinație de by este un set de elemente selectate dintr-o mulțime de elemente , în care ordinea elementelor nu este luată în considerare. $n$ $k$ $k$ $n$

În consecință, combinațiile care diferă numai în ordinea elementelor (dar nu și în compoziție) sunt considerate la fel - așa difer combinațiile de plasări . Deci, de exemplu, combinațiile de 3 elemente 2 și 3 ( submulțimi (nestrict) pentru care ) dintr-un set de 6 elemente 1 ( ) sunt aceleași (în timp ce aranjamentele ar fi diferite) și constau din aceleași elemente 1. $k=3$ $n=6$

În general, numărul tuturor submulților posibile de elemente ale unei mulțimi de elemente este la intersecția diagonalei --a și a--lea rând al triunghiului lui Pascal . [unu] $k$ $n$ $k$ $n$

Numărul de combinații

Numărul de combinații de prin $n$ $k$ coeficient binomial egal

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

Pentru o funcție generatoare fixă a secvenței de numere combinate , , , … este $n$ ${\tbinom {n}{0))$ ${\tbinom {n}{1))$ ${\tbinom {n}{2))$

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

Funcția de generare bidimensională a numerelor combinate este

\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}}.

Combinații cu repetări

O combinație cu repetări de la până la este un astfel de set -element din -element set, la care fiecare element poate participa de mai multe ori, dar în care ordinea nu este luată în considerare ( multiset ). În special, numărul de funcții monotone nedescrescătoare de la set la set este egal cu numărul de combinații cu repetări de la la . $n$ $k$ $k$ $n$ $\{1,2,\dots ,k\)$ $\{1,2,\puncte,n\}$ $n$ $k$

Numărul de combinații cu repetări ale unui coeficient binomial egal $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)!}}.

Dovada

Să fie tipuri de obiecte, iar obiectele de același tip nu se pot distinge. Să existe un număr nelimitat (sau suficient de mare, cel puțin nu mai puțin de ) de obiecte de fiecare tip. Din acest sortiment vom selecta obiecte; selecția poate conține obiecte de același tip, ordinea selecției nu contează. Se notează prin numărul de obiecte selectate de tipul --lea, , . Apoi . Dar numărul de soluții la această ecuație poate fi calculat cu ușurință cu ajutorul „bilelor și partițiilor”: fiecărei soluții îi corespunde un aranjament de bile și partiții într-un rând, astfel încât să existe exact bile între partițiile -a și -a. Dar astfel de aranjamente sunt exact ceea ce trebuia să fie dovedit. ■ $n$ $k$ $k$ $x_{j}$ $j$ $x_{j}\geq 0$ $j=1,2,\dots ,n$ $x_{1}+x_{2}+\dots +x_{n}=k$ $k$ $n-1$ $(j-1)$ $j$ $x_{j}$ ${\tbinom {n+k-1}{k))$

Pentru fixed , funcția generatoare a numerelor de combinații cu repetări de la by este egală cu $n$ $n$ $k$

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

Funcția generatoare bidimensională a numerelor de combinații cu repetări este

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

Vezi și

Note

↑ Triunghiul uimitor al marelui francez. . Consultat la 20 aprilie 2010. Arhivat din original pe 21 aprilie 2010. (nedefinit)

Link -uri

R. Stanley. Combinatorică enumerativă. — M .: Mir, 1990.