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.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]​ De manera similar a como los coeficientes binomiales o combinacionesPara 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}.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]​y corresponde al número de k-combinaciones con repetición tomadas de un conjunto con n elementos.Así, del listado inicial podemos deducir queDado 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 esLa 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: 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: 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 binomialEste 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 deQueda establecido así el siguiente teorema.de multiconjuntos con k elementos escogidos de un conjunto con n elementos satisface: Y ademásExisten dos otras interpretaciones combinatorias importantes para los coeficientesRetomando el ejemplo de los 10 caramelos y los 4 niños, observamos que cada repartición corresponde a una soluciónsi 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., si las variables únicamente toman valores enteros no negativos.Esta interpretación se verifica a partir de la anterior tomando tantos términos iguales a i como tenga valorde multiconjuntos con k elementos escogidos de un conjunto con n elementos puede interpretarse también como: Las combinaciones con repetición satisfacen varias identidades que recuerdan o se asemejan a las identidades para coeficientes binomiales.