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.
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).
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
$$ 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: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:
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 $$
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.
Comentarios
Publicar un comentario
Los comentarios son bienvenidos siempre que sean respetuosos y corteses y traten del asunto de la entrada.
Dirige un correo a martinjaime80@hotmail.com informando de que deseas publicar un comentario