Combinacions en repetició

En combinatòria, les combinacions en repetició d'un conjunt són les distintes formes en que es pot fer una selecció d'elements d'un conjunt dau, permetent que les seleccions de dits elements puguen repetir-se.

De manera formal, una combinació en repetició és la selecció d'un multiconjunto, els elements del qual pertanyguen a un conjunt de tamany donat.

Enunciat del problema

En este cas el problema que es planteja és com seguix: es tenen objectes de n tipos diferents. ¿Quantes k-disposicions es poden formar usant estos, si no es té en conte l'orde dels elements en la disposició (en atres paraules, diferents disposicions deuen distinguir-se per lo manco en un objecte)?^[1]

Definició

De manera similar a com els coeficients binomiales o combinacions $(\binom{n}{k})$ , corresponen al número de formes en que es pot seleccionar un subconjunt de k elements a partir d'un conjunt donat en n elements, és possible plantejar el problema de determinar el número de formes de triar un multisubconjunto d'un conjunt.

Recordem que en un multiconjunto és permés repetir elements encara que, de la mateixa manera que en els conjunts, l'orde en que es mencionen és irrellevant.

Per eixemple, {a, i, i, i, o, o, o, o} és el mateix multiconjunto que {i, i, o, o, a, i, o, o}

Per a ilustrar el problema, considerem el conjunt X={a, b, c, d}. Llistem tots els possibles multiconjuntos de 3 elements obtinguts del conjunt X. Per a brevetat, indicarem les lletres com si anaren una paraula:

aaa	aab	aac	aad	abb	abc	abd	acc	acd	add
bbb	bbc	bbd	bcc	bcd	bdd	ccc	ccd	cdd	ddd

Es recalca que l'orde no importa, per açò és que no es llista per eixemple, aca ya que el multiconjunto {a, c, a} és el mateix que el multiconjunto {a, a, c}. Estes seleccions a on es permet repetició pero no es pren en conte l'orde es denominen combinacions en repetició.

Aixina, del llistat inicial podem deduir que $((\binom{4}{3})) = 20$ .

Càlcul del número de combinacions en repetició

Abans d'establir una fòrmula per al càlcul directe de combinacions en repetició, plantejarem un eixemple clàssic de problema relacionat en multiconjuntos.

La solució de l'eixemple anterior és conceptualment correcta (dona el resultat per mig d'una interpretació combinatòria) pero no és pràctica ya que no proporciona realment el número de formes en que es pot fer el repartiment. Per a obtindre la fòrmula procedim a usar la següent estratagema.

Volem dividir 10 objectes (els caramelos) en 4 grups. Per a això coloquem 10 objectes en llínea i insertem 3 separadores per a dividir-los en 4 seccions. Per eixemple, si representem els caramelos en asteriscs i els separadores en barres, els eixemples mencionats serien:

AABBBCCDDD → **/***/**/***

ADDDDDDDDD → *///*********

AABBBBBDDD → **/*****//***

I qualsevol série de 10 asteriscs separats per 3 barres (permetent grups buits) correspon a una forma de repartir i a la seua volta, a un multiconjunto:

****/***/**/* → AAAABBBCCD (4 caramelos per a Alonso, 3 per a Berta, 2 per a Carla i 1 per a Daniel)

*****/*****// → AAAAABBBBB (5 caramelos per a Alonso i 5 per a Berta)

D'esta forma, el número de formes de repartir correspon al número de séries de 10 asteriscs i 3 barres. Pero açò és precisament el número de formes d'elegir 3 objectes d'un conjunt en 13 (de les 13 posicions s'estan triant qué 3 seran barres) i per tant el resultat és el coeficient binomial $(\binom{13}{3}) = 286$ .

Este argument es pot aplicar en general: repartir k objectes entre n persones, correspon a formar multiconjuntos de tamany k (els caramelos) triats d'un conjunt en n (els niños), i a la seua volta açò pot enumerar-se en una série de k asteriscs i n-1 barres, que pot realisar-se de $(\binom{k + (n - 1)}{n - 1}) = (\binom{n + k - 1}{k})$ formes. Queda establit aixina la següent teorema.

Atres interpretacions combinatòries

Existixen dos atres interpretacions combinatòries importants per als coeficients $((\binom{n}{k})) = (\binom{k + n - 1}{n - 1})$

La primera interpretació està relacionada en el número de solucions de certes equacions diofánticas. Reprenent l'eixemple dels 10 caramelos i els 4 chiquets, observem que cada repartiment correspon a una solució $(x_{1}, x_{2}, x_{3}, x_{4})$ de l'equació Plantilla:Ecuacion si cada variable pot prendre únicament valors sancers no negatius.

La correspondència està donada per assignar a la variable i-ésima el número de caramelos rebuts pel i-ésimo chiquet. Com a eixemple:

AABBBCCDDD → $x_{1} = 2, x_{2} = 3, x_{3} = 2, x_{4} = 3$ .
ADDDDDDDDD → $x_{1} = 1, x_{2} = 0, x_{3} = 0, x_{4} = 9$ .
AABBBBBDDD → $x_{1} = 2, x_{2} = 5, x_{3} = 0, x_{4} = 3$ .

La generalisació seria que $((\binom{n}{k}))$ representa el número de solucions de l'equació

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

si les variables únicament prenen valors sancers no negatius.

La segona interpretació és que $((\binom{n}{k}))$ correspon al número de successions monòtones de k térmens positius, acotades per n, és dir, conta el número de formes d'omplir la successió

$1 \leq a_{1} \leq a_{2} \leq \dots \leq a_{k} \leq n$ .

Esta interpretació es verifica a partir de l'anterior prenent tants térmens iguals a i com tinga valor $x_{i}$ .

Eixemple:

AABBBCCDDD: $x_{1} = 2, x_{2} = 3, x_{3} = 2, x_{4} = 3$ correspon a la successió monòtona

$1 \leq 1 \leq 2 \leq 2 \leq 2 \leq 3 \leq 3 \leq 4 \leq 4 \leq 4$ .

ADDDDDDDDD: $x_{1} = 1, x_{2} = 0, x_{3} = 0, x_{4} = 9$ correspon a la successió monòtona

$1 \leq 4 \leq 4 \leq 4 \leq 4 \leq 4 \leq 4 \leq 4 \leq 4 \leq 4$ .

AAAABBBBBC: $x_{1} = 4, x_{2} = 5, x_{3} = 1, x_{4} = 0$ correspon a la successió monòtona

$1 \leq 1 \leq 1 \leq 1 \leq 2 \leq 2 \leq 2 \leq 2 \leq 2 \leq 3$ .

Referències

↑ K. Ribnikov: Anàlisis Combinatori ISBN 5-03-000610-9

Bibliografia

Vore també

Referències

Este artícul conté una traducció derivada de «Combinaciones con repetición» 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] K. Ribnikov: Anàlisis Combinatori ISBN 5-03-000610-9

[1]