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.
¿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
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
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:
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 . |
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
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
,
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
.
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:
|
Referencias
- ↑ K. Ribnikov: Análisis Combinatorio ISBN 5-03-000610-9
- ↑ Eric W. Weisstein. «Multichoose». Wolfram Mathworld. Consultado el 15 de diciembre de 2011.
- ↑ 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. Consultado el 03:19 15 dic 2011 (UTC).
- 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