Combinació (matemàtiques)

En matemàtiques i, en concret, en combinatòria, una combinació és una selecció d'elements d'un conjunt que té membres distints, de modo que l'orde de selecció no importa (a diferència de les permutació). Per eixemple, donades tres frutes, digam una poma, una taronja i una pera, hi ha tres combinacions de dos frutes que es poden extraure d'este conjunt: podem elegir una poma i una pera; una poma i una taronja; o una pera i una taronja. Més formalment, una k-combinació d'un conjunt S és un subconjunt de k elements distints de S. Dos combinacions són idèntiques si i solament si cada combinació té els mateixos membres. (L'orde d'elecció dels elements no importa; si l'orde importara, elegir la poma i després la pera seria distint d'elegir la pera i després la poma).

Si el conjunt a on elegir té n elements, el número de k combinacions (és dir, el número de subconjunts de k elements), denotat per $C (n, k)$ o $C_{k}^{n}$ , és igual al coeficient binomial

$(\binom{n}{k}) = \frac{n (n - 1) \dots (n - k + 1)}{k (k - 1) \dots 1},$

que es pot escriure usant factorials com $\frac{n!}{k! (n - k)!}$ quan $k \leq n$ , i val zero quan $k > n$ (no hi ha cap subconjunt de més elements que el total).

Esta fòrmula es demostra de la manera següent: Primer elegim k elements distints del conjunt de n per orde. Per a elegir el primer tenim n opcions; per al segon, com ya no podem elegir el que ya hem elegit, n-1 opcions; per al tercer, n-2, i aixina fins al k-ésimo, per al que tenim n-(k-1)=n-k+1 opcions. En total tenim n(n-1)···(n-k+1) opcions per a elegir els k elements per orde.

Aixina tindríem el número d'eleccions ordenades de k elements. En efecte, contant d'esta forma, estem contant vàries voltes la mateixa selecció d'elements simplement perque els hem pres en órdens distints. Per eixemple, estem contant com a distintes les eleccions que prenen els mateixos elements pero que el primer element que elegix una l'atra ho elegix en últim lloc. En general, estem contant cada combinació (cada elecció d'un mateix subconjunt d'elements) tantes voltes com a maneres tenim de reordenar els seus elements (formes d'elegir-los en un cert orde). Com el número de formes de reordenar un conjunt de k elements és k!=k(k-1)···1, el número d'eleccions de k elements sense importar la seua orde (i.i. de k-combinacions) és

$(\binom{n}{k}) = \frac{n (n - 1) \dots (n - k + 1)}{k (k - 1) \dots 1}$

Una combinació és una combinació de n coser preses k al mateix temps sense repetició. Per a referir-se a combinacions en les que es permet la repetició, a sovint s'utilisen els térmens^[1] k-combinació en repetició, k-multiconjunto, ^[2] o k-selecció.^[3] Si en l'eixemple anterior de les frutes fora possible tindre més d'un eixemplar de fruta de cada tipo hi hauria tres seleccions 2 més: una en dos pomes, una en dos taronges i una en dos peres.

Encara que el conjunt de tres frutes era lo suficientment chicotet per a escriure una llista completa de combinacions, açò es torna poc pràctic a mida que aumenta el tamany del conjunt. Per eixemple, una mane de pòquer es pot descriure com una combinació de 5 (k = 5) de cartes d'una baralla de 52 cartes (n = 52). Les 5 cartes de la mà són totes distintes, i l'orde de les cartes en la mà no importa (et repartixquen les cartes en l'orde en que te les repartixquen, la mà que tens és la mateixa). Usant la fòrmula de dalt, hi ha 2.598.960 combinacions d'este tipo i la provabilitat de traure una mà concreta a l'encert és per tant de 1 / 2.598.960.

Número de k combinacions

Archiu:Combinations without repetition; 5 choose 3.svg

Subconjunts de 3 elements d'un conjunt de 5 elements

El número de k-combinacions d'un conjunt S de n elements es denota a sovint en texts de combinatòria elemental per $C (n, k)$ , o per mig de variacions com $C_{k}^{n}$ , $_{n} C_{k}$ , $^{n} C_{k}$ , $C_{n, k}$ o inclús $C_{n}^{k}$ ^[4] (l'última forma és estàndar en els texts en francés, rumà, rus i chinenc^[5]^[6]). No obstant, el mateix número apareix en molts atres contexts matemàtics, a on es denota per $(\binom{n}{k})$ (a sovint llegit com " n sobre k "); en particular, apareix com a coeficient en la fòrmula binomial, i d'ahí el seu nom, coeficient binomial.

Es pot definir $(\binom{n}{k})$ per a tots els número natural k al mateix temps per la relació (donada per la fòrmula binomial)

$(1 + X)^{n} = \sum_{k \geq 0} (\binom{n}{k}) X^{k},$

de la qual cosa es desprén clarament que

$(\binom{n}{0}) = (\binom{n}{n}) = 1,$

i ademés

$(\binom{n}{k}) = 0$

per a k > n.

Per a vore que estos coeficients conten k-combinacions de S, primer es pot considerar una colecció de n variables distintes X_s etiquetades pels elements s de S, i expandir el producte sobre tots els elements de S:

$\prod_{s \in S} (1 + X_{s});$

Expandint el producte en una suma, esta té 2ⁿ sumants distints corresponents a tots els subconjunts de S: cada sumant és el producte d'unes $X_{s_{1}} X_{s_{2}} \dots X_{s_{k}}$ i a cada u d'estos li podem fer correspondre el subconjunt ${s_{1}, s_{2}, \dots, s_{k}} \subseteq S$ . Ara, si denotem totes les variables X_s com una variable no etiquetada X, de modo que el producte es convertix en (1 + X)ⁿ, l'expressió $X_{s_{1}} X_{s_{2}} \dots X_{s_{k}}$ de cada k-combinació de S es convertix indistintament dels seus elements i la seua orde en X^k, de modo que el coeficient d'eixa potència en el resultat és igual al número de dites k-combinacions.

Els coeficients binomiales es poden calcular explícitament de vàries maneres. Per a obtindre'ls tots per a les expansions de (1 + X), (1 + X)², ..., (1 + X)ⁿ, es pot utilisar (ademés dels casos bàsics ya daus) la relació de recursión

$(\binom{n}{k}) = (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k}),$

per a 0 < k < n, la qual cosa se seguix algebraicamente de que (1 + X)ⁿ = (1 + X)^{n − 1}(1 + X); açò conduïx a la construcció del triàngul de Pascal. Una manera combinatòria de justificar esta relació sorgix d'usar que $(\binom{n}{k})$ és el número de subconjunts de k elements d'un conjunt S de n. Aixina, fixem un element $s_{0} \in S$ . Els subconjunts de k elements de S es poden separar en aquells que continguen a s₀ i aquells que no. Podem calcular la cantitat que hi ha dels primers: en haver elegit ya l'element s₀, només nos falten per elegir k-1 elements dels n-1 restants. D'estos hi ha $(\binom{n - 1}{k - 1})$ . Per un atre costat, també podem contar el número de k-combinacions que no contenen a s₀: cal elegir un subconjunt de k elements dels n-1 restants, açò és, hi ha $(\binom{n - 1}{k})$ opcions. D'ací se seguix que $(\binom{n}{k}) = (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k})$ .

Per a determinar un coeficient binomial individual, és més pràctic utilisar la fòrmula

$(\binom{n}{k}) = \frac{n (n - 1) (n - 2) \dots (n - k + 1)}{k!},$

la demostració del qual ya s'ha donat en l'introducció.

Quan k és major que n/2, la fòrmula anterior conté factors comuns en el numerador i el denominador, i en cancelar-los s'obté la relació

$(\binom{n}{k}) = (\binom{n}{n - k}),$

per a 0 ≤ k ≤ n. Açò expressa una simetria que és evident a partir de la fòrmula binomial, i que també pot entendre's en térmens de k-combinacions prenent el complement de dita combinació, que és una (n − k)-combinació (cada k-combinació determina una (n - k)-combinació i viceversa: aquells elements que no han segut triats; per tant té que haver la mateixa cantitat de cada una).

Finalment, hi ha una fòrmula que mostra esta simetria directament i té el mèrit de ser fàcil de recordar:

$(\binom{n}{k}) = \frac{n!}{k! (n - k)!},$

a on n! denota el factorial de n. S'obté de la fòrmula anterior multiplicant denominador i numerador per (n − k)! , per lo que de fet computacionalment és menys eficient que eixa fòrmula.

De les fòrmules anteriors es deduïxen les relacions entre els números adjacents en el triàngul de Pascal en les tres direccions:

$(\binom{n}{k}) = {\begin{matrix} (\binom{n}{k - 1}) \frac{n - k + 1}{k} & si k > 0 \\ (\binom{n - 1}{k}) \frac{n}{n - k} & si k < n \\ (\binom{n - 1}{k - 1}) \frac{n}{k} & si n, k > 0 \end{matrix} .$

Junt en els casos bàsics $(\binom{n}{0}) = 1 = (\binom{n}{n})$ , estos permeten el càlcul successiu de tots els números de combinacions d'un conjunt d'un mateix número d'elements (una fila en el triàngul de Pascal), de k-combinacions de conjunts de tamanys creixents i de combinacions en un complement de tamany fix n − k.

Eixemple de conteo de combinacions

Com a eixemple concret, es pot calcular el número de mans de cinc cartes possibles a partir d'una baralla estàndart d'cincuenta y dos cartes com: ^[7]

$(\binom{52}{5}) = \frac{52 \times 51 \times 50 \times 49 \times 48}{5 \times 4 \times 3 \times 2 \times 1} = \frac{311,875,200}{120} = 2,598,960.$

Alternativament, es pot utilisar la fòrmula en térmens de factorials i cancelar alguns factors del numerador en alguns del denominador, despuix de la qual cosa només es requerix la multiplicació dels factors restants: $\begin{matrix} (\binom{52}{5}) & = \frac{52!}{5! 47!} \\ = \frac{52 \times 51 \times 50 \times 49 \times 48 \times 47!}{5 \times 4 \times 3 \times 2 \times 1 \times 47!} \\ = \frac{52 \times 51 \times 50 \times 49 \times 48}{5 \times 4 \times 3 \times 2} \\ = \frac{(26 \times 2) \times (17 \times 3) \times (10 \times 5) \times 49 \times (12 \times 4)}{5 \times 4 \times 3 \times 2} \\ = 26 \times 17 \times 10 \times 49 \times 12 \\ = 2,598,960. \end{matrix}$

Un atre càlcul alternatiu, equivalent al primer, es basa en escriure

$(\binom{n}{k}) = \frac{(n - 0)}{1} \times \frac{(n - 1)}{2} \times \frac{(n - 2)}{3} \times \dots \times \frac{(n - (k - 1))}{k},$

la qual cosa dona

$(\binom{52}{5}) = \frac{52}{1} \times \frac{51}{2} \times \frac{50}{3} \times \frac{49}{4} \times \frac{48}{5} = 2,598,960.$

Quan s'evalua en el següent orde, $52 \div 1 \times 51 \div 2 \times 50 \div 3 \times 49 \div 4 \times 48 \div 5$ , açò es pot calcular utilisant només aritmètica de número entero. La raó és que quan es calcula cada divisió, el resultat intermig que es produïx és en sí mateixa un coeficient binomial, per lo que mai es produïxen restants (els coeficients binomiales són per definició el número de combinacions d'un conjunt, és dir, número entero).

Utilisant la fòrmula simètrica en térmens de factorials sense realisar simplificació s'obté un càlcul prou extens:

$\begin{matrix} (\binom{52}{5}) & = \frac{n!}{k! (n - k)!} = \frac{52!}{5! (52 - 5)!} = \frac{52!}{5! 47!} \\ = \frac{80, 658, 175, 170, 943, 878, 571, 660, 636, 856, 403, 766, 975, 289, 505, 440, 883, 277, 824, 000, 000, 000, 000}{120 \times 258, 623, 241, 511, 168, 180, 642, 964, 355, 153, 611, 979, 969, 197, 632, 389, 120, 000, 000, 000} \\ = 2,598,960. \end{matrix}$

Enumeració de k-combinacions

Es poden enumerar totes les k-combinacions d'un conjunt donat S de n elements en un orde fix, lo que establix una biyección d'un interval de $(\binom{n}{k})$ número entero en el conjunt d'eixes k-combinacions. Suponent que S és un conjunt ordenat, per eixemple S = {1, 2, ..., n}, hi ha dos possibilitats naturals per a ordenar les seues k combinacions: comparant primer els seus elements més menuts (com en les ilustracions anteriors) o comparant primer els seus elements més grans. L'última opció té la ventaja de que agregar un nou element més gran a S no canviarà la part inicial de l'enumeració, sino que només agregarà les noves k-combinacions del conjunt més gran despuix de les anteriors. Repetint este procés, l'enumeració pot estendre's indefinidament en k-combinacions de conjunts cada volta més grans. Si ademés es prenen els intervals dels número entero començant en el 0, llavors la i-ésima k-combinació de l'enumeració es pot calcular fàcilment a partir de i, i la biyección aixina obtinguda es coneix com sistema numèric combinatori. També es coneix com "ranc"/"rànquing" i "unranking" en matemàtiques computacionals. ^[8] ^[9]

Hi ha moltes formes d'enumerar k-combinacions. Una forma és rastrejar els números d'índex k dels elements seleccionats, començant en {0 .. k −1} (basat en zero) o {1 .. k } (basat en un) com la primera k-combinació permesa. Després, passar repetidament a la següent k-combinació permesa incrementant el número d'índex més chicotet per al qual açò no crearia dos números d'índex iguals i, al mateix temps, restablint tots els números d'índex més chicotet als seus valors inicials.

Combinacions en repetició

Una k-combinació en repetició, o k-multicombinación, o multisubconjunto de tamany k d'un conjunt S de tamany n queda definida per un conjunt de k elements no necessàriament distints de S, a on no es té en conte l'orde: dos seqüències definixen el mateix multiconjunto si una pot obtindre's de l'atra permutant els térmens. En atres paraules, és una elecció de k elements d'un conjunt de n elements que permet duplicats (és dir, en tongada) pero ignora ordenaments diferents (per eixemple, {2,1,2} = {1,2,2}). Si s'associa un índex a cada element de S i es pensa en els elements de S com a tipos d'objectes, llavors podem denotar per $x_{i}$ el número d'elements del tipo i en un multisubconjunto.

Tornant a l'eixemple de les frutes de l'introducció, teníem tres frutes: una poma, una taronja i una pera. Les 2-combinacions eren eleccions de subconjunts de dos elements (de dos frutes distintes). Per a entendre les k-multicombinaciones, o multiconjuntos de k elements, suponga's que tenim una cantitat arbitrariamente gran d'eixes frutes (les pomes, taronges i peres són els tipos de fruta anteriors). Les 2-multicombinaciones es correspondrien en elegir dos frutes qualssevol, permetent duplicats: podem prendre dos pomes, dos taronges o dos peres ademés de les 2-combinacions. Les k-multicombinaciones es correspondrien en prendre k frutes qualssevol, permetent repetir tipos.

Una atra manera de vore-ho és que el número de multisubconjuntos de tamany k d'un conjunt de tamany n és el número de solucions sanceres no negatives (lo que permet zero) de l'equació diofántica: ^[10]

$x_{1} + x_{2} + \dots + x_{n} = k .$

En efecte, el conjunt ${1, \dots, n}$ és el conjunt de tipos d'objectes que hi ha per a elegir. De cada tipo i tenim que elegir una cantitat x_i de manera que en total la cantitat d'objectes elegits siga k, és dir, imponem que $x_{1} + x_{2} + \dots + x_{n} = k .$

Si S té n elements, el número de k- multisubconjuntos es denota per

$((\binom{n}{k})),$

una notació anàloga al coeficient binomial, que conta k-subconjunts. Esta expressió també es pot donar en térmens de coeficients binomiales:

$((\binom{n}{k})) = (\binom{n + k - 1}{k}) .$

Esta relació es pot demostrar fàcilment utilisant una representació coneguda com barres i estreles:^[11]

Demostració:

Artícul principal → Barres i estreles (combinatòria).

Podem representar una solució de l'equació diofántica anterior com seguix. Dibuixem $x_{1}$ estreles, després un separador (una barra), després atres $x_{2}$ estreles, després una atra barra, i aixina successivament. El número total d'estreles en esta representació és k i el número total de barres, n - 1 (puix una separació en n partixes necessita n - 1 separadores). Aixina que, una seqüència de k + n - 1 símbols (estreles i barres) correspon a una solució de l'equació si conté k estreles. Qualsevol solució es pot representar elegint k de les k + n - 1 posicions per a ser ocupades per estreles, i reblint les atres en barres. Per eixemple, la solució $x_{1} = 3, x_{2} = 2, x_{3} = 0, x_{4} = 5$ de l'equació $x_{1} + x_{2} + x_{3} + x_{4} = 10$ (n = 4 i k = 10) es pot representar per

☆☆☆|☆☆||☆☆☆☆☆.

Aixina que, hi ha una biyección entre k-multiconjuntos d'un conjunt de n elements i colocació de k estreles en una llista de k + n - 1 símbols, per lo que hi ha la mateixa cantitat d'una cosa que dona l'atra. Pero la segona cosa són el número de subconjunts de k elements d'un de k + n - 1 elements, és dir, ve dau, per definició, per $(\binom{n + k - 1}{k}) . ◻$

Archiu:Combinations with repetition; 5 multichoose 3.svg

Biyección entre 3-subconjunts d'un 7-conjunt (esquerra) i 3-multiconjuntos en elements d'un 5-conjunt (dreta).
Açò ilustra que

(\binom{7}{3}) = ((\binom{5}{3}))

.

Igual que en els coeficients binomiales, existixen vàries relacions entre estes expressions d'elecció múltiple. Per eixemple, per a $n \geq 1, k \geq 0$ , se satisfà que

$((\binom{n}{k})) = ((\binom{k + 1}{n - 1})) .$ Esta identitat es desprén de l'intercanvi de les estreles i les barres en la representació anterior.^[12]

Eixemple de conteo de multisubconjuntos

Per eixemple, si hi ha quatre tipos de dònuts (n = 4) en un menú per a elegir i es volen tres dònuts (k = 3), el número de formes d'elegir les dònuts (en repetició perque podem demanar el mateix més d'una volta) es pot calcular com

$((\binom{4}{3})) = (\binom{4 + 3 - 1}{3}) = (\binom{6}{3}) = \frac{6 \times 5 \times 4}{3 \times 2 \times 1} = 20.$

Este resultat es pot verificar enumerant tots els 3-multisubconjuntos del conjunt S = {1,2,3,4}. Açò es mostra en la següent taula.^[13] La segona columna enumera els dònuts que realment va elegir, la tercera columna mostra les solució sancera no negativa $[x_{1}, x_{2}, x_{3}, x_{4}]$ de l'equació $x_{1} + x_{2} + x_{3} + x_{4} = 3$ que es correspon en l'elecció i l'última columna dona la representació de les solucions per mig d'estreles i barres. ^[14]

N.º	3-multiset	Eq. solution	Stars and bars
1	{1,1,1}	[3,0,0,0]	$★ ★ ★ \| \| \|$
2	{1,1,2}	[2,1,0,0]	$★ ★ \| ★ \| \|$
3	{1,1,3}	[2,0,1,0]	$★ ★ \| \| ★ \|$
4	{1,1,4}	[2,0,0,1]	$★ ★ \| \| \| ★$
5	{1,2,2}	[1,2,0,0]	$★ \| ★ ★ \| \|$
6	{1,2,3}	[1,1,1,0]	$★ \| ★ \| ★ \|$
7	{1,2,4}	[1,1,0,1]	$★ \| ★ \| \| ★$
8	{1,3,3}	[1,0,2,0]	$★ \| \| ★ ★ \|$
9	{1,3,4}	[1,0,1,1]	$★ \| \| ★ \| ★$
10	{1,4,4}	[1,0,0,2]	$★ \| \| \| ★ ★$
11	{2,2,2}	[0,3,0,0]	$\| ★ ★ ★ \| \|$
12	{2,2,3}	[0,2,1,0]	$\| ★ ★ \| ★ \|$
13	{2,2,4}	[0,2,0,1]	$\| ★ ★ \| \| ★$
14	{2,3,3}	[0,1,2,0]	$\| ★ \| ★ ★ \|$
15	{2,3,4}	[0,1,1,1]	$\| ★ \| ★ \| ★$
16	{2,4,4}	[0,1,0,2]	$\| ★ \| \| ★ ★$
17	{3,3,3}	[0,0,3,0]	$\| \| ★ ★ ★ \|$
18	{3,3,4}	[0,0,2,1]	$\| \| ★ ★ \| ★$
19	{3,4,4}	[0,0,1,2]	$\| \| ★ \| ★ ★$
20	{4,4,4}	[0,0,0,3]	$\| \| \| ★ ★ ★$

Vore també

Notes i referències

↑ When the term combination is used to refer to either situation (as in (Brualdi, 2010)) care must be taken to clarify whether sets or multisets llaure being discussed.
↑ Mazur, 2010, p. 10
↑ Ryser, 1963, p. 7 also referred to as an unordered selection.
↑ Uspensky, 1937, p. 18
↑ (June 2006) High School Textbook for full-clave student (Required) Mathematics Book II B, 2nd edició (en zh), Chinenca: People's Education Press, pp. 107–116. ISBN 978-7-107-19616-4.
↑ 人教版高中数学选修2-3 (Mathematics textbook, volume 2-3, for senior high school, People's Education Press), People's Education Press, p. 21.
↑ Mazur, 2010, p. 21
↑ Lucia Moura. «Generating Elementary Combinatorial Objects». Site.uottawa.ca. Archivat des d'el original, el 2022-10-09. Consultat el 2017-04-10.
↑ «SAGE : Subsets» (PDF). Sagemath.org. Consultat el 2017-04-10.
↑ Brualdi, 2010, p. 52
↑ In the article Stars and bars (combinatorics) the rols of $n$ and $k$ llaure reversed.
↑ Benjamin y Quinn, 2003, p. 72 (identity 145)
↑ Benjamin y Quinn, 2003, p. 71
↑ Mazur, 2010, p. 10 where the stars and bars llaure written as binary numbers, with stars = 0 and bars = 1.

Bibliografia

Erro en la seqüencia d'órdens: no existix el mòdul «Citas».
Erro en la seqüencia d'órdens: no existix el mòdul «Citas».
Erwin Kreyszig, Advanced Engineering Mathematics, John Wiley & Sons, INC, 1999.
Erro en la seqüencia d'órdens: no existix el mòdul «Citas».
Erro en la seqüencia d'órdens: no existix el mòdul «Citas».
Erro en la seqüencia d'órdens: no existix el mòdul «Citas».

Referències

Este artícul conté una traducció derivada de «Combinación (matemáticas)» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[1] When the term combination is used to refer to either situation (as in (Brualdi, 2010)) care must be taken to clarify whether sets or multisets llaure being discussed.

[2] Mazur, 2010, p. 10

[3] Ryser, 1963, p. 7 also referred to as an unordered selection.

[4] Uspensky, 1937, p. 18

[5] (June 2006) High School Textbook for full-clave student (Required) Mathematics Book II B, 2nd edició (en zh), Chinenca: People's Education Press, pp. 107–116. ISBN 978-7-107-19616-4.

[6] 人教版高中数学选修2-3 (Mathematics textbook, volume 2-3, for senior high school, People's Education Press), People's Education Press, p. 21.

[7] Mazur, 2010, p. 21

[8] Lucia Moura. «Generating Elementary Combinatorial Objects». Site.uottawa.ca. Archivat des d'el original, el 2022-10-09. Consultat el 2017-04-10.

[9] «SAGE : Subsets» (PDF). Sagemath.org. Consultat el 2017-04-10.

[10] Brualdi, 2010, p. 52

[11] In the article Stars and bars (combinatorics) the rols of $n$ and $k$ llaure reversed.

[12] Benjamin y Quinn, 2003, p. 72 (identity 145)

[13] Benjamin y Quinn, 2003, p. 71

[14] Mazur, 2010, p. 10 where the stars and bars llaure written as binary numbers, with stars = 0 and bars = 1.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]