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 tiene 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 , 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.
Así, del listado inicial podemos deducir que .
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.
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 qué 3 serán barras) y por tanto el resultado es el coeficiente binomial .
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 formas. Queda establecido así el siguiente teorema.
Otras interpretaciones combinatorias
Existen dos otras interpretaciones combinatorias importantes para los coeficientes
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 de la ecuación Plantilla:Ecuacion 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 → .
- ADDDDDDDDD → .
- AABBBBBDDD → .
La generalización sería que representa el número de soluciones de la ecuación Plantilla:Ecuación si las variables únicamente toman valores enteros no negativos.
La segunda interpretación es que 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 Plantilla:Ecuación Esta interpretación se verifica a partir de la anterior tomando tantos términos iguales a i como tenga valor .
Ejemplo:
- AABBBCCDDD: corresponde a la sucesión monótona
- ADDDDDDDDD: corresponde a la sucesión monótona
- AAAABBBBBC: corresponde a la sucesión monótona
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 tiene su equivalente en la siguiente identidad: Plantilla:Teorema
Referencias
Bibliografía
Véase también
Plantilla:Control de autoridades
- ↑ K. Ribnikov: Análisis Combinatorio ISBN 5-03-000610-9