Combinaciones con repetición

 

Es un tema de combinatoria que siempre se me atravesó.
Es un tema que en enseñanza secundaria se enuncia, te dan la fórmula, pero no aparece por ningún lado ni demostración ni indicación alguna de dónde sale la fórmula.
Pero luego en universidad te lo dan por sabido, así que nunca has visto demostración de la fórmula.
Para colmo, cuando te enfrentas a la demostración o demostraciones, se basan en una biyección que a mi no me resulta nada fácil de comprender.

AQUÍ VERÁS LA MISMA ENTRADA, PERO LAS FÓRMULAS SE MOSTRARÁN CORRECTAMENTE

AQUÍ VERÁS LA MISMA ENTRADA, PERO LAS FÓRMULAS SE MOSTRARÁN CORRECTAMENTE

Para lograr entender esa prueba, las dos versiones que conozco, van estas líneas. Se entiende que para comprender lo que sigue hay que estar familiarizados con la combinatoria que se da en la enseñanza media: principios fundamentales del conteo (principios de la suma y del producto), permutaciones sin repetición, variaciones sin repetición y combinaciones sin repetición. También cierta familiaridad con los factoriales y los números combinatorios. Esos serían los requisitos previos para poder manejarse con lo que sigue

Por otra parte no estoy tan interesado en una prueba formal como en comprender "de dónde sale la fórmula", los razonamientos y cálculos que permiten conocer el número de combinaciones con repetición de n elementos tomados de p en p.

Antes de comenzar el repaso pongo un enlace donde aparece lo básico de combinatoria. Al final se tratan también las combinaciones con repetición, pero, a mi juicio, de manera insuficiente
http://campus.cva.itesm.mx/nazira/Tc1003/PDF/Apuntes/0600%20Tc1003_Analisis_Combinatorio.pdf
No me gusta sobrecargar de enlaces estas entradas, pero ésta es realmente buena, está desarrollada toda la combinatoria de bachillerato de manera comprensible y "amable"
http://matap.dmae.upm.es/WebpersonalBartolo/Probabilidad/1_Combinatoria.pdf
En este enlace encontramos enunciados de problemas de combinatorio (bachillerato)
https://drive.google.com/file/d/0BzfhQuA7D_e6bHJKNVdXSmhvQ3c/view?usp=sharing
Y las soluciones a esos problemas están en
http://www.juntadeandalucia.es/averroes/iesarroyo/matematicas/materiales/4eso/solucionlibronuevo4b/U-11.pdf


Sin más preámbulos empezamos a repasar.
Comienzo con las combinaciones sin repetición, puesto que la prueba "reduce" las combinaciones con repetición a combinaciones sin repetición. Para comprender bien la prueba primero hay que entender perfectamente que son las combinaciones sin repetición para luego comprender también qué son las combinaciones con repetición. Sólo después de repasar estos conceptos abordaremos la prueba que es objeto de esta entrada con posibilidades de comprenderla.
Aunque voy a desarrollar lo básico directamente, no está de más señalar documentos donde consultar sobre combinatoria:
http://www.youtube.com/watch?v=mlsJzyJmNtc
http://bioinfo.uib.es/~merce/Docencia/AlgInf/Tema1/combinatoria.pdf
http://recursostic.educacion.es/descartes/web/materiales_didacticos/Combinatoria_2/introduccion.htm
http://bitacoraed.wordpress.com/2007/03/17/ecuaciones-con-numeros-combinatorios-2/
http://webs.ono.com/joaquinmateopo1/TECNICAS%20DE%20RECUENTO/NUMEROS%20COMBINATORIOS.pdf
http://www.youtube.com/watch?v=NTBHu_YXNBI
Por último, combinatoria avanzada  y mas combinatoria avanzada

Ahora desarrollamos la parte de la teoría que nos hace falta.
Me estoy permitiendo sacar texto de varios documentos de la red que luego mencionaré

1) Dos maneras alternativas de ver qué es una combinación sin repetición

Tenemos la definición clásica:

Definición 1
Las combinaciones sin repetición de n elementos tomados de p en p se definen como las distintas agrupaciones formadas con p elementos distintos, eligiéndolos de entre los n elementos de que disponemos, considerando una combinación distinta a otra sólo si difieren en algún elemento, (No influye el orden de colocación de sus elementos).

Hay una manera también clásica, de pensar en las combinaciones, imaginando a los n elementos, de manera que pintamos de rojo p de ellos y el resto los pintamos de azul. Así obtenemos la siguiente:

Definición 1 (ligeramente modificada)

Las combinaciones sin repetición de n elementos tomados de p en p se definen como las distintas maneras de marcar p elementos de entre los n dejando el resto sin marcar.

Definición 1 (más que modificada, simplificada) Cada combinación sin repetición de n elementos tomados de p en p no es más que un subconjunto de p elementos del conjunto de n elementos.

Con cualquiera de estas definiciones llegamos a la fórmula clásica

(AQUÍ VERÁS LA MISMA ENTRADA, PERO LAS FÓRMULAS SE MOSTRARÁN CORRECTAMENTE)

$$ C^{p} _n  = \displaystyle\frac{n!}{(n-p)! p!} $$ 

Iba a poner un enlace a una demostración, pero no encuentro: casi todos los archivos dan las fórmulas y trabajan el tema a partir de las fórmulas, pero no se dan indicaciones de cómo se ecuentran esas fórmulas, como si fueran revelación divina y no producto de esfuerzo e ingenio. (Me encomiendo a los curiosos y laboriosos lectores para que me indiquen enlaces a sitios donde se hallen dichas pruebas) 

2) Deducción del número de combinaciones sin repeticiones.

 Como no conseguí  enlace a ninguna prueba, pongo la mía (que es la que habitualmente vemos en todos los textos) Partimos de los siguientes hechos:

Conocemos qué son las variaciones de n elementos tomados de p en p  y también las permutaciones de n elementos y conocemos las fórmulas $$ P_n = n! $$   y   $$  V^{p} _n  =n(n-1)...(n-p+1)= \displaystyle\frac{n!}{(n-p)!} $$  y también conocemos las relaciones entre combinaciones, variaciones y permutaciones que resumimos de la siguiente manera:
Dada una combinación p-aria, ordenando sus elementos de todas las maneras posibles, obtenemos variaciones distintas.
Así, si manejamos combinaciones 3-arias de un conjunto de cinco elementos, $$  \{1,2,3,4,5 \} $$ la combinación 234 da origen a las variaciones 234, 243, 324, 342, 423, 432
En general, como el número de permutaciones de p elementos es $$ P_p = p! $$ cada combinación p-aria da origen a $$ p! $$ variaciones distintas. Por consiguiente se cumple: $$ V^{p} _n  = C^{p} _n  \cdot{P_p}$$ de donde $$ C^{p} _n = \displaystyle\frac{V^{p} _n }{P_p} = \displaystyle\frac{n(n-1)...(n-p+1)}{p!} $$
Multiplicando el numerador y el denominador por el número $$ (n-p)(n-p-1)...3 \cdot{2} \cdot{1} = (n-p)! $$  (ya que suponemos $$ p<n $$ ) obtenemos la expresión habitual $$ C^{p} _n = \displaystyle\frac{n!}{(n-p)!p!} $$

Ahora voy a explicar qué son combinaciones con repetición. es decir, vamos a entrar en materia. Para ver lo mismo que voy a poner, pero más resumido, entra en http://thales.cica.es/rd/Recursos/rd99/ed99-0516-02/practica/comb_rept.htm
Proseguimos:
3) Qué es una combinación con repetición. Ejemplos.
El problema de las combinaciones sin repetición era, partiendo de un conjunto de n elementos diferentes, formar grupos de p elementos, también diferentes.
Supongamos ahora que hay varias copias idénticas de cada uno de los n objetos, como por ejemplo idénticas copias de libros en una librería, o pasteles indistinguibles entre sí en una pastelería. Entonces podemos preguntarnos:Dadas n categorías diferentes de objetos, disponiendo de suministro ilimitado de elementos de cada categoría, ¿cuántas combinaciones de p elementos pueden formarse? (cada combinación puede contener varios elementos indistinguibles entre sí)
Por ejemplo, imaginemos cuatro amigos que van a una pastelería donde pueden comprar seis tipos diferentes de dulces: melillas, milojas, casitas, japonesas, piononos y riñoncitos. Suponemos que cada uno de los amigos elige el dulce que más le apetece. ¿De cuántas maneras se pueden elegir los dulces?
Una elección puede ser
                  japonesa, japonesa, japonesa, japonesa
otra puede ser  miloja, miloja, casita, casita                 etc
Aquí adoptamos el punto de vista del vendedor, al que le da igual qué amigo compra qué dulce, de manera que no distinguimos el caso en que Alberto compra melilla y Benito elige miloja, del caso en que es Alberto el que compra miloja y Benito el de la melilla.
Así llegamos a la siguiente definición:

Los grupos de p objetos, distintos o repetidos, elegidos entre n dados, considerando como iguales los formados por los mismos objetos repetidos el mismo número de veces, se llaman combinación p-aria con repetición entre n objetos. El número de combinaciones con repetición de n elementos tomados de p en p se representará $$ CR^{p} _n $$

Siempre que se da una definición conviene ilustrarla con ejemplos:

Consideremos tres objetos a,b,c y vamos a formar combinaciones con repetición
Combinaciones monarias:  Son sólo tres:  a     b       c   Por tanto $$ CR^{1} _3 = 3 $$
Combinaciones binarias:  aa,  ab,     ac,     bb,     bc,     cc.    Son  6. Por tanto $$ CR^{2} _3   = 6 $$
Combinaciones ternarias:
aaa,    aab,     aac,     abb,      abc,      acc,      bbb,      bbc,      bcc,       ccc.     Son en total 10
Por tanto  $$ CR^{3} _3  = 10 $$

Combinaciones cuaternarias:  son en total 15
aaaa         aaab          aaac                                    accc
aabb         aabc                                                     bbbb,           bbbc
aacc                                                                      bbcc
abbb        abbc                                                      bccc
abcc                                                                      cccc

Por tanto $$ CR^{4} _3 = 15 $$

AQUÍ VERÁS LA MISMA ENTRADA, PERO LAS FÓRMULAS SE MOSTRARÁN CORRECTAMENTE

4) Método para resolver el problema: lo reformulamos trasladándolo a otro campo

Todas las pruebas que he visto, que en el fondo son variaciones de la misma prueba, hacen lo mismo: reformulan el problema, convirtiéndolo en otro que sí se resuelve.
La prueba que mejor he entendido comienza reinterpretando las combinaciones con repetición como soluciones (¡atención!, esto es clave, sólo se permiten como soluciones números enteros no negativos) de la ecuación, $$ x_1 +x_2 +x_3 +.....+x_n = p $$

En el ejemplo de antes, el de la pastelería, tendríamos $$ x_1 + x_2  +x_3  +x_4  + x_5 +x_6 = 4 $$
donde
  $$ x_1 $$ significa el número de melillas que se compran, (para simplificar pondremos en vez de melilla "me")
  $$x_2$$ el número de milojas (en adelante representaremos miloja por "mi")
$$x_3$$ el número de casitas (simplificaremos casita por "ca")
$$x_4 $$ el número de japonesas (nos referiremos a las japonesas por "ja")
$$x_5$$ el número de piononos (en vez de piononos, pondremos "pi")
$$x_6$$ el número de riñoncitos (en vez de riñoncitos pondremos "ri")
Todos estos números pueden ser cero o números enteros positivos, pero cumpliendo la condición de que la suma de los seis valga 4

Vamos a explicar el método de razonamiento para este ejemplo concreto y más tarde lo aplicaremos a otros casos. Al final llegaremos a una generalización, que es nuestro objetivo final.

Primero vamos a asegurar que entendemos que cada combinación con repetición cuaternaria de estos seis elementos corresponde a una solución de la ecuación anterior y recíprocamente.
Por ejemplo la  combinación con repetición $$ \{ mi,mi,ja,ja \}$$  corresponde a la solución $$ x_1 =0, x_2 = 2, x_3 =0, x_4 =2, x_5 = 0, x_6 =0 $$
Por otra parte la solución $$ x_1 =1, x_2 =0, x_3 =0, x_4 =1, x_5= 0, x_6 =2 $$ corresponde a la combinación con repetición  $$  \{ me, ja, ri,ri \} $$
Podemos convencernos realizando los ejemplos que se nos ocurran de que a cada combinación con repetición corresponde una única solución, y que a cada solución corresponde una única combinación con repetición.
En esta situación en matemáticas se dice que hemos definido una biyección entre el conjunto de las combinaciones con repetición y el de las soluciones. Como consecuencia de esto, hay el mismo número de combinaciones con repetición que de soluciones de la ecuación. Por tanto si hallamos el número de soluciones, tendremos el número de combinaciones con repetición.

5) La famosa biyección : vemos cómo a cada combinación con repetición corresponde una única combinación sin repetición

Seguimos viendo el método general mediante el problema concreto de los 4 amigos en la pastelería

Atentos/as ahora a como vamos a hallar el número de soluciones, porque no lo vamos a hacer directamente, sino estableciendo otra biyección. La cosa es como sigue:

Para hallar el número de soluciones (en números enteros no negativos) de  $$ x_1 + x_2  +x_3  +x_4  + x_5 +x_6 = 4 $$  tenemos que realizar un segundo "artificio". Imaginamos que tenemos cuatro "unidades" (que representamos por "u")  y 6-1=5 separadores (que representamos por "s") y que formamos ristras  de 9 elementos, que son unos ues y otros eses.
(¡Atención! Son 5 "eses" otra vez porque para separar las "ues" de la fila en seis lotes, hacen falta  cinco "eses")
Una ristra puede ser $$sussuusus$$.  Otra fila de 9 elementos puede ser: $$uusssuss$$.
Siempre son 9 elementos, 4 de ellos "ues" y 5 de ellos "eses"
Observa que hay tantas "ues" como indica la suma total de las soluciones, y tantas "eses" como el número de incógnitas diferentes menos 1.
A su vez en el lenguaje de las combinaciones con repetición, las u corresponden al tamaño de las combinaciones, p,  y las s se derivan del  número de categorías diferentes de objetos, n


 Daremos una regla mediante la cual a cada ristra o fila  vamos a hacer corresponder una única solución y a cada solución una única ristra. Así volvemos a tener una biyección , esta vez entre soluciones y ristras. Cuando consigamos hallar el número de ristras, tendremos el de soluciones (y además,claro, el de combinaciones con repetición)

La regla es la siguiente: Dada una fila de s y u,  el valor de $$x_1$$ se obtiene contando las u que hay a la izquierda de la primera s,  el valor de $$x_2$$ se obtiene contando las u que hay entre la primera y la segunda s, .... y así hasta el valor de $$x_6$$  que se obtiene contando las u que hay a la derecha de la última s

Ejemplos
$$ ussusuuss $$ corresponde a la solución $$ x_1 = 1, x_2 = 0, x_3 =1, x_4 = 2,  x_5 =0, x_6 = 0 $$
$$ sssuussuu$$ corresponde a la solución $$ x_1 =0,  x_2 =0, x_3 =0, x_4 =2, x_5 =0, x_6 =  2 $$
$$ x_1 =0, x_2 =0 , x_3 =1, x_4 =1, x_5 =1, x_6 =1 $$ corresponde a  $$ ssusususu $$

Bien, ahora vamos a preguntarnos cúantas filas diferentes de "ues" y  "eses" hay. Tenemos 9 elementos, de los cuales 5 son s y 4 son u.
Luego hay tantas filas diferentes como elecciones podemos hacer para marcar 5 elementos como s (o bien 4 elementos como u) que según la "definición 1 (ligeramente modificada)" eran $$ C^{4} _9  = C^{5} _9 $$
Por tanto el número de soluciones de  $$ x_1 + x_2  +x_3  +x_4  + x_5 +x_6 = 4 $$ es $$ C^{4} _9  = C^{5} _9 $$

En resumen cada combinación cuaternaria con repetición de seis elementos se corresponde mediante la biyección  que hemos definido, con  una combinación ordinaria  (sin repetición) de 9 elementos tomados de cuatro en cuatro.
Hay que darse cuenta de que interpretamos la combinación sin repetición como una manera de marcar con u cuatro de los nueve elementos.


Esto quiere decir que hay tantas combinaciones con repetición de seis elementos tomados de cuatro en cuatro como combinaciones sin repetición (ordinarias) de 9 elementos tomados de 4 en cuatro.
En fórmulas, $$ CR^{4} _6  =  C^{4} _9  =  \displaystyle\frac{9!}{5! \cdot{4!}} $$


Vamos a ver cómo funciona este razonamiento en otro caso. Suponemos que a la misma pastelería del ejemplo anterior van esta vez 10 amigos.

PRIMER PASO: Se trata de hallar el número de combinaciones con repetición de 6 elementos tomados de 10 en 10. Consideramos grupos de 10 elementos formados con los 6 pasteles, pudiéndose repetir los elementos, tales como
$$ \{ me,mi,mi,mi,ca,ja,ja,ja,ja,ri \} $$  o  $$ \{ mi,mi,mi,ja,ja,ja,pi,pi,pi,pi \} $$ etc.

SEGUNDO PASO:  Pasamos de las combinaciones con repetición a las soluciones en números enteros no negativos de la ecuación $$ x_1 +x_2 +x_3  + x_4 + x_5 + x_6 = 10 $$

TERCER PASO:  Asociamos a cada solución de la ecuación  $$ x_1 +x_2 +x_3  + x_4 + x_5 + x_6 = 10 $$ una única fila compuesta por 10 "ues"  y  6-1 =5  "eses",  como por ejemplo  $$  usuuususuuuussu $$  o bien $$ suuussuuusuuuus $$
¡Atención! Son 5 "eses" otra vez porque para separar las "ues" de la fila en seis lotes, hacen falta  cinco "eses"
CUARTO PASO: El número de filas es $$ C^{5} _{15} = C^{10} _{15}  $$

CONCLUSIÓN         $$ CR^{10} _6 =   C^{10} _{15} $$


6)  Generalización

Ahora repetimos el mismo esquema, pero con $$ CR^p  _n $$


PRIMER PASO: Se trata de hallar el número de combinaciones con repetición de n elementos tomados de p en p. Consideramos grupos de p elementos formados con los n elementos (o categorías de elementos) pudiéndose repetir los elementos

SEGUNDO PASO:  Pasamos de las combinaciones con repetición a las soluciones en números enteros no negativos de la ecuación $$ x_1 +x_2 +x_3  + .....+x_{n-1} + x_n  = p $$

TERCER PASO:  Asociamos a cada solución de la ecuación  $$ x_1 +x_2 +x_3  + .....+x_{n-1} + x_n  = p $$ una única fila compuesta por p "ues"  y  n-1   "eses"
¡Atención! Son n-1 "eses" otra vez porque para separar las "ues" de la fila en n lotes, hacen falta  n-1 "eses"

CUARTO PASO: El número de filas es $$ C^{n-1} _{p+n-1} = C^{p} _{p+n-1}  $$

CONCLUSIÓN         $$ CR^{p} _n =   C^{p} _{p+n-1}  = C^{n-1} _{p+n-1} $$

7) Por fin la fórmula
De las dos posibilidades nos quedamos con la que sugiere tomar las combinaciones ordinarias también de p en p
$$ CR^p _n   =  C^p _{p+n-1} $$

Para más adelante
8) Comprobaciones
9) Otros problemas

10) Bibliografía: Los libros donde se explica este asunto de manera completa y clara son:
                         *  Mathematics of Choice/How to Count without Counting, by Ivan Niven  (in English)
                         *   Matemática discreta, por Francisco Javier Cirre Torres
                         *  También he utilizado el Grimaldi (Matemática discreta y combinatoria) y el Análisis                          Algebraico de Rey Pastor

Termino con un enlace en el que se trata la combinatoria con cierta profundidad
http://imerl.fing.edu.uy/matdisc1/archivos/Material/capitulo2.pdf

Libro dedicado a la combinatoria
https://drive.google.com/file/d/0B6IfwG5dZJExam9WV2dlc0FCb2s/view 

Como ves imaginado/a lector/a se trata de una entrada en construcción dentro de un blog en construcción.
Anímate a comentar aciertos y errores, tanto en el planteamiento como en la ejecución, tanto en lo nimio como en el fondo del planteamiento.
Gracias de antemano.
Hasta la próxima entrada.