Combinaciones con repetición

En combinatoria, las combinaciones con repetición de un conjunto son las distintas formas en que se puede hacer una selección de elementos de un conjunto dado, permitiendo que las selecciones puedan repetirse.

De manera formal, una combinación con repetición es la selección de un multiconjunto cuyos elementos pertenezcan a un conjunto dado.

Enunciado del problema

En este caso el problema que se plantea es como sigue: se tienen objetos de n tipos diferentes. ¿Cuántas k-disposiciones se pueden formar usando estos, si no se toma en cuenta el orden de los elementos en la disposición ( en otras palabras, diferentes disposiciones deben distinguirse por lo menos en un objeto)?^[1]​

Definición

De manera similar a como los coeficientes binomiales o combinaciones ${\displaystyle {\binom {n}{k}}}$ , corresponden al número de formas en que se puede seleccionar un subconjunto de k elementos a partir de un conjunto dado con n elementos, es posible plantear el problema de determinar el número de formas de escoger un multisubconjunto de un conjunto.

Recordemos que en un multiconjunto es permitido repetir elementos aunque, al igual que en los conjuntos, el orden en que se mencionan es irrelevante.

Por ejemplo, {a, e, e, i, o, o, o, u} es el mismo multiconjunto que {e, i, o, u, a, e, o, o}

Para ilustrar el problema, consideremos el conjunto X={a, b, c, d}. Listemos todos los posibles multiconjuntos de 3 elementos obtenidos del conjunto X. Para brevedad, indicaremos las letras como si fuesen una palabra:

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

Se recalca que el orden no importa, por esto es que no se lista por ejemplo, aca ya que el multiconjunto {a, c, a} es el mismo que el multiconjunto {a, a, c}. Estas selecciones donde se permite repetición pero no se toma en cuenta el orden se denominan combinaciones con repetición.

El número de formas en que se puede extraer un multiconjunto con k elementos de un conjunto con n elementos se denota^[2]​^[3]​ ${\displaystyle \left(\!\!{n \choose k}\!\!\right)}$  y corresponde al número de k-combinaciones con repetición tomadas de un conjunto con n elementos.

Así, del listado inicial podemos deducir que ${\displaystyle \scriptstyle \left(\!\!{4 \choose 3}\!\!\right)=20}$ .

Cálculo del número de combinaciones con repetición

Antes de establecer una fórmula para el cálculo directo de combinaciones con repetición, plantearemos un ejemplo clásico de problema relacionado con multiconjuntos.

¿De cuántas maneras se puede repartir 10 caramelos a 4 niños?

Vamos a imaginar que los nombres son Alonso, Berta, Carla y Daniel (que representaremos como A, B, C, D). Una posible forma de repartir los caramelos sería: dar 2 caramelos a Alonso, 3 a Berta, 2 a Carla y 3 a Daniel. Dado que no importa el orden en que se reparten, podemos representar esta selección como AABBBCCDDD Otra forma posible de repartir los caramelos podría ser: dar 1 caramelo a Alonso, ninguno a Berta y Carla, los 9 restantes se los damos a Daniel. Esta repartición la representamos como ADDDDDDDDD De manera inversa, cualquier serie de 10 letras A, B, C, D corresponde a una forma de repartir los caramelos. Por ejemplo, la serie AABBBBBDDD corresponde a: Dar dos caramelos a Alonso, 5 caramelos a Berta, ninguno a Carla y 3 a Daniel. De esta forma, por el principio de la biyección, el número de formas en que se puede repartir los caramelos es igual al número de series de 10 letras (sin tomar en cuenta el orden) A, B, C, D. Pero cada una de ellas corresponde a un multiconjunto con 10 elementos, por lo que concluimos que el número total de formas de repartir los caramelos es ${\displaystyle \scriptstyle \left(\!\!{4 \choose 10}\!\!\right)}$ .

La solución del ejemplo anterior es conceptualmente correcta (da el resultado mediante una interpretación combinatoria) pero no es práctica ya que no proporciona realmente el número de formas en que se puede hacer la repartición. Para obtener la fórmula procedemos a usar la siguiente estratagema.

Queremos dividir 10 objetos (los caramelos) en 4 grupos. Para ello colocamos 10 objetos en línea e insertamos 3 separadores para dividirlos en 4 secciones. Por ejemplo, si representamos los caramelos con asteriscos y los separadores con barras, los ejemplos mencionados serían:

• AABBBCCDDD → **/***/**/***
• ADDDDDDDDD → *///*********
• AABBBBBDDD → **/*****//***

Y cualquier serie de 10 asteriscos separados por 3 barras (permitiendo grupos vacíos) corresponde a una forma de repartir y a su vez, a un multiconjunto:

• ****/***/**/* → AAAABBBCCD (4 caramelos para Alonso, 3 para Berta, 2 para Carla y 1 para Daniel)
• *****/*****// → AAAAABBBBB (5 caramelos para Alonso y 5 para Berta)

De esta forma, el número de formas de repartir corresponde al número de series de 10 asteriscos y 3 barras. Pero esto es precisamente el número de formas de elegir 3 objetos de un conjunto con 13 (de las 13 posiciones se están escogiendo cuales 3 serán barras) y por tanto el resultado es el coeficiente binomial ${\displaystyle {\binom {13}{3}}=286}$ .

Este argumento se puede aplicar en general: repartir k objetos entre n personas, corresponde a formar multiconjuntos de tamaño k (los caramelos) escogidos de un conjunto con n (los niños), y a su vez esto puede enumerarse con una serie de k asteriscos y n-1 barras, que puede realizarse de ${\displaystyle {\binom {k+(n-1)}{n-1}}={\binom {n+k-1}{k}}}$  formas. Queda establecido así el siguiente teorema.

El número ${\displaystyle \scriptstyle \left(\!\!{n \choose k}\!\!\right)}$  de multiconjuntos con k elementos escogidos de un conjunto con n elementos satisface: Es igual al número de combinaciones con repetición de k elementos escogidos de un conjunto con n elementos. Es igual al número de formas de repartir k objetos en n grupos. Y además ${\displaystyle \left(\!\!{n \choose k}\!\!\right)={\binom {n+k-1}{k}}={\frac {(n+k-1)!}{k!(n-1)!}}}$ .

Otras interpretaciones combinatorias

Existen dos otras interpretaciones combinatorias importantes para los coeficientes ${\displaystyle \displaystyle \left(\!\!{n \choose k}\!\!\right)={\binom {k+n-1}{n-1}}}$ 

La primera interpretación está relacionada con el número de soluciones de ciertas ecuaciones diofánticas. Retomando el ejemplo de los 10 caramelos y los 4 niños, observamos que cada repartición corresponde a una solución ${\displaystyle (x_{1},x_{2},x_{3},x_{4})}$  de la ecuación

${\displaystyle x_{1}+x_{2}+x_{3}+x_{4}=10}$ 

si cada variable puede tomar únicamente valores enteros no negativos.

La correspondencia está dada por asignar a la variable i-ésima el número de caramelos recibidos por el i-ésimo niño. Como ejemplo:

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

La generalización sería que ${\displaystyle \displaystyle \left(\!\!{n \choose k}\!\!\right)}$  representa el número de soluciones de la ecuación

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

si las variables únicamente toman valores enteros no negativos.

La segunda interpretación es que ${\displaystyle \displaystyle \left(\!\!{n \choose k}\!\!\right)}$  corresponde al número de sucesiones monótonas de k términos positivos, acotadas por n, es decir, cuenta el número de formas de llenar la sucesión

${\displaystyle 1\leq a_{1}\leq a_{2}\leq \cdots \leq a_{k}\leq n}$ .

Esta interpretación se verifica a partir de la anterior tomando tantos términos iguales a i como tenga valor ${\displaystyle x_{i}}$ .

Ejemplo:

• AABBBCCDDD: ${\displaystyle x_{1}=2,x_{2}=3,x_{3}=2,x_{4}=3\,}$  corresponde a la sucesión monótona

${\displaystyle 1\leq 1\leq 2\leq 2\leq 2\leq 3\leq 3\leq 4\leq 4\leq 4}$ .

• ADDDDDDDDD: ${\displaystyle x_{1}=1,x_{2}=0,x_{3}=0,x_{4}=9\,}$  corresponde a la sucesión monótona

${\displaystyle 1\leq 4\leq 4\leq 4\leq 4\leq 4\leq 4\leq 4\leq 4\leq 4}$ .

• AAAABBBBBC: ${\displaystyle x_{1}=4,x_{2}=5,x_{3}=1,x_{4}=0\,}$  corresponde a la sucesión monótona

${\displaystyle 1\leq 1\leq 1\leq 1\leq 2\leq 2\leq 2\leq 2\leq 2\leq 3}$ .

El número ${\displaystyle \scriptstyle \left(\!\!{n \choose k}\!\!\right)}$  de multiconjuntos con k elementos escogidos de un conjunto con n elementos puede interpretarse también como: El número de soluciones enteras no negativas de la ecuación ${\displaystyle x_{1}+x_{2}+\cdots +x_{n}=k}$ . El número de sucesiones monótonas positivas ${\displaystyle 1\leq a_{1}\leq a_{2}\leq \cdots \leq a_{k}\leq n}$ .

Identidades

Las combinaciones con repetición satisfacen varias identidades que recuerdan o se asemejan a las identidades para coeficientes binomiales.

Por ejemplo, la identidad de Pascal ${\displaystyle \displaystyle {\binom {n-1}{k-1}}+{\binom {n-1}{k}}={\binom {n}{k}}}$  tiene su equivalente en la siguiente identidad:

Para cualquier ${\displaystyle n\geq 0,k\geq 0}$  (exceptuando ${\displaystyle n=k=0}$ ) se cumple ${\displaystyle \left(\!\!{{n-1} \choose k}\!\!\right)+\left(\!\!{n \choose {k-1}}\!\!\right)=\left(\!\!{n \choose k}\!\!\right)}$

Referencias

1. K. Ribnikov: Análisis Combinatorio ISBN 5-03-000610-9
2. Eric W. Weisstein. «Multichoose». Wolfram Mathworld. Consultado el 15 de diciembre de 2011. 
3. Quinn, Benjamin Arthur T.; Quinn, Jennifer J. (2003). Proofs that Really Count: The art of combinatorial proof. The Mathematical Association of America. pp. 70-71. ISBN 0-88385-333-7. 

Bibliografía

• Arthur Benjamin (2003). Proofs that really count. Mathematical Association of America. ISBN 0883853337.  |fechaacceso= requiere |url= (ayuda)
• Miklos Bona (2006). A Walk Through Combinatorics (2 edición). World Scientific Publishing Company. ISBN 9812568859.  |fechaacceso= requiere |url= (ayuda)

Véase también

• Multiconjunto
• Coeficiente binomial

•   Datos: Q5558950