¿Cómo puedo contar soluciones a $x_1 + \ldots + x_n = N$?

Question

Estoy interesado en cómo muchos entero no negativo, las soluciones que hay son:

$$x_1 + \ldots + x_N = B$$

donde al menos $K$ de las variables $x_1, \ldots , x_N \geq C$

Por ejemplo, cuando: $B = 5, N = 3, K = 2, C = 2$

Quiero contar las soluciones para:

$$x_1 + x_2 + x_3 = 5$$

donde al menos $2$ de las variables se $\geq 2$.

He encontrado el número total de candidatos soluciones mediante el uso de la $\binom{B+N-1}{B} = 21$

Sin embargo, sólo $9$ de ellos tienen dos variables $\geq 2$.

\begin{align*} 2+0+3& =5\\ 2+1+2& =5\\ 3+0+2& =5\\ 1+2+2& =5\\ 3+2+0& =5\\ 0+2+3& =5\\ 0+3+2& =5\\ 2+3+0& =5\\ 2+2+1& =5 \end{align*}

Siento que hay una conexión a la Asociada a los números de Stirling del segundo tipo. Pero no puedo poner :(

EDITAR:

Aquí está mi código para enumerar todos ellos para contar el número de maneras de seleccionar B elementos de un conjunto de N (de manera uniforme con reemplazo), que tiene al menos C copias de K elementos - también se muestra el resultado de esta pregunta que estoy haciendo aquí es el núcleo de la pieza. Obviamente no se pueden ejecutar para valores muy grandes de los parámetros - por eso estoy aquí :) el Código está aquí

Aquí hay otro ejemplo para B = 6, N = 3, C = 2 y K = 2 hay 16 soluciones:

\begin{align*} 0+2+4& = 6\\ 0+3+3& = 6\\ 0+4+2& = 6\\ 1+2+3& = 6\\ 1+3+2& = 6\\ 2+0+4& = 6\\ 2+1+3& = 6\\ 2+2+2& = 6\\ 2+3+1& = 6\\ 2+4+0& = 6\\ 3+0+3& = 6\\ 3+1+2& = 6\\ 3+2+1& = 6\\ 3+3+0& = 6\\ 4+0+2& = 6\\ 4+2+0& = 6\\ \end{align*}

Hay un número de diferentes soluciones correctas a continuación. No sé que aceptar.

Answer 1

Sin pérdida de generalidad, consideremos $x_1,x_2,\ldots,x_k \geq C$.

A continuación, vamos a

$$y_i = \begin{cases}x_i - C &i\leq k\\ x_i & i > k \end{cases}$$

La resolución de

$$\left\{\begin{array}[lll] xx_1 + x_2 + \ldots + x_n &=& N\\ x_i \geq 0& & \\ x_1,x_2,\ldots,x_k& \geq & C\end{array}\right.$$ es equivalente a la resolución de $$\left\{\begin{array}[lll] yy_1 + y_2 + \ldots + y_n &=& N-kC\\ y_i \geq 0& &\end{array}\right.$$ The number of solutions excluding permutations is the number of partitions of $N-kC$ into $m$ integers where $m \leq$n.

Para cada una de estas soluciones, la adición de $C$ $k$de ellos daría una solución del problema original. Hay $n\choose k$ formas de hacer así, pero estamos overcounting algunas soluciones si no se $i,j$ tal que $y_i = y_j$ o si $y_i + C = y_j$. Para cada una de estas soluciones que tenemos en la mayoría de los $n!$ soluciones distintas (incluyendo permutaciones), de nuevo estamos overcounting algunos si se $i,j$ tal que $y_i = y_j$ o si $y_i + C = y_j$. Esto nos da un poco cerca de límite superior en la cantidad de soluciones:

$${n\choose k} n!\sum_{m=1}^n P_m(N-kC)$$

Answer 2

Un enfoque a la medida por la analítica de la combinatoria. El coeficiente de $x^B$ en

$$ \frac{1}{(1-x)^N} = \left(1+x+x^2+x^3+\ldots\right)^N $$ obviamente, se cuenta el número de maneras de representar la $B$ como una suma de $N$ enteros no negativos. Por las estrellas y las barras, o por el (negativo) teorema del binomio, el número es $\binom{N+B-1}{N-1}$. Podemos usar una variable adicional para marcar los términos con exponente $\geq C$, y considerar la posibilidad de: $$ g(z,x) = \left(1+x+x^2+\ldots+x^{C-1}+ z x^{C}+z x^{C+1}+ z x^{C+2}+\ldots\right)^N $$ que es: $$ g(z,x) = \left(\frac{1-x^C}{1-x}+z\cdot\frac{x^C}{1-x}\right)^N = \frac{(1+(z-1) x^C)^N}{(1-x)^N}.$$ Ahora el coeficiente de $x^B$ $g(z,x)$ es un polinomio en la $z$ variable, $h_B(z)$, y estamos interesados en un resumen de la monomials de $h_B(z)$ cuyo grado es $\geq K$. De esa suma se evaluó en $z=1$ da la respuesta a nuestro problema. Sospecho, sin embargo, no es agradable cerrado fórmula para resumir el proceso, ya que incluso el cálculo de $h_B(z)$ implica una convolución. Se le multa con una representación integral de la respuesta? Eso no es difícil de lograr a través de Cauchy de la integral de la fórmula.

Si $B=5,N=3, C=2$$K=2$,$h_B(z)=12z+\color{red}{9}z^2$, por lo tanto la respuesta es $\color{red}{9}$ comprobado. La forma general de la respuesta está dada por:

$$\begin{eqnarray*} [x^B]\sum_{D\geq K}[z^D]\frac{\left((1-x^C)+z x^C\right)^N}{(1-x)^N}&=&[x^B]\frac{1}{(1-x)^N}\sum_{D\geq K}\binom{N}{D}x^{CD}(1-x^C)^{N-D}\\&=&\sum_{D\geq K}\binom{N}{D}[x^{B-CD}]\frac{(1-x^C)^{N-D}}{(1-x)^N}\\&=&\color{red}{\sum_{D\geq K}\binom{N}{D}\sum_{h=0}^{N-D}\binom{N-D}{h}(-1)^h\binom{N+B-CD-Ch-1}{N-1}}, \end{eqnarray*}$$

bastante fea.

Answer 3

Usted podría mover a nuevas variables $x_i' = x_i - C \ge 0$ para las variables con el valor mínimo $C$. Entonces la ecuación se transforma a $$ x'_1 + \ldots x'_K + x_{K+1} + \ldots x_N = B - K \, C $$ suponiendo WLOG GRUMBL MUMBL que esas variables son los primeros a$K$.

Este es un problema de la forma $$ n_1 + \ldots + n_N = n \quad (n_i \ge 0) \quad (*) $$ que está relacionado con composiciones a partir de la combinatoria. Una composición de $n$ es una manera de escribir $n$ como suma de enteros $n_i \ge 1$. Necesitamos débil composición de $n$, lo que permite a los términos de $n_i \ge 0$, pero sólo aquellos que han $N$ términos. El número de composiciones de $n$ a $N$ partes es $\binom{n-1}{N-1}$, el número de la debilidad de las composiciones de $n$ a $N$ partes de la siguiente manera de mirar el número de composiciones de $n+N$ a $N$ partes (y restando $1$ para cada una de las $N$ partes en ambos lados), por lo que la ecuación de $(*)$ ha $$ \binom{n+N-1}{N-1} = \binom{B-K\,C+N-1}{N-1} $$ soluciones.

Su ejemplo se convierte en $$ x'_1 + x'_2 + x_3 = 5-2\cdot 2 = 1 $$ y debe tener $\binom{1+3-1}{3-1}=\binom{3}{2}=3!/(2!1!)=3$ soluciones. Nos encontramos $$ (x'_1, x'_2, x_3) \(x_1, x_2, x_3) \\ (1,0,0) \a (3,2,0) \\ (0,1,0) \a (2,3,0) \\ (0,0,1) \a (2,2,1) $$ La solución encontrada en $x'_i$ debe luego ser transformada a través de $x_i = x'_i + C$, ver el lado derecho de arriba.

Actualización: El asumido por encima de las limitaciones que estaban en posiciones fijas y adjunta las limitaciones de la $x_i \ge C$ a las variables$1$$K$. Debe quedar claro que si las restricciones se asignan a un subconjunto de variables indexadas por $I = \{ I_1, \ldots, I_K \} \subset \{1, \ldots, N \}$ terminamos con las mismas soluciones, aunque permutated, junto a la permutación de los índices.

E. g. para el ejemplo tenemos: $$ (x_1, x'_2, x_3') \(x_1, x_2, x_3) \\ (1,0,0) \a (1,2,2) \\ (0,1,0) \a (0,3,2) \\ (0,0,1) \a (0,2,3) $$ y $$ (x_1', x_2, x_3') \(x_1, x_2, x_3) \\ (1,0,0) \a (3,0,2) \\ (0,1,0) \a (2,1,2) \\ (0,0,1) \a (2,0,3 el) $$ Estos son todos los $9$ soluciones.

Lo que tenemos aquí son combinaciones, como sólo estamos interesados en el subconjunto elegido, no en qué orden los elementos que fueron elegidos. Hay $\binom{N}{K}$ $K$-combinaciones de un conjunto de $N$ elementos.

Nota: Esta parte de las necesidades de $C \ge 1$, de lo contrario, la resultante de las tuplas no son distintas. No podría estar más condiciones que ver, para justificar este factor, ver los comentarios.

Resultado:

No debe ser $$ \binom{N}{K} \binom{B-K\,C +N-1}{N-1} $$ soluciones para el problema original. Precaución: Esto podría degradar a una cota superior, ver los comentarios.

Answer 4

Deje $A_i$ el conjunto de soluciones en números enteros no negativos a$x_1+\cdots+x_n=B$$x_i\ge C$$1\le i\le n$,

y deje $T_l=\sum\big|A_{i_1}\cap\cdots\cap A_{i_l}\big|$, donde la suma se toma sobre todos los $l$-subconjuntos de a$\{1,\cdots,n\}$$1\le l\le n$.

Mediante la Inclusión-Exclusión, el número de elementos en al menos k de $A_1,\cdots,A_n$ está dado por

$\displaystyle\sum_{i=k}^n(-1)^{i-k}\binom{i-1}{k-1}T_i=\color{blue}{\sum_{i=k}^n(-1)^{i-k}\binom{i-1}{k-1}\binom{n}{i}\binom{B-Ci+n-1}{n-1}}$

desde $T_i$ es la suma de $\binom{n}{i}$ términos, cada uno de los cuales tiene el valor de $\binom{B-Ci+n-1}{n-1}$.

---

Véase también la respuesta http://math.stackexchange.com/a/362516 relacionados con la versión de Inclusión-Exclusión.

---

Aquí un par de ejemplos, que han sido verificados por considerar los casos:

$\textbf{1)}$ $B=6, n=3, C=2, k=2$:

$\displaystyle\sum_{i=2}^3(-1)^{i-2}\binom{i-1}{1}\binom{3}{i}\binom{8-2i}{2}=\binom{1}{1}\binom{3}{2}\binom{4}{2}-\binom{2}{1}\binom{3}{3}\binom{2}{2}=18-2=\color{blue}{16}$

$\textbf{2)}$ $B=12, n=5, C=4, k=2$:

$\displaystyle\sum_{i=2}^5(-1)^{i-2}\binom{i-1}{1}\binom{5}{i}\binom{16-4i}{4}=\binom{1}{1}\binom{5}{2}\binom{8}{4}-\binom{2}{1}\binom{5}{3}\binom{4}{4}=700-20=\color{blue}{680}$

$\textbf{3)}$ $B=18, n=6, C=3, k=4$:

$\displaystyle\sum_{i=4}^6(-1)^{i-4}\binom{i-1}{3}\binom{6}{i}\binom{23-3i}{5}=\binom{3}{3}\binom{6}{4}\binom{11}{5}-\binom{4}{3}\binom{6}{5}\binom{8}{5}+\binom{5}{3}\binom{6}{6}\binom{5}{5}=\color{blue}{5,596}$