Número de combinaciones con conjuntos de elementos idénticos

Question

Estaba tratando de escribir un programa python que toma una cadena e imprime todas las posibles combinaciones de caracteres de la misma y a su vez calcula el número de dichas combinaciones posibles de una cadena para verificar su corrección

Esto me hizo pensar en el siguiente problema: Dado N total de objetos de k tipos distintos tales que para i = 1 a k, r _i los objetos son del mismo tipo ¿cuál es el número total de combinaciones que contienen R ¿Objetos?

El problema de permutaciones que contiene todos los N objetos es mucho más sencillo e intuitivo, sin embargo, me interesa R < N .

He investigado un poco y sólo he podido encontrar este artículo discutiendo el problema, donde se sugirió que la respuesta sería la coeficiente de x R en la siguiente ecuación:

(1+x+x 2 +..+x r ₁ )(1+x+x 2 +..+x r ₂ ).....(1+x+x 2 +..+x r _k )

¿Es esta la única manera de resolver este problema? Además, ¿cómo se puede resolver el problema cuando se especifica que la longitud de la combinación es como máximo R en lugar de exactamente R?

Answer 1

Todos los métodos para resolver el problema son equivalentes a encontrar el coeficiente apropiado en el polinomio. Es posible, utilizando el álgebra elemental, construir una fórmula con no más de $2^k$ (como se muestra a continuación), pero multiplicar simplemente el polinomio original suele ser más fácil y menos propenso a errores.

El polinomio dado es $$\prod_{i=1}^k1+x+x^2+\cdots+x^{r_i}=\prod_{i=1}^k\frac{1-x^{r_i+1}}{1-x}=(1-x)^{-k}\prod_{i=1}^k1-x^{r_i+1}$$

Ahora, $$(1-x)^{-k}=\sum_{i=0}^\infty\binom{k-1+i}ix^i$$

y $$\prod_{i=1}^k1-x^{r_i+1}=\sum_{S\subset\{r_1\cdots r_k\}}(-1)^{|S|}x^{\sum_{\alpha\in S}(\alpha+1)}$$ lo que significa $1$ , menos todo $x^{r_i+1}$ tomadas de una en una, además de todas $x^{r_i+r_j+2}$ tomados de dos en dos, menos todos $x^{r_i+r_j+r_k+3}$ tomados de tres en tres, etc.

Poniendo todo junto, dejemos que $U_n$ sea el subconjunto de todos los subconjuntos $S$ de $\{r_1+1,r_2+1,\cdots r_k+1\}$ tal que la suma $s(S)=\sum_{\alpha\in S}\alpha$ es siempre menor o igual que $n$ . Entonces la fórmula es $$\sum_{S\in U_n}(-1)^{|S|}\binom{k-1+n-s(S)}{n-s(S)}$$ que es equivalente a la dada por san .

En el ejemplo de $r_1=2,\ r_2=1,\ r_3=2,\ n=3$ obtenemos $U_3=\{\emptyset,\{3\},\{2\},\{3\}\}$ y $$\binom53-\binom20-\binom31-\binom20=10-1-3-1=5$$ como se esperaba.

En lugar de todo eso, podríamos multiplicarnos en un retablo. Por ejemplo, tomar el $r$ -valores $5,3,2$ :

$$\begin{array}{ccccccccccc}1&1&1&1&1&1\\1&2&3&4&4&4&3&2&1\\1&3&6&9&11&12&11&9&6&3&1\end{array}$$ La primera fila $(A_{1,j})$ contiene $r_1+1$ los. Para $i>1$ El $i$ se forma sumando cada grupo de $r_i+1$ números adyacentes en la fila anterior: $$A_{i,j}=\sum_{k=0}^{r_i}A_{i-1,j-k}$$ asumiendo que todo lo que está fuera del rango es cero. Por ejemplo, la tercera fila se forma como $$0+0+1,\ 0+1+2,\ 1+2+3,\ 2+3+4,\ 3+4+4,\ 4+4+4,\ldots$$

Inmediatamente podemos leer que hay $11$ combinaciones de $6$ objetos, etc. En Python se podría escribir algo como newrow = [sum(row[max(0,i-r):i+1]) for i in range(len(row)+r)]

Answer 2

Creo que la presentación como coeficientes de ese polinomio es la respuesta más sencilla posible. Una presentación más geométrica es como el número de puntos enteros de la intersección del hiperplano $\mathcal{P}: x_1+\dots+x_k=R$ en $\Bbb{R}^k$ con el paralelepípedo $I_1\times\dots\times I_k$ , donde $I_i=[0,r_i]$ . Es decir, $$ \# \ \Bbb{N}_0^k\cap (I_1\times\dots\times I_k) \cap \mathcal{P} $$

$\textbf{EDIT:}$

A partir de esta interpretación geométrica se puede obtener una expresión combinatoria para el número, que llamaremos $N(r_0,\dots,r_k,R)$ . Para ello, es conveniente considerar $k+1$ conjuntos, con $r_0,\dots,r_k$ respectivamente (hace que la fórmula tenga un aspecto más agradable). A continuación, defina $$ F=\{J\subset \{0,\dots,k\}, \text{such that } S_J:=\sum_{i\in J}r_i\le R-|J|\}, $$ y tenemos $$ N(r_0,\dots,r_k,R)=\sum_{J\in F}(-1)^{|J|}\binom{R-S_J-|J|+k}{k} $$

Se puede verificar la fórmula, por ejemplo, en el caso de que para todo $i$ tenemos $r_i\ge R$ donde da el número correcto $\binom{R+k}{k}$ (ya que $\emptyset\in F$ y $S_{\emptyset}=0$ ); y también en el caso de que sólo una $r_i<R$ (supongamos, por ejemplo, que $r_0$ ), donde da el número correcto $\binom{R+k}{k}-\binom{R-r_0-1+k}{k}$ .

La idea de la prueba es que se empieza con un $k$ -simplemente con $\binom{R+k}{k}$ puntos enteros y cada $r_i<R$ recorta una parte más pequeña $k$ -simplex (de longitud lateral $R-r_0-1$ ), que hay que restar, pero si $r_i+r_j\le R-2$ entonces hay que sumar los puntos en un $k$ -simplex (con longitud lateral $R-(r_i+r_j)-2$ ), que has restado dos veces y continúas con el mismo método para todos los $J\in F$ .

Con respecto a la pregunta "También cómo se resolvería el problema cuando se especifica que la longitud de la combinación es como máximo R en lugar de exactamente R", observe que $$ \sum_{r=0}^{R}N(r_0,\dots,r_k,r)=N(r_0,\dots,r_k,R,R). $$

Answer 3

Empiezas el post mencionando cadena es decir palabras que formalmente se consideran distintos también según el orden de sus caracteres .
Entonces, usted plantea la pregunta "Dados N objetos totales de k tipos distintos tales que para i = 1 a k, ri objetos son del mismo tipo, ¿cuál es el número total de combinaciones que contienen R objetos?" y citando la respuesta en la referencia que has encontrado, parece que en realidad estás interesado en el número de subconjuntos con repetición limitada, donde el orden de los elementos no importa, por ejemplo $\{ACAB\}=\{AABC\}$ .

Estoy desarrollando mi respuesta de acuerdo con este último supuesto.

Si el $r_i$ eran todos iguales a $r$ entonces la solución vendría dada por $N_b(R,r,k)$ donde $$ \bbox[lightyellow] { N_{\,b} (s,r,m) = \text{No}\text{. of solutions to}\;\left\{ \begin{gathered} 0 \leqslant \text{integer }x_{\,j} \leqslant r \hfill \\ x_{\,1} + x_{\,2} + \cdots + x_{\,m} = s \hfill \\ \end{gathered} \right. } \tag{1} $$ y $$ \bbox[lightyellow] { N_b (s,r,m)\quad \left| {\;0 \leqslant \text{integers }s,m,r} \right.\quad = \sum\limits_{\left( {0\, \leqslant } \right)\,\,k\,\,\left( { \leqslant \,\frac{s} {r}\, \leqslant \,m} \right)} {\left( { - 1} \right)^k \left( \begin{gathered} m \hfill \\ k \hfill \\ \end{gathered} \right)\left( \begin{gathered} s + m - 1 - k\left( {r + 1} \right) \\ s - k\left( {r + 1} \right) \\ \end{gathered} \right)} } \tag{2} $$ cuya z-Tranform es de hecho $$ \bbox[lightyellow] { F_b (x,r,m) = \sum\limits_{0\,\, \leqslant \,\,s\,\,\left( { \leqslant \,\,r\,m} \right)} {N_b (s,r,m)\;x^{\,s} } = \left( {1 + x + \cdots + x^{\,r} } \right)^m = \left( {\frac{{1 - x^{\,r + 1} }} {{1 - x}}} \right)^m } \tag{3} $$ como se explica en este otro post .

Si el $r_i$ asumen sólo dos valores $r_1$ y $r_2$ y hay $k_1$ y $k_2$ conjuntos distintos en cada clase, entonces $$ \bbox[lightyellow] { F_b (x,r_{\,1} ,r_{\,2} ,k_{\,1} ,k_{\,2} ) = \left( {1 + x + \cdots + x^{\,r_{\,1} } } \right)^{\,k_{\,1} } \left( {1 + x + \cdots + x^{\,r_{\,2} } } \right)^{\,k_{\,2} } } $$ y se pueden obtener los coeficientes operando la convolución en $s=R$ de los dos respectivos $N_b$ 's.
El mismo esquema si el $r_i$ se pueden agrupar en unos "pocos" valores diferentes.

Si en cambio hay "muchos" $r_i$ 's, y bastante disperso en valor, entonces desde el punto de vista computacional de vista es mejor y obtener los coeficientes de la convolución de los $k$ cadenas binarias $$ \bbox[lightyellow] { \left[ {0 \le n \le r_{\,i} } \right] } $$ donde $[P]$ es el Soporte Iverson $$ \bbox[lightyellow] { \left[ P \right] = \left\{ {\begin{array}{*{20}c} 1 & {P = TRUE} \\ 0 & {P = FALSE} \\ \end{array} } \right. } $$

No conozco una fórmula cerrada para ello.

Sin embargo, dependiendo de la aplicación real, de la distribución del $k$ y $r$ etc. las cadenas binarias pueden considerarse discretas (en el límite $\to$ continua) secuencias, es decir, como pulsos cuadrados unitarios de duración $r_i$ (o $r_{i}+1$ dependiendo de la forma en que el $0$ -ésima).
Así que pueden considerarse como la suma de dos funciones Heaviside, o la integral de dos funciones Delta, y ser manipuladas mediante la transformada de Fourier o de Laplace. Eso ayuda a obtener algunas expansiones asintóticas, y en todo caso la transformada inversa del producto de los términos individuales proporciona una fórmula global .

Por último, para los grandes $k$ el problema se aproximará al de la suma de muchas variables casuales, uniformemente distribuidas en el intervalo $[0,r_i]$ y por lo tanto se puede manejar con los instrumentos de la Teoría de la Probabilidad.