Combinaciones con repetición

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]

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:

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.

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

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.

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.

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}$.

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:

• 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)

• Multiconjunto
• Coeficiente binomial