Combinaţie

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare
Notă despre dezambiguizare.svg Dezambiguizare - Dacă sunteți în căutarea altor semnificații, consultați Combinație (dezambiguizare) .
Subseturi de 3 elemente ale unui set de 5 elemente
Subseturi de 3 elemente ale unui set de 5 elemente

In combinatorică , dat n și k două pozitive numere întregi , definim o combinație de n elemente luate k la un moment dat (sau n elemente ale clasei k sau de n elemente un k pentru k) fiecare subset de elemente k extras dintr - un set de n elemente. Vorbim de combinație simplă dacă nu poate avea elemente care se repetă și de combinație cu repetare altfel. În cazul combinațiilor simple, trebuie să rezulte neapărat kn .

În ambele cazuri, subseturile trebuie luate în considerare, indiferent de ordinea elementelor . De exemplu, dacă suntem în setul de prezență {p, q, r, s, t} și examinăm combinații de clasa 3, grupurile prs , psr, rps, spr, rsp și srp reprezintă aceeași combinație formată din aceleași elemente în timp ce grupurile prs și srq reprezintă două combinații diferite deoarece diferă în cel puțin unul dintre elemente.

Combinații simple

Având în vedere un set A de cardinalitate n , numărul de subseturi de A de cardinalitate kn , adică combinațiile de n elemente luate de la k la k , se obține împărțind numărul tuturor subseturilor posibile de cardinalitate k ordonate în A ( dispoziții din n elemente din clasa k ) pentru numărul de permutări ale k elemente:

Simbolul se numește coeficient binomial .

Justificarea formulei

Luați în considerare subseturile de cardinalitate 4 ale mulțimii { a, b, c, d, e, f }. Vom avea asta:

Mai exact, cele 15 grupuri sunt:

abcd, abce, abcf, abde, abdf, abef, acde,
acdf, acef, adef, bcde, bcdf, bcef, bdef, cdef

Rezultatul poate fi obținut cu următorul raționament. Să ne imaginăm că punem cele 6 litere a, b, c, d, e, f într-o pungă și extragem aleatoriu prima care poate fi indiferent una dintre cele 6: de aceea avem 6 posibilități de extracție. Acum să trecem la extragerea celei de-a doua litere: din moment ce rămân 5 în pungă, avem 5 posibilități de extracție. Să trecem mai departe pentru a extrage a treia literă: din moment ce rămân 4 în pungă, avem 4 posibilități de extracție. În cele din urmă, repetând din nou raționamentul, atunci când mergem să extragem a patra literă, vor rămâne 3 în pungă și, prin urmare, vom avea 3 posibilități de extracție. Dacă înmulțim toate posibilitățile împreună, vom avea 6 × 5 × 4 × 3 = 360 grupuri posibile.

Valoarea obținută de 360 ​​este, în realitate, numărul de dispoziții simple a 6 obiecte din clasa 4 în care ordinea este relevantă . De exemplu, literele extrase ulterior ar putea fi a, b, c, d , dar și d, c, b, a . Cele două secvențe reprezintă aceeași combinație, deoarece diferă doar în ordine, dar nu și în elementele care le constituie . În general, cele patru litere a, b, c, d pot apărea în 24 de moduri diferite pentru a fi considerate, totuși, echivalente în scopul combinațiilor:

abcd abdc acbd acdb adbc adcb
bacd badc bcad bcda bdac bdca
cabd cadb cbad cbda cdab cdba
dabc dacb dbac dbca dcab dcba

Neinteresând ordinea de extracție, trebuie să împărțim 360 la numărul de secvențe care pot fi formate cu aceleași 4 litere, adică la numărul de permutări a 4 elemente, dat de 4! = 24. Rezultatul final este:

Generalizând, dacă avem n elemente pentru a grupa akak, trebuie să facem următoarea relație:

Dacă înmulțim numărătorul și numitorul cu (nk)! obținem, așa cum am vrut să dovedim:

Să luăm un alt exemplu pentru a repeta diferența dintre combinație și aranjament. Dacă doriți să cunoașteți numărul de comitete formate din 3 membri care pot fi formați alegând din 6 persoane, este interesant doar să știți în câte moduri puteți alege membrii comitetului indiferent de cine este ales primul sau ultimul: în în acest caz, luăm în considerare combinațiile și numărul de comitete posibile este dat de C 6.3 = 20. Dacă în schimb am dori să știm în câte moduri se pot prezenta primii 3 clasificați între 6 concurenți, ordinea ar fi relevantă: alt caz luăm în considerare dispozițiile și, prin urmare, posibilele clasificări ar fi date de D 6.3 = 120.

Ordinea lexicografică

Pentru a evita în mod eronat să considerăm validă o combinație simplă care, în realitate, a fost deja luată în considerare anterior cu o altă ordine, se poate recurge la această altă definiție a combinației.

Luați în considerare un set S de n elemente, ordonate anterior și considerați un număr natural k astfel încât 0≤k≤n. O combinație de elemente de S de lungime k este orice secvență de k elemente de S care crește conform ordinii prestabilite anterior.

De exemplu, combinațiile de lungime 4 ale elementelor { a, b, c, d, e, f }, ordonate anterior conform ordinii alfabetice tradiționale, sunt următoarele 15:

abcd abce abcf abde abdf abef acde acdf acef adef
bcde bcdf bcef bdef
cdef

Se poate vedea cum combinațiile respectă ordinea lexicografică , în conformitate cu ultima definiție dată. Prin respectarea ordinii, evităm confuzia considerând ca fiind două combinații diferite care în realitate nu sunt, induse în eroare de ordinea diferită în care sunt prezentate elementele sale.

Criptomorfism

Referindu-ne la exemplul de mai sus, putem codifica combinațiile simple pe care le-am obținut cu secvențe binare. În cazul nostru particular aceste secvențe binare au lungimea 6 și greutatea 4 și au același conținut informațional ca combinațiile indicate în exemplu. În acest caz, folosind numere binare din 6 cifre, dintre care primul este 1 dacă apare la zero și în caz contrar, al doilea este 1 sau 0 în funcție de apariția sau nu a b etc., avem:

111100 111010 111001 110110 110101 110011 101110 101101 101011 100111
011110 011101 011011 010111
001111

Rețineți cum aceste secvențe sunt prezentate în ordine antilexicografică.

În general, prin urmare, între combinațiile simple de n elemente de lungime k și secvențele binare de lungime n și greutate k există un criptomorfism și este echivalent să funcționeze cu combinațiile sau cu secvențele binare. A putea opera într-un mod echivalent cu secvențe binare este foarte util în domeniul computerului.

Combinații cu repetare

În combinații cu repetarea lungimii k , fiecare element poate fi repetat de până la k ori. Numărul lor este:

Acest rezultat poate fi demonstrat în mai multe moduri.

Prima demonstrație

Având în vedere orice set finit de n elemente, acesta poate fi plasat într-o corespondență unu-la-unu cu mulțimea {1, 2, ..., n }.

A calcula considerăm secvențele nedescrescente, de lungime k , ale unor numere întregi aparținând lui {1, 2, ..., n }. Să luăm în considerare una dintre aceste secvențe:

și asociați secvența:

Noua secvență este strict în creștere, nu are repetări și, prin urmare, identifică o combinație simplă de lungime k a numerelor întregi în {1, 2, ..., n + k –1}. Asocierea anterioară plasează într-o corespondență unu-la-unu combinațiile cu repetări de lungime k ale elementelor din {1, 2, ..., n } cu combinațiile simple de lungime k ale numerelor întregi din {1, 2,. .., n + k -1}. Prin urmare, numărul combinațiilor cu repetări de lungime k ale primelor n numere întregi pozitive coincide cu numărul combinațiilor simple de lungime k ale primelor n + k -1 numere întregi pozitive:

Un exemplu vă poate ajuta să înțelegeți mai bine dovada. Având în vedere setul {1,2}, asociem fiecărei combinații cu repetarea clasei 3 o secvență definită ca mai sus:

1,1,1 → 1, 1 + 1, 1 + 2 → 1,2,3
1,1,2 → 1, 1 + 1, 2 + 2 → 1,2,4
1,2,2 → 1, 2 + 1, 2 + 2 → 1,3,4
2,2,2 → 2, 2 + 1, 2 + 2 → 2,3,4

Fiecărei combinații cu repetare îi corespunde una și numai una dintre combinațiile simple din clasa 3 a mulțimii {1, ..., (2 + 3-1)} = {1, 2, 3, 4} și invers . Numărul primelor este, prin urmare, egal cu numărul celui din urmă, care este C 2 + 3-1,3 .

A doua dovadă

Numărul de combinații de n elemente din clasa k este egal cu numărul funcțiilor crescătoare dintr-un set A de cardinalitate k într-un set B de cardinalitate n .

Orice astfel de funcție este un set de perechi ( a i , b j ), unde a i este un element al lui A (cu i = 1,2, ..., k ) și b j este un element al lui B (cu j = 1,2, ..., n ). În acest set, există atâtea perechi câte elemente ale lui A și niciun element al lui A nu apare în mai multe perechi. Mai mult, elementele lui B pot apărea fiecare în nici una sau mai multe perechi.

Într-o primă fază, secvențele de perechi sunt considerate relevante; de exemplu, identificați două perechi în care un element dat b este prezent pe al doilea element, secvența ( a 1 , b ), ( a 2 , b ) este diferită de secvența ( a 2 , b ), ( a 1 , b ).

Mai mult, cu F k indicăm setul de funcții de la A la B , cu F k-1 setul de funcții dintr-un subset de cardinalitate k -1 de A în B , în ambele cazuri considerând funcții distincte, provizoriu, diferite doar pentru succesiunea cuplurilor care împart al doilea membru.

Să | F k-1 | numărul de funcții de ultimul tip. Există n + k –1 modalități de a extinde fiecare dintre aceste funcții la toate A. De fapt, după ce ați ales orice element b j din B , dacă acesta este deja prezent în alte perechi m j (cele, de fapt, al căror al doilea membru este b j ), noua pereche ( a k , b j ) poate fi plasată în secvența cu celelalte în m j +1 moduri diferite: înainte de primul sau după oricare dintre sts . Având în vedere că:

și că noua pereche poate avea orice element de B pe al doilea membru, avem:

Cardinalitatea mulțimii F k poate fi deci calculată prin recurență :

Se poate observa că acesta este numărul de aranjamente simple ale elementelor ( n + k –1) din clasa k .

Pentru a obține numărul de funcții în creștere, este suficient să se elimine distincția introdusă anterior între diferite funcții numai pentru secvența de perechi, apoi să se aleagă doar una dintre k ! permutări ale perechilor (care sunt la fel de multe ca elementele lui A ). Se obține astfel:

Și aici poate fi util un exemplu. Fie A = { a 1 , a 2 , a 3 } și B = { b 1 , b 2 }. Setul F 1 conține doar două funcții: ( a 1 , b 1 ) și ( a 1 , b 2 ).

Acum adăugăm perechile având un 2 ca prim element și considerăm distincte funcțiile cu secvențe diferite ale perechilor care împart al doilea membru. Obținem funcțiile în F 2 :

din ( a 1 , b 1 ) din ( a 1 , b 2 )
( a 2 , b 1 ), ( a 1 , b 1 ) ( a 2 , b 1 ), ( a 1 , b 2 )
( a 1 , b 1 ), ( a 2 , b 1 ) ( a 2 , b 2 ), ( a 1 , b 2 )
( a 1 , b 1 ), ( a 2 , b 2 ) ( a 1 , b 2 ), ( a 2 , b 2 )

Prin urmare, avem:

Acestea sunt cele 6 dispoziții simple ale (2 + 2-1) = 3 elemente din clasa 2. Cele trei elemente sunt cele două elemente ale lui A considerate până acum și un „element de separare” care permite să se distingă care sunt asociate cu b 1 și cum ar fi a b 2 . Indicând acest element cu o bară verticală, cele șase funcții sunt:

  1. la 1 la 2 | (ambele asociate cu b 1 )
  2. la 2 la 1 | (ambele asociate cu b 1 )
  3. la 1 | a 2 ( a 1 asociat cu b 1 , a 2 asociat cu b 2 )
  4. la 2 | a 1 ( a 2 asociat cu b 1 , a 1 asociat cu b 2 )
  5. | a 1 a 2 (ambele asociate cu b 2 )
  6. | a 2 la 1 (ambele asociate cu b 2 )

Pentru a obține numărul de funcții în creștere, adică acelea astfel încât, dacă i < j atunci f ( a i ) ≤ f ( a j ), împărțiți doar la numărul de permutări ale celor două elemente ale lui A , care sunt 2! = 2. Astfel obținem că funcțiile în creștere sunt 6/2 = 3 (sunt cele de pe primul, al treilea și al cincilea loc ale listei).

Pentru a extinde funcțiile la toate A , adăugăm perechile care au un 3 ca prim element:

din ( a 2 , b 1 ), ( a 1 , b 1 ) din ( a 1 , b 1 ), ( a 2 , b 1 ) din ( a 1 , b 1 ), ( a 2 , b 2 ) din ( a 2 , b 1 ), ( a 1 , b 2 ) din ( a 2 , b 2 ), ( a 1 , b 2 ) din ( a 1 , b 2 ), ( a 2 , b 2 )
( a 3 , b 1 ), ( a 2 , b 1 ), ( a 1 , b 1 ) ( a 3 , b 1 ), ( a 1 , b 1 ), ( a 2 , b 1 ) ( a 3 , b 1 ), ( a 1 , b 1 ), ( a 2 , b 2 ) ( a 3 , b 1 ), ( a 2 , b 1 ), ( a 1 , b 2 ) ( a 3 , b 1 ), ( a 2 , b 2 ), ( a 1 , b 2 ) ( a 3 , b 1 ), ( a 1 , b 2 ), ( a 2 , b 2 )
( a 2 , b 1 ), ( a 3 , b 1 ), ( a 1 , b 1 ) ( a 1 , b 1 ), ( a 3 , b 1 ), ( a 2 , b 1 ) ( a 1 , b 1 ), ( a 3 , b 1 ), ( a 2 , b 2 ) ( a 2 , b 1 ), ( a 3 , b 1 ), ( a 1 , b 2 ) ( a 3 , b 2 ), ( a 2 , b 2 ), ( a 1 , b 2 ) ( a 3 , b 2 ), ( a 1 , b 2 ), ( a 2 , b 2 )
( a 2 , b 1 ), ( a 1 , b 1 ), ( a 3 , b 1 ) ( a 1 , b 1 ), ( a 2 , b 1 ), ( a 3 , b 1 ) ( a 1 , b 1 ), ( a 3 , b 2 ), ( a 2 , b 2 ) ( a 2 , b 1 ), ( a 3 , b 2 ), ( a 1 , b 2 ) ( a 2 , b 2 ), ( a 3 , b 2 ), ( a 1 , b 2 ) ( a 1 , b 2 ), ( a 3 , b 2 ), ( a 2 , b 2 )
( a 2 , b 1 ), ( a 1 , b 1 ), ( a 3 , b 2 ) ( a 1 , b 1 ), ( a 2 , b 1 ), ( a 3 , b 2 ) ( a 1 , b 1 ), ( a 2 , b 2 ), ( a 3 , b 2 ) ( a 2 , b 1 ), ( a 1 , b 2 ), ( a 3 , b 2 ) ( a 2 , b 2 ), ( a 1 , b 2 ), ( a 3 , b 2 ) ( a 1 , b 2 ), ( a 2 , b 2 ), ( a 3 , b 2 )

pentru un total de 24 de perechi. Prin urmare, avem:

Acesta este numărul de aranjamente simple ale (2 + 3-1) = 4 elemente din clasa 3, unde cele patru elemente sunt un 1 , un 2 , un 3 și „elementul separator” care permite să se distingă dacă sunt asociate cu b 1 sau a b 2 . Numărul funcțiilor în creștere se obține împărțind la numărul permutărilor celor trei elemente ale lui A : 24/3! = 24/6 = 4. Funcțiile în creștere sunt, de fapt:

  1. la 1 la 2 la 3 | sau ( a 1 , b 1 ), ( a 2 , b 1 ), ( a 3 , b 1 )
  2. la 1 la 2 | a 3 sau ( a 1 , b 1 ), ( a 2 , b 1 ), ( a 3 , b 2 )
  3. la 1 | a 2 a 3 sau ( a 1 , b 1 ), ( a 2 , b 2 ), ( a 3 , b 2 )
  4. | a 1 a 2 a 3 sau ( a 1 , b 2 ), ( a 2 , b 2 ), ( a 3 , b 2 )

A treia dovadă

Dovada anterioară poate fi simplificată după cum urmează. Având în vedere un set A de k elemente, vrem să împărțim elementele sale în n grupuri, fiecare conținând 0 până la k elemente din A. Reprezentăm elementele lui A cu asteriscuri, grupurile cu n –1 bare verticale; de exemplu, dacă n = 4 și k = 6, putem avea partiții precum următoarele (între paranteze numărul de elemente din fiecare grup):

∗ ∗ | ∗ ∗ | ∗ | ∗ (2,2,1,1)
| ∗ ∗ ∗ | ∗ | ∗ ∗ (0,3,1,2)

sau:

∗ ∗ | | | ∗ ∗ ∗ ∗ (2,0,0,4)

sau, de asemenea:

∗ ∗ ∗ ∗ ∗ ∗ | | | (6,0,0,0)

În fiecare reprezentare avem o succesiune de simboluri n + k –1. Deoarece nu îi pasă de comandă, este doar o problemă de a vedea câte modalități puteți alege n –1 dintre aceste simboluri pentru a le transforma în bare. Cu alte cuvinte, este vorba de găsirea tuturor permutărilor posibile ale simbolurilor n + k –1, având în vedere că k sunt egale între ele (asteriscurile) și același lucru este valabil și pentru barele verticale n –1. Prin urmare, pentru o proprietate a coeficientului binomial și luând în considerare formula permutărilor cu repetiții :

Exemple

Combinațiile cu repetarea lungimii 2 din primele 5 numere întregi pozitive sunt:

și exact: 11, 12, 13, 14, 15, 22, 23, 24, 25, 33, 34, 35, 44, 45, 55.

Cu toate acestea, se poate avea și k > n : de exemplu, combinațiile de lungime 5 ale primelor 2 numere întregi pozitive sunt:

și anume: 11111, 11112, 11122, 11222, 12222, 22222.

Numărul de soluții întregi ale unei ecuații

Calculul combinațiilor cu repetiție permite găsirea numărului de soluții întregi non-negative ale unei ecuații în n variabile de tipul:

În acest caz, k poate fi văzut ca numărul de unități care pot fi împărțite în n grupuri diferite, chiar și goale, deci ca numărul de asteriscuri din a treia dovadă, "+" jucând rolul barelor. De exemplu, ecuația:

admite, printre altele, următoarele soluții (între paranteze reprezentările cu secvențe de "1" și "+"):

Găsirea numărului lor este echivalentă cu găsirea numărului de combinații cu repetarea a n elemente din clasa k . În cazul ecuației date, numărul este:

Pentru un caz mai simplu, soluțiile întregi non-negative ale ecuației:

Sunt:

sau cele patru perechi (0,3), (1,2), (2,1), (3,0).

Se poate calcula, de asemenea, numărul de soluții întregi pozitive ale unei ecuații (numit „numărul compozițiilor lui k în n părți”). Având în vedere o ecuație ca:

doar transformă-l în:

setarea y i = x i –1. Se obține astfel:

În cazul ecuației x 1 + x 2 = 3, numărul soluțiilor întregi pozitive (numărul compozițiilor de 3 în 2 părți) este:

sau cele două perechi (1,2) și (2,1).

Multiseturi

Numărul de combinații cu repetarea a n elemente din clasa k se mai numește și numărul de multiseturi de cardinalitate k a unui set de cardinalitate n .

În acest sens, definiția multisetului este utilizată ca funcție m U : U → {0,1,2, ...}. De exemplu, având în vedere mulțimea U = { a , b , c }, un multiset de cardinalitate 3 este {( a , 0), ( b , 2), ( c , 1)}, adică în notație exponențială, a 0 b 2 c 1 . Cardinalitatea sa este suma celor doi membri ai perechilor sau a exponenților din a doua notație. Acest multiset poate fi reprezentat ca una dintre combinațiile posibile cu repetarea clasei 3 a celor 3 elemente ale lui U : bbc .

Numărul de combinații cu repetarea clasei 3 a celor 3 elemente ale lui U este (3 + 3–1)! / (2! 3!) = 10; combinațiile sunt:

aaa, aab, aac, abb, abc, acc, bbb, bbc, bcc, ccc

Acesta este, de asemenea, numărul de multiseturi de cardinalitate 3 ale U , care sunt:

a 3 b 0 c 0 , a 2 b 1 c 0 , a 2 b 0 c 1 , a 1 b 2 c 0 , a 1 b 1 c 1 , a 1 b 0 c 2 , a 0 b 3 c 0 , a 0 b 2 c 1 , a 0 b 1 c 2 , a 0 b 0 c 3

Se poate observa că numărul lor este, de asemenea, egal cu cel al soluțiilor întregi non-negative ale ecuației:

Bibliografie

  • Mauro Cerasoli, Franco Eugeni și Marco Protasi, Elemente de matematică discretă , Zanichelli, Bologna, 1988.
  • Sheldon M. Ross, Calculul probabilităților , Apogeo, Milano, 2004.

Elemente conexe

Alte proiecte

linkuri externe

Controlul autorității Tezaur BNCF 32733
Matematica Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică