Kombinációk száma

Egy verseny elődöntőjében 8-an indulnak. Az első három helyezett jut a döntőbe. Hányféleképpen alakulhat a továbbjutók személye?

Ebben a feladatban a sorrend közömbös. Mind a hárman továbbjutnak. A kérdés tehát az, hogy hogyan lehet 8 emberből  3-t kiválasztani olyan esetekben, amikor a sorrend közömbös?

A feladat hasonló variációk számánál látottakhoz, de ebben a kérdésben csak a kiválasztás a feladat, az elrendezés nem.

Gondolkodhatunk tehát hasonlóan, ahogy a variációknál láttuk.
Az első helyre 8, a második helyre 7, a harmadik helyre pedig 6 lehetőség volt akkor, amikor a sorrend is lényeges volt.

Ha azonban a sorrendtől eltekintünk, akkor a kapott számot el kell osztani a kiválasztott elemek lehetséges elrendezésének számával, ezért a kapott eredmény: ​\( \frac{8·7·6}{3!}=\frac{8·7·6}{6}=56 \)​

A kérdést általánosabban is megfogalmazhatjuk:

Hányféleképpen választhatunk ki „n” különböző tárgyból „k” darabot, ha a kiválasztás sorrendje közömbös?

Ezt a kérdést így is megfogalmazhatjuk:
Az „n” elemű halmaznak hány darab „k” elemű részhalmaza van.

Definíció:

Az „n” elem halmaz „k” elemű részhalmazait az „n” elem k-ad osztályú kombinációinak nevezzük és ​\( {C^k_{n}} \)​-val jelöljük (n≥k).

Tétel:

„n” különböző elem „k”-ad osztályú kombinációjának száma:  ​\( {C^k_{n}}=\binom{n}{k}​=\frac{n!}{k!·\left( n-k \right)! } \)​​,n≥k.

Bizonyítás.

Adott n elem k-ad osztályú kombinációjából úgy állíthatjuk elő a k-ad osztályú variációkat, hogy az egyes kombinációk elemeit sorba rendezzük, permutáljuk.
Ez azt jelenti, hogy: ​\( P_{k}·{C^k_{n}}={V^k_{n}} \), azaz ​\( {C^k_{n}}=\frac{{V^k_{n}}}{P_{k}} \)​

Mivel ​\( {V^k_{n}} \)=n⋅(n-1)⋅(n-2)⋅…⋅(n-k+2)⋅(n-k+1)= ​\( \frac{n!}{\left( n-k \right)! } \)​
és P_k=k⋅(k-1)⋅(k-2)⋅…⋅3⋅2⋅1=k!, ezért: ​​\( {C^k_{n}}=\frac{n!}{k!·\left( n-k \right)! } \)​

Definíció:

A kapott ​\( \frac{n!}{k!·\left( n-k \right)! } \)​  kifejezésre bevezetünk egy új jelölést: \( \binom{n}{k}​ \)​  amit n alatt k-nak olvassunk, és binomiális együtthatónak is nevezzük.

Tehát: ​\( {C^k_{n}}​=\frac{n!}{k!·\left( n-k \right)! }=\binom{n}{k} \)​

Az természetes, hogy „n” elemből „k” darabot ugyanannyiféleképpen lehet kiválasztani, ahányféleképpen „n” elemből „(n-k)” darabot nem kiválasztani. Ez a binomiális együtthatóknak a szimmetria tulajdonsága: ​\( \binom{n}{k}​=\binom{n}{n-k} \)​.

\( \binom{n}{k}​ \) ​definíciójából következően:

a) ​\( \binom{n}{1}=n​ \)​ Mivel n darab tárgyból 1-t kiválasztani n féleképpen lehet.
Másrészt: ​\( \binom{n}{1}=\frac{n!}{1!(n-1)!}=n​ \)​
​\( \binom{n}{1}​=\binom{n}{n-1} \)​ Szimmetria tulajdonság.

b) ​\( \binom{n}{n}=1​ \)​ Mivel n darab tárgyból mindet kiválasztani csak egyféleképpen lehet.
És ​\( \binom{n}{0}=1​ \)​ Hiszen egyet sem kiválasztani szintén csak egyféleképpen lehet.

c) Definíció szerint:  ​\( \binom{0}{0}=1 \)​

Feladat:

Adott a síkban húsz pont, amelyek közül bármely három nem illeszkedik egy egyenesre. Hány háromszöget határoznak meg?

Megoldás:

Az adott 20 pont közül bármelyik hármat kiválasztva a feltétel szerint mindig háromszöget kapunk, hiszen bármely három pont nem esik egy egyenesbe.
Ugyanaz a három pont bármilyen kiválasztási sorrendben ugyanazt a háromszöget határozza meg, ezért az így keletkezett háromszögek száma 20-nak 3-d osztályú kombinációjával egyenlő.

​\( \binom{20}{3}​=\frac{20!}{3!17!}=\frac{20·19·18·17!}{1·2·3·17!}=\frac{20·19·18}{1·2·3·}=1140 \)​

Tehát egy síkon belüli 20 darab pont, amelyik közül bármely 3 nem illeszkedik egy egyenesre, 1140 darab háromszöget határoz meg.

(Összefoglaló feladatgyűjtemény 4039. feladat.)