¿Puede encontrarse una fórmula algorítmica (es decir, operativa, no solo conceptual) para el número de n-combinaciones con repetición "limitada"?...

NOTA SOBRE LA AUTORÍA DE LA RESOLUCIÓN DE ESTE PROBLEMA:

Ignoro si este problema propuesto por mí en este foro estaba formulado, resuelto y publicado con anterioridad, por lo cual, hasta donde yo sé, mi solución es original, salvo que existiera un precedente publicado antes de ahora.

Para exponer mi propio método de resolución de este problema, que yo mismo planteé como pregunta en este foro, consigno a continuación, y en primer lugar las notaciones que emplearé. Algunas son de uso común y extendido, mientras que otras las he elegido personalmente para abreviar o unificar la solución del presente problema combinatorio.

NOTACIÓN: Sean m, n enteros positivos.

C(m,n) = [m↓n] = nº de combinaciones sin repetición de m elementos tomados de n en n = m! / [n! * (m-n)! ].

CR (m,n) = número de combinaciones con repetición (ilimitada)

de m elementos tomados de n en n. No importa el orden y cada elemento puede desde no figurar en una combinación, hasta figurar repetido 1, 2…y hasta n veces, como máximo.

Es sabido que CR (m,n) = [(m+n-1)↓n] = (m+n-1)! / [(m-1)! * n! ]

Convenios de notación:

0! = 1! = 1

(Curiosamente, entre los principiantes se discute mucho sobre el porqué del convenio 0! =1 pero no sobre porqué se conviene en que 1! =1, que ciertamente es otro convenio, pues 1! no es ningún producto, dado que no existe un producto de un solo factor. Todo el "misterio" se debe a la comodidad de poder aplicar la fórmula

[m↓n] = m! / [n! * (m-n)! ] en los casos n=m, n = 1 o incluso [m↓0]).

[m↓0] = 1; [0↓0] = 1; CR (m,0) = 1 ; CR (0,n) = 0 ; CR (m,1) = m ;

en este último caso, el de las combinaciones con repetición de m elementos tomados de 1 en 1, la repetición es imposible, pero en todos los textos sobre combinatoria se sigue admitiendo la definición de combinaciones con repetición, en el sentido de que la repetición no se excluye como condición previa, aunque de hecho no es posible que haya ninguna, y así CR (m,1) = C (m,1) = [m↓1] = m ;

CR (m, - n) = 0. Si m < n → por definición, [m↓n] = 0 , CR (m,n) = 0.

Gracias a estos convenios de notación no tendremos que establecer continuamente advertencias sobre en qué casos las fórmulas combinatorias -que emplearemos en este problema y en muchos otros- tienen o no tienen sentido.

MI SOLUCIÓN DEL PROBLEMA

Supongamos que tenemos los elementos distintos

a₁, a₂…, aₘ, y para computar el número exacto de sus combinaciones de n en n, con repetición limitada cada uno de ellos, nos imponen las limitaciones en su repetición r₁, r₂…, rₘ,

siendo cada uno de los rⱼ un entero tal que 1 ≤ rⱼ ≤ n,

para todo j tal que 1 ≤ j ≤ m.

Para que la notación no oscurezca las ideas, esto significa que a₁ puede no figurar en cada combinación de las que queremos hacer el recuento, o bien puede figura una vez, o dos veces…o hasta r₁ veces, pero no más de r₁ veces; análogamente, a₂ solo puede aparecer en cada combinación repetido desde 0 hasta r₂ veces…etc.

Llamaremos rebosamiento de aⱼ al conjunto de todas las combinaciones con repetición ilimitada, cuyo número total es

CR (m,n), en las cuales aⱼ se repita más de rⱼ veces.

Por ejemplo, si r₁ = 3, m = 4 , n = 8,

la combinación [a₁a₁a₁a₁ a₂a₂ a₃a₃] pertenece al rebosamiento de a₁, porque a₁ está repetida más veces de lo permitido, que eran 3 veces como máximo. Puede pertenecer a la vez a otros rebosamientos, o no hacerlo, según sean las limitaciones de los demás elementos. Por ejemplo, si r₂ = 1, la combinación anterior pertenece tanto al rebosamiento de a₁, como al rebosamiento de a₂.

Representaremos este conjunto por R(a₁).

Del mismo modo, y en general, para cada j entero, tal que 1 ≤ j ≤ m,

R(aⱼ) es el conjunto de n-combinaciones con repetición ilimitada, de a₁, a₂…, aₘ en las que aⱼ se repite más veces que rⱼ, el máximo permitido.

La intersección: R(aⱼ) ∩ R(aₖ) será el conjunto de n-combinaciones con repetición ilimitada, de a₁, a₂…, aₘ en las que aⱼ se repite más veces que rⱼ, y también aₖ se repite más veces que rₖ. Es decir, hay rebosamiento tanto en aⱼ como en aₖ. Pero para más comodidad de notación, omitiremos el signo de intersección,y escribiremos

R(aⱼ) ∩ R(aₖ) = R(aⱼ , aₖ).

En general, R(aⱼ , aₖ, …aₛ) significará R(aⱼ) ∩ R(aₖ) ∩…∩ R(aₛ) y representará al conjunto de n-combinaciones con repetición ilimitada, de a₁, a₂…, aₘ en las que se produce simultáneamente el rebosamiento de aⱼ , aₖ, …aₛ.

Es claro que hay m conjuntos de rebosamiento de 1 elemento, que serían R(a₁), R(a₂), …,R(aₘ) ; [m↓2] conjuntos de rebosamiento de 2 elementos, que serían R(a₁ , a₂), R(a₁ , a₃), …etc. hasta R(aₘ₋₁ , aₘ) … etc. así como, en general, [m↓k] conjuntos de rebosamiento de k elementos, donde k es cualquier entero tal que 1 ≤ k ≤ m.

Finalmente, sea R = R(a₁) ∪ R(a₂) ∪ …∪R(aₘ) (*)

R es el conjunto de todas las n-combinaciones de los m elementos

a₁ , a₂ , … , aₘ , con repetición ilimitada, en las cuales al menos uno de los elementos está "rebosado", es decir, se repite más veces de lo permitido.

En efecto, si alguna n-combinación de los m elementos

a₁ , a₂ , … , aₘ , con repetición ilimitada, presenta rebosamiento en uno (o más) de los elementos a₁ , a₂ , … , aₘ , pertenecerá al menos a una de las clases de combinaciones caracterizadas por hacer rebosar un elemento dado, o sea, al menos a uno de los conjuntos R(a₁), R(a₂), … R(aₘ) (y puede que a varios de ellos), luego pertenecerá a la unión de todos ellos.

Recíprocamente, si una n-combinación de los m elementos

a₁ , a₂ , … , aₘ , elegida entre todas aquellas n-combinaciones de tales elementos con repetición ilimitada, pertenece a la unión

R(a₁) ∪ R(a₂) ∪ …∪ R(aₘ) , pertenecerá a alguno de los conjuntos

R(a₁), R(a₂), … R(aₘ), digamos R(aₖ), y por tanto producirá rebosamiento en el elemento aₖ, de modo que esa combinación pertenecerá a R, esto es, al conjunto de todas las n-combinaciones de los m elementos a₁ , a₂ , … , aₘ , con repetición ilimitada, en las cuales al menos uno de sus elementos está "rebosado", es decir, se repite más veces de lo permitido, lo que demuestra la igualdad (*).

La pregunta pide encontrar una fórmula (convencional, no "artificial") que permita calcular el nº exacto de n-combinaciones de los m elementos a₁ , a₂ , … , aₘ , con repetición limitada, en las cuales no se produce rebosamiento de ninguno de sus elementos, de acuerdo a las limitaciones respectivas

a₁ , máximo de repeticiones = r₁ ;

a₂, máximo de repeticiones = r₂ ;

…………………………………………………

aₘ, máximo de repeticiones = rₘ ;

siendo cada uno de los rⱼ un entero tal que 1 ≤ rⱼ ≤ n, para todo j tal que 1 ≤ j ≤ m.

Pues bien: si de todas las n-combinaciones de los m elementos a₁ , a₂ , … , aₘ , con repetición ilimitada, suprimimos todas las que producen rebosamiento en algún elemento aⱼ, donde 1 ≤ j ≤ m, nos quedarán las combinaciones con repetición limitada que deseamos contar, sin que falte ninguna, y sin repetir ninguna de ellas; en efecto, una vez suprimidas las que producen algún rebosamiento, las que queden no lo producirán, luego serán combinaciones correctas, con repetición limitada dentro de los márgenes pedidos; ninguna puede estar repetida, puesto que lo habría estado antes entre la totalidad de las n-combinaciones de los m elementos a₁ , a₂ , … , aₘ , con repetición ilimitada, en contra de lo que suponemos: que partíamos de la lista de todas las n-combinaciones de los m elementos a₁ , a₂ , … , aₘ , con repetición ilimitada, sin repetir ninguna. Además, si buscamos una concreta entre las combinaciones con repetición limitada que deseamos contar, siendo una de las n-combinaciones de los m elementos a₁ , a₂ , … , aₘ, en la que se admite la repetición (aunque no se exige) estaría en la lista inicial de las n-combinaciones de los m elementos a₁ , a₂ , … , aₘ , con repetición ilimitada.

Por tanto, el número buscado, de n-combinaciones de los m elementos a₁ , a₂ , … , aₘ , con repetición limitada, mediante los límites respectivos r₁ , r₂ , … , rₘ,

será # L [ (a₁ ; r₁) , (a₂ ; r₂) … (aₘ ; rₘ) ] = (m+n-1↓n) - # R, es decir, será el nº total de combinaciones, exceptuando las que rebosan en algún elemento.

Como R es una unión, R = R(a₁) ∪ R(a₂) ∪ …∪R(aₘ) , podemos calcular su cardinal, #R, mediante la fórmula de inclusión-exclusión, también llamada principio de clasificación cruzada :

#(A ∪ B ∪ C ∪ … ∪ M ) = ∑#(A) - ∑#(A∩B) + ∑#(A∩B∩C) - …; luego :

#R = ∑ # R(a₁) - ∑ #R(a₁,a₂) + ∑ #R(a₁,a₂, a₃) - …

Pero #R(a₁) = CR (m , n - 1 - r₁), puesto que para rebosar en a₁ es necesario y suficiente elegir r₁ + 1 elementos a₁, y el resto hasta n completarlos tomando elementos cualesquiera en combinación con repetición de los elementos disponibles que son todos ellos a₁ , a₂ , … , aₘ.

Igualmente, #R(a₂) = CR (m , n - 1 - r₂), etc.

En general, # R(a₁, a₂, …aₖ) = CR (m , n - k - r₁ - r₂ -…- rₖ)

(el sumando -k proviene de sumar los -1 en - r₁ - 1 - r₂ - 1 - …- rₖ - 1), etc.

Así pues, si los rₖ fueran todos iguales, podría simplificarse mucho la fórmula final, pero en el caso contrario, que es el más general, habría que calcular

2ᵐ - 1 términos entre todos los sumatorios, que provienen de [m↓1] + [m↓2] + … + [m↓m] = 2ᵐ - 1.

Si hubiera m = 10 objetos, por ejemplo, deberíamos calcular 1023 términos entre todos los sumatorios, cálculo largo y pesado, pero fácilmente programable en un ordenador.

Fórmula final:

# L [ (a₁ ; r₁) , (a₂ ; r₂) … (aₘ ; rₘ) ] = [ (m+n-1)↓n) ] - ∑ CR (m , n - 1 - r₁) +

+ ∑CR (m , n - 2 - r₁ - r₂) - ∑CR (m , n - 3 - r₁ - r₂ - r₃) +…

+(-1)ᵏ ∑CR (m , n - k - r₁ -r₂ -…- rₖ) ± …

entendiendo, por los convenios establecidos, que si algún índice inferior es negativo, la correspondiente CR vale cero.

Ejemplo concreto:

Tenemos los objetos (o letras) a, b, c, d. Queremos calcular todas las combinaciones con repetición de estos elementos, tomados de 6 en 6, tales que, en cada una de ellas, a no se repita más de 3 veces, b no más de 6 veces,

c no más de 3 veces y d no más de 1 vez.

Tendremos m = 4 ; n = 6 ; r₁ = 3 ; r₂ = 6 ; r₃ = 3 ; r₄ = 1 ;

Luego vale, por ejemplo aabbcd ; y sirve, porque ninguna letra sobrepasa el máximo permitido; sirve también bbbbbb, pero no sirve abcccc, porque c ha sobrepasado su límite (solo podía repetirse hasta tres veces, pero no cuatro).

Para contar el nº total de las combinaciones válidas, tenemos:

#R(a₁) = CR (m , n - 1 - r₁) →

#R(a) = CR (4 , 6 - 1 - 3) = CR (4 , 2) = [5↓2] = 10.

#R(b) = CR (4 , 6 - 1 - 6) = 0

#R(c) = CR (4 , 6 - 1 - 3) = CR (4 , 2) = [5↓2] = 10.

#R(d) = CR (4 , 6 - 1 - 1) = CR (4 , 4) = [7↓4] = 35.

Recordemos que, en general,

# R(a₁, a₂, …aₖ) = CR (m , n - k - r₁ - r₂ -…- rₖ) →

#R(a, b) = CR (4 , 6 - 2 - 3 - 6) = 0.

#R(a, c) = CR (4 , 6 - 2 - 3 - 3) = 0.

#R(a, d) = CR (4 , 6 - 2 - 3 - 1) = CR (4 ,0) = 1.

#R(b, c) = CR (4 , 6 - 2 - 6 - 3) = 0.

#R(b, d) = CR (4 , 6 - 2 - 6 - 1) = 0.

#R(c, d) = CR (4 , 6 - 2 - 3 - 1) = CR (4 ,0) = 1.

#R(a, b, c) = CR (4 , 6 - 3 - 3 - 6 - 3) = 0.

#R(a, b, d) = CR (4 , 6 - 3 - 3 - 6 - 1) = 0.

#R(a, c, d) = CR (4 , 6 - 3 - 3 - 3 - 1) = 0.

#R(b, c, d) = CR (4 , 6 - 3 - 6 - 3 - 1) = 0.

#R(a, b, c, d) = CR (4 , 6 - 4 - 3 - 6 - 3 - 1) = 0.

Luego #R = (10+0+10+35) - (0+0+1+0+0+1) + (0+0+0+0) - 0 = 53.

De manera que

# L [ (a ; 3) , (b ; 6), (c ; 3), (d ; 1) ] = CR(4, 6) - 53 = [9↓6] - 53 = 84 – 53 = 31.

Por tanto:

Hay 31 combinaciones de a, b, c, d, tomados de seis en seis, admitiendo repeticiones siempre que a no se repita más de 3 veces, b no más de 6, c no más de 3 y d no más de 1 vez.

Corolario: Si tomásemos todos los rⱼ = n tendríamos todas las combinaciones con repetición ilimitada y su fórmula clásica,

CR (m, n) = [(m+n-1)↓n] puesto que todos los sumatorios serían nulos.