Número de soluciones integrales de$x_1+x_2+\cdots+x_k=n$ con condiciones$1\leq x_1<\cdots<x_k\leq m$ para algunos enteros$m,n,k$

Question

He sabido que el número de soluciones integrales positivas de$$x_1+\cdots+x_k = n$$ is $ \ binom {n-1} {k-1}$. Do we have any formula to count the number of solutions of the equation $$x_1+\cdots+x_k = n$$ with conditions $ 1 \ leq x_1 <\ cdots <x_k \ leq m$ for some integers $ m, n, k $?

Answer 1

[Demasiado largo el comentario] No es tan sencillo, por lo que yo sé. Usted puede comenzar por señalar que debemos tener cada uno de los $x_i \geq i$, por lo que (ajuste $y_i = x_i -i$) el problema es equivalente a contar soluciones para$\sum y_i = n - \binom{k+1}2$$0 \leq y_1 \leq y_2 \leq \dots \leq y_k \leq m-k$. Ese problema sin la $\leq m-k$ restricción es discutido en el Número de enteros soluciones si $x_1\leq x_2\leq x_3\leq \cdots\leq x_r\leq k$, y hay una recursividad puede utilizar. Para lidiar con el $\leq m-k$ restricción, restar fuera de los casos en donde la $y_k > m-k$; usted puede hacer esto por otro recursividad.

Answer 2

El uso de funciones de generación el problema se vuelve ligeramente más claro.

Si recordamos que la generación de la función para las particiones de $n$ en distintas partes $p_d(n)$ con tamaños de pieza $j=1$ $j=m$ es:

$$\prod_{j=1}^{m}(1+q^j)=\sum_{n}p_d(n)q^n\tag{1}$$

dado que el coeficiente de $q^n$ recibe una contribución de $1$ para cada una de las posibles distintas partición de $n$.

Entonces todo lo que necesita hacer es utilizar algunos enumerador ($x$ dicen) para contar el número de piezas. Este enumerador debe simplemente a que la etiqueta de cada parte del enumerador de la $q^j$ en nuestros productos. Por lo tanto la generación de la función para las particiones de $n$ a $k$ partes diferenciadas $p_d(n,k)$ con el tamaño de las piezas entre las $1$ $m$ es una versión modificada de $(1)$:

$$\prod_{j=1}^{m}(1+xq^j)=\sum_{n,k}p_d(n,k)x^kq^n\tag{2}$$

También es posible expresar el producto en términos de Gauss coeficientes binomiales como:

$$\prod_{j=1}^{m}(1+xq^j)=\sum_{n,k}p_d(n,k)x^kq^n=\sum_{k}{m\choose k }_qq^{\binom{k+1}{2}}x^k\tag{3}$$

por lo que se estaría buscando la $q^n$ coeficiente de ${m\choose k}_qq^{\binom{k+1}{2}}$.