Combinații (combinatorică) - alegerea de subseturi în ciuda ordinului

Uneori face o alegere din setul fără a ține cont de ordinea. Această alegere se numește o combinație. Dacă joci cărți, de exemplu, știi că în cele mai multe situații, ordinea în care dețineți un card, nu contează.

Exemplul 1: găsi toate combinațiile de 3 litere luate dintr-un set de 5 litere.

Când vom găsi mulțimea tuturor combinațiilor de obiecte 5, dacă luăm obiectul 3 la un moment dat, vom găsi toate subgrupurile de 3 celule. În acest caz, ordinea obiectelor nu este luată în considerare. apoi,
Acesta numit de același set ca.

subgrup
Setul A este un subset al lui B și A indică faptul că un subset și / sau la fel ca și în cazul în care fiecare element B A este elementul B.

Elementele nu ordonate subset. Atunci când se analizează combinația, nu este luată în considerare în ordine!

combinație
O combinație care cuprinde obiecte k este un subset format din obiecte k.

Dorim să scrie formula pentru calcularea numărului de combinații de n obiecte, daca sunt luate la obiectele simultan.

Amestec de desemnare
Numărul de combinații de n obiecte, daca sunt luate la facilitățile, în același timp, notat n Ck.

Noi numim combinații n Ckchislo. Dorim să scrie o formulă generală pentru n Ck pentru orice k ≤ n. În primul rând, este adevărat că n Cn = 1, pentru că un set cu n elemente are doar un subset de n elemente, și-a stabilit în sine. În al doilea rând, n C1 = n, deoarece o pluralitate de n elemente are doar subseturi de n 1 în fiecare element. In final, n C0 = 1, deoarece un set cu n elemente este doar un subset cu elemente 0, adică vidă ∅. Pentru a lua în considerare alte combinații, să ne întoarcem la exemplul 1 și numărul de combinații este comparabil cu numărul de permutări.

Rețineți că fiecare combinație de 3 componente este de 6 sau 3. permutări.
3! C3 = 5 • 60 5 = P3 = 5 • 4 • 3
așa
.
În general, numărul de combinații de k elemente selectate dintre n obiecte. n Ck ori permutări ale acestor elemente k. Ar trebui să fie egal cu numărul de permutări de n elemente cu k elemente:
k! Ck .n = n Pk
n Ck = n Pk / k!
n Ck = (1 / k!). n Pk
n = Ck

Combinații de obiecte k din n obiecte
Numărul total de combinații de elemente k din n obiecte este notat cu n Ck. determinat
(1) n = Ck,
sau
(2) n = Ck

Un alt tip de notație pentru n Ck este coeficientul binomial. Motivul pentru această terminologie va fi clar mai jos.

Exemplul 2 Se calculează din formula (1) și (2).

Rețineți, asta nu înseamnă că n / k.

Exemplul 3. Se calculează u.

Soluție Noi folosim formula (1) pentru primul operand și formula (2) pentru al doilea. atunci
,
folosind (1) și
,
formula ispolzuya (2).

Vă rugăm să rețineți că
,
Exemplul 2 și utilizând rezultatul ne dă
.
Aceasta implică faptul că numărul 5 elementul subset al unei multitudini de elemente 7 este același ca și numărul de subseturi 2-celule de la 7 elemente. Atunci când cele 5 elemente selectate din set, care nu includ elementul 2. Pentru a vedea acest lucru, ia în considerare setul:

În general, avem următoarele. Acest rezultat oferă o metodă alternativă de calcul a combinației.

Un subgrup de k și dimensiunea dimensiunea
și n = Ck n Cn-k
Numărul de subseturi la o multitudine de mărimi de la n obiecte este aceeași ca și numărul de subseturi de dimensiune n -. Numărul combinațiilor de k obiectului pluralității n obiecte este aceeași ca și numărul de combinații de n obiecte luate simultan.

Acum vom rezolva problemele cu combinațiile.

Exemplul 4. Michigan loterie. In curs de desfasurare Michigan de două ori pe săptămână loterie WINFALL are un jackpot care este cel puțin egală cu 2 dolari mln. SUA. Per dolar jucător poate lovi orice 6 numere de la 1 la 49. În cazul în care aceste numere coincid cu cele care se încadrează în timpul loterie jucătorul câștigă. (Sursa: Michigan Loterie)
a) Câte combinații posibile de 6 numere din loterie?
b) Să presupunem că 10 minute te duci pentru a cumpăra un bilet de loterie și cruce din 6 numere. Câte bilete de loterie puteți cumpăra timp de 4 zile?
c) Câte persoane pe care le-ar trebui să angajeze timp de 4 zile, pentru a cumpăra bilete la toate combinațiile posibile, și să fie sigur că va câștiga?

decizie
a) Nu există numere de ordine. Ai cruce orice 6 numere de la 1 la 49. Apoi, numărul de combinații posibile este

b) În primul rând, vom calcula numărul de minute în 4 zile -X:
4 zile • (24 ore / 1 zi). (60 min / h 1) = 5760 min.
Apoi, ai putea cumpăra 576 de bilete pentru 4 zile.
c) Tu ar trebui să angajeze un 13983816/576, sau aproximativ 24278 de oameni pentru a cumpăra bilete la toate combinațiile posibile pentru un câștig garantat. (Cu condiția că se pot cumpăra bilete de 24 de ore.)

comitetelor EXEMPLUL 5 Numărul pot fi formate din grupuri de 5 și 7 guvernatori Senat dacă fiecare comitet este format din 3 guvernatori și 4 Senatului?

Trei soluție guvernator poate fi ales căi C3 5 și 4 pot fi ales senator 7 C4 moduri. Dacă vom folosi metoda de numărare fundamentală, constatăm că numărul posibil de comisie, oricum