Combinació

De la Viquipèdia, l'enciclopèdia lliure.
Saltar a la navegació Saltar a la cerca
Nota de desambiguació.svg Desambiguació : si busqueu altres significats, vegeu Combinació (desambiguació) .
Subconjunts de 3 elements d'un conjunt de 5 elements
Subconjunts de 3 elements d'un conjunt de 5 elements

En combinatòria , donats n i k dos nombres enters positius, definim una combinació de n elements presos k alhora (o de n elements de la classe k o de n elements de k a k ) cada subconjunt de k elements extrets d’un conjunt de n elements. Parlem de combinació simple si no pot tenir elements que es repeteixen i de combinació amb repetició en cas contrari. En el cas de combinacions simples, ha de resultar necessàriament kn .

En ambdós casos, els subconjunts s'han de considerar independentment de l'ordre dels elements . Per exemple, si estem en el conjunt presència {p, q, r, s, t} i examinem combinacions de classe 3, els grups prs, PSR, RPS, spr, RSP i SRP representen la mateixa combinació com format per la els mateixos elements mentre que els grups prs i srq representen dues combinacions diferents ja que difereixen en almenys un dels elements.

Combinacions simples

Donat un conjunt A de cardinalitat n , el nombre de subconjunts d' A de cardinalitat kn , és a dir, les combinacions de n elements presos de k a k , s'obté dividint el nombre de tots els possibles subconjunts ordenats de cardinalitat k en A ( disposicions de n elements de la classe k ) per al nombre de permutacions de k elements:

El símbol s’anomena coeficient binomial .

Justificació de la fórmula

Considereu els subconjunts de cardinalitat 4 del conjunt { a, b, c, d, e, f }. Ho tindrem:

Concretament, els 15 grups són:

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

El resultat es pot obtenir amb el raonament següent. Imaginem que posem les 6 lletres a, b, c, d, e, f en una bossa i en traiem a l'atzar la primera que pot ser indiferentment una de les 6: per tant, tenim 6 possibilitats d'extracció. Ara anem a extreure la segona lletra: com que en queden 5 a la bossa, tenim 5 possibilitats d'extracció. Passem a extreure la tercera lletra: com que en queden 4 a la bossa, tenim 4 possibilitats d'extracció. Finalment, repetint de nou el raonament, quan anem a extreure la quarta lletra quedaran 3 a la bossa i, per tant, tindrem 3 possibilitats d’extracció. Si multipliquem totes les possibilitats, tindrem 6 × 5 × 4 × 3 = 360 grups possibles.

El valor obtingut de 360 ​​és, en realitat, el nombre de disposicions simples de 6 objectes de classe 4 en què l'ordre és rellevant . Per exemple, les cartes extretes posteriorment podrien ser a, b, c, d , però també d, c, b, a . Les dues seqüències representen la mateixa combinació ja que es diferencien només per l’ordre, però no pels elements que les constitueixen . En general, les quatre lletres a, b, c, d poden aparèixer de 24 maneres diferents per considerar-se, però, equivalents als efectes de les combinacions:

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

En no estar interessats en l’ordre d’extracció, hem de dividir 360 pel nombre de seqüències que es poden formar amb les mateixes 4 lletres, és a dir, pel nombre de permutacions de 4 elements, donades per 4! = 24. El resultat final és:

Generalitzant, si tenim n elements per agrupar akak, hem de fer la relació següent:

Si multiplicem el numerador i el denominador per (nk)! aconseguim, com volíem demostrar:

Prenem un altre exemple per reiterar la diferència entre combinació i disposició. Si voleu conèixer el nombre de comissions de 3 membres que es poden formar triant entre 6 persones, només és interessant saber de quantes maneres podeu triar els membres del comitè independentment de qui sigui elegit primer o darrer: a en aquest cas, considerem les combinacions i el nombre de comitès possibles ve donat per C 6.3 = 20. Si en canvi volguéssim saber de quantes maneres es poden presentar els 3 primers classificats entre 6 competidors, l’ordre seria rellevant: en aquest altre cas estem considerant les disposicions i, per tant, les possibles classificacions vindrien donades per D 6.3 = 120.

Ordre lexicogràfic

Per tal d'evitar considerar erròniament vàlida una combinació simple que en realitat ja s'ha tingut en compte prèviament amb un altre ordre, es pot recórrer a aquesta altra definició de combinació.

Penseu un conjunt S de n elements, prèviament ordenats, i considerar un nombre enter natural de k tal que 0≤k≤n. Una combinació d'elements de S de longitud k és qualsevol seqüència de k elements de S que augmenta segons l'ordre predeterminat prèviament.

Per exemple, les combinacions de longitud 4 dels elements de { a, b, c, d, e, f }, prèviament ordenades segons l’ordre alfabètic tradicional, són les 15 següents:

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

Es pot veure com les combinacions respecten l' ordre lexicogràfic , d'acord amb l'última definició donada. En complir-nos amb l’ordre, evitem la confusió en considerar dues combinacions diferents que en realitat no ho són, enganyades pel diferent ordre en què es presenten els seus elements.

Criptomorfisme

En referència a l’exemple anterior, podem codificar les combinacions simples que hem obtingut amb seqüències binàries. En el nostre cas particular, aquestes seqüències binàries tenen una longitud de 6 i un pes de 4 i tenen el mateix contingut d'informació que les combinacions indicades a l'exemple. En aquest cas, utilitzant números binaris de 6 dígits, el primer dels quals és 1 si apareix a zero i en cas contrari, el segon és 1 o 0 segons aparegui o no la b , etc. Tenim:

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

Observeu com es presenten aquestes seqüències en ordre antilexicogràfic.

En general, per tant, entre les combinacions simples de n elements de longitud k i les seqüències binàries de longitud n i pes k hi ha un criptomorfisme i equival a operar amb les combinacions o amb les seqüències binàries. Poder operar d’una manera equivalent amb seqüències binàries és molt útil en el camp de l’ordinador.

Combinacions amb repetició

En combinacions amb repetició de longitud k , es pot repetir cada element fins a k vegades. El seu nombre és:

Aquest resultat es pot demostrar de diverses maneres.

Primera manifestació

Donat qualsevol conjunt finit de n elements, es pot situar en una correspondència individual amb el conjunt {1, 2, ..., n }.

Per calcular considerem les seqüències no decreixents, de longitud k , de enters que pertanyen a {1, 2, ..., n }. Considerem una d’aquestes seqüències:

i associeu la seqüència:

La nova seqüència augmenta estrictament, no té repeticions i, per tant, identifica una combinació simple de longitud k dels enters en {1, 2, ..., n + k –1}. L'associació anterior situa en una correspondència un a un les combinacions amb repeticions de longitud k dels elements de {1, 2, ..., n } amb les combinacions simples de longitud k dels enters de {1, 2,. .., n + k -1}. Per tant, el nombre de combinacions amb repeticions de longitud k dels primers n enters positius coincideix amb el nombre de combinacions simples de longitud k dels primers n + k -1 enters positius:

Un exemple us pot ajudar a entendre millor la prova. Donat el conjunt {1,2}, associem a cadascuna de les seves combinacions amb la repetició de la classe 3 una seqüència definida de la manera anterior:

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

A cadascuna de les combinacions amb repetició correspon una i només una de les combinacions simples de la classe 3 del conjunt {1, ..., (2 + 3-1)} = {1, 2, 3, 4} i viceversa . Per tant, el nombre dels primers és igual al nombre dels segons, que és C 2 + 3-1,3 .

Segona prova

El nombre de combinacions de n elements de la classe k és igual al nombre de funcions creixents d'un conjunt A de cardinalitat k a un conjunt B de cardinalitat n .

Qualsevol tal funció és un conjunt de parells ( a i , b j ), on a i és un element de A (amb i = 1,2, ..., k ) i b j és un element de B (amb j = 1,2, ..., n ). En aquest conjunt, hi ha tants parells com elements d’ A i cap element d’ A apareix en més d’un parell. A més, els elements de B poden aparèixer en cap o més parells.

En una primera fase, les seqüències de parells es consideren rellevants; per exemple, identifiqueu dos parells en què hi hagi un element donat b al segon membre, la seqüència ( a 1 , b ), ( a 2 , b ) és diferent de la seqüència ( a 2 , b ), ( a 1 , b ).

A més, amb F k indiquem el conjunt de funcions d' A a B , amb F k-1 el conjunt de funcions d'un subconjunt de cardinalitat k -1 d' A en B , en ambdós casos considerant funcions diferents, provisionalment, diferents només per a la seqüència de parelles que comparteixen el segon membre.

Deixem | F k-1 | el nombre de funcions de l'últim tipus. Hi ha n + k –1 maneres d’estendre cadascuna d’aquestes funcions a tota A. De fet, havent escollit qualsevol element b j de B , si aquest ja està present en altres m j parells (aquells, de fet, el segon membre dels quals és b j ), el nou parell ( a k , b j ) es pot col·locar a seqüencia amb els altres de m j +1 de maneres diferents: abans de la primera o després de qualsevol de les p . Considerant això:

i que el nou parell pot tenir qualsevol element de B al segon membre, tenim:

Per tant, la cardinalitat del conjunt F k es pot calcular per recurrència :

Es pot observar que aquest és el nombre d’ arranjaments simples d’elements ( n + k –1) de la classe k .

Per obtenir el nombre de funcions creixents, n'hi ha prou amb eliminar la distinció introduïda abans entre diferents funcions només per a la seqüència de parells, i després escollir només una de les k ! permutacions dels parells (que són tants com els elements d' A ). S'obté així:

També aquí pot ser útil un exemple. Sigui A = { a 1 , a 2 , a 3 } i B = { b 1 , b 2 }. El conjunt F 1 només conté dues funcions: ( a 1 , b 1 ) i ( a 1 , b 2 ).

Afegim ara els parells que tenen un 2 com a primer element i considerem diferents les funcions amb diferents seqüències dels parells que comparteixen el segon membre. Tenim les funcions a F 2 :

de ( a 1 , b 1 ) de ( 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 )

Per tant, tenim:

Aquestes són les 6 disposicions simples de (2 + 2-1) = 3 elements de la classe 2. Els tres elements són els dos elements d’ A considerats fins ara i un "element de separació" que permet distingir quins s’associen amb b 1 i com ara b 2 . Indicant aquest element amb una barra vertical, les sis funcions són:

  1. d' 1 a 2 | (tots dos associats a b 1 )
  2. de 2 a 1 | (tots dos associats a b 1 )
  3. a 1 | a 2 ( a 1 associat a b 1 , a 2 associat a b 2 )
  4. a 2 | a 1 ( a 2 associat a b 1 , a 1 associat a b 2 )
  5. | a 1 a 2 (tots dos associats a b 2 )
  6. | a 2 a 1 (tots dos associats a b 2 )

Per obtenir el nombre de funcions creixents, és a dir, aquelles tals que si i < j llavors f ( a i ) ≤ f ( a j ), només heu de dividir pel nombre de permutacions dels dos elements d' A , que són 2! = 2. Així obtenim que les funcions creixents són 6/2 = 3 (són les que es troben al primer, tercer i cinquè lloc de la llista).

Per estendre les funcions a totes les A , afegim els parells que tenen un 3 com a primer element:

de ( a 2 , b 1 ), ( a 1 , b 1 ) de ( a 1 , b 1 ), ( a 2 , b 1 ) de ( a 1 , b 1 ), ( a 2 , b 2 ) de ( a 2 , b 1 ), ( a 1 , b 2 ) de ( a 2 , b 2 ), ( a 1 , b 2 ) de ( 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 )

per a un total de 24 parelles. Per tant, tenim:

Aquest és el nombre d'ordenacions simples de (2 + 3-1) = 4 elements de la classe 3, on els quatre elements són un 1 , un 2 , un 3 i l '"element separador" que permet distingir si estan associats a b 1 o a b 2 . El nombre de funcions creixents s’obté dividint pel nombre de permutacions dels tres elements d’ A : 24/3! = 24/6 = 4. Les funcions creixents són, de fet:

  1. d' 1 a 2 a 3 | o ( a 1 , b 1 ), ( a 2 , b 1 ), ( a 3 , b 1 )
  2. d' 1 a 2 | a 3 o ( a 1 , b 1 ), ( a 2 , b 1 ), ( a 3 , b 2 )
  3. a 1 | a 2 a 3 o ( a 1 , b 1 ), ( a 2 , b 2 ), ( a 3 , b 2 )
  4. | a 1 a 2 a 3 o ( a 1 , b 2 ), ( a 2 , b 2 ), ( a 3 , b 2 )

Tercera prova

La prova anterior es pot simplificar de la següent manera. Donat un conjunt A de k elements, volem dividir els seus elements en n grups, cadascun contenint de 0 a k elements d' A. Representem els elements d’ A amb asteriscs, els grups amb n –1 barres verticals; per exemple, si n = 4 i k = 6, podem tenir particions com la següent (entre parèntesis el nombre d'elements de cada grup):

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

o bé:

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

o també:

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

A cada representació tenim una seqüència de símbols n + k –1. Com que no es preocupa per l'ordre, només es tracta de veure de quantes maneres podeu triar n –1 d'aquests símbols per convertir-los en barres. En altres paraules, es tracta de trobar totes les permutacions possibles dels símbols n + k –1, considerant que k són iguals entre si (els asteriscs) i el mateix passa amb les barres verticals n –1. Per tant, per a una propietat del coeficient binomial i tenint en compte la fórmula de permutacions amb repeticions :

Exemples

Les combinacions amb repetició de longitud 2 dels primers 5 enters positius són:

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

Tanmateix, també es pot tenir k > n : per exemple, les combinacions de longitud 5 dels 2 primers enters positius són:

a saber: 11111, 11112, 11122, 11222, 12222, 22222.

Nombre de solucions senceres d'una equació

El càlcul de combinacions amb repetició permet trobar el nombre de solucions enteres no negatives d’una equació en n variables del tipus:

En aquest cas k es pot veure com el nombre d'unitats que es poden dividir en n grups diferents, fins i tot buits, per tant com el nombre d'asteriscs de la tercera prova, el "+" que fa el paper de les barres. Per exemple, l'equació:

admet, entre d'altres, les següents solucions (entre parèntesis les representacions amb seqüències de "1" i "+"):

Trobar el seu nombre equival a trobar el nombre de combinacions amb repetició de n elements de la classe k . En el cas de l’equació donada, el nombre és:

Per a un cas més simple, les solucions enteres no negatives de l'equació:

Jo sóc:

o els quatre parells (0,3), (1,2), (2,1), (3,0).

També es pot calcular el nombre de solucions enteres positives d'una equació (anomenada "nombre de composicions de k en n parts"). Donada una equació com:

només cal convertir-lo en:

configuració y i = x i –1. S'obté així:

En el cas de l’equació x 1 + x 2 = 3, el nombre de solucions enteres positives (el nombre de composicions de 3 en 2 parts) és:

o els dos parells (1,2) i (2,1).

Multisets

El nombre de combinacions amb repetició de n elements de la classe k també s’anomena nombre de multiconjunts de cardinalitat k d’un conjunt de cardinalitat n .

En aquest sentit, la definició de multiconjunt s'utilitza com a funció m U : U → {0,1,2, ...}. Per exemple, tenint en compte el conjunt U = { a , b , c }, un conjunt múltiple de cardinalitat 3 és {( a , 0), ( b , 2), ( c , 1)}, és a dir, en notació exponencial, a 0 b 2 c 1 . La seva cardinalitat és la suma dels segons membres de les parelles o dels exponents de la segona notació. Aquest multiset es pot representar com una de les possibles combinacions amb la repetició de la classe 3 dels 3 elements de U : bbc .

El nombre de combinacions amb la repetició de la classe 3 dels 3 elements de U és (3 + 3-1)! / (2! 3!) = 10; les combinacions són:

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

Aquest és també el nombre de multiconjunts de cardinalitat 3 de U , que són:

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

Es pot observar que el seu nombre també és igual al de les solucions enteres no negatives de l'equació:

Bibliografia

  • Mauro Cerasoli, Franco Eugeni i Marco Protasi, Elements of matemàtiques discretes , Zanichelli, Bolonya, 1988.
  • Sheldon M. Ross, Càlcul de probabilitats , Apogeo, Milà, 2004.

Articles relacionats

Altres projectes

Enllaços externs

Control de l'autoritat Thesaurus BNCF 32733
Matemàtiques Portal de matemàtiques : accediu a les entrades de Wikipedia relacionades amb les matemàtiques