Estrellas y barras ordenadas

Question

Encuentre el número de ordenados $8$ -partidas de enteros no negativos $x_0 < x_1 < x_2 < \cdots < x_7$ tal que $\sum_{i=0}^{7} x_i = 99$

Es evidente que la pregunta anterior no puede responderse con las clásicas estrellas y barras, y la sustitución $y_i = x_i - i$ tampoco parece ayudar. No veo cómo progresar.

Answer 1

Mal funcionamiento del cerebro. Está buscando un división en diferentes partes con 7 partes del número entero 99

Answer 2

Podemos obtenerla mediante la función generadora de particiones (como sugiere vonbrand), que viene dada por

$$ G(x)=\frac{x^{28}}{{\left(1-x\right)} {\left(1-x^{2}\right)} {\left(1-x^{3}\right)}{\left(1-x^{4}\right)}{\left(1-x^{5}\right)}{\left(1-x^{6}\right)}{\left(1-x^{7}\right)} {\left(1-x^{8}\right)}} $$

y la respuesta requerida es $$[x^{99}]G(x)=207945$$

Answer 3

Dejemos que $F(m,k,b)$ sea el número de los estrictamente ordenados $k$ -tuplas $0 \leq x_1 < \ldots < x_k \leq b$ con $\sum_{i=1}^k x_k = m$ .

Para $b < k-1$ estos requisitos son contradictorios. La suma mínima de un $k$ -tupla es $0 + 1 + \ldots + (k-1)$ que es $\frac{k(k-1)}{2}$ . La suma máxima de un $k$ -tupla es $b + (b-1) + \ldots + (b-k+1)$ que es $\frac{b(b+1) - (b-k)(b-k+1)}{2}$ .

Para $m = \frac{k(k-1)}{2}$ y $b \geq k-1$ , hay exactamente el $k$ -tupla $(0,1,\ldots,k-1)$ .

De ello se desprende que $$\begin{eqnarray} (1)\quad& F(m,k,b) &=& 0 \quad \text{if } b < k-1 \text{ or } m < \tfrac{k(k-1)}{2} \text{ or } m > \tfrac{b(b+1) - (b-k)(b-k+1)}{2} \\ (2)\quad& F(m,k,b) &=& 1 \quad \text{if } b \geq m \text{ and } k=1 \\ (3)\quad& F(m,k,b) &=& 1 \quad \text{if } b \geq k-1 \text{ and } m = \tfrac{k(k-1)}{2} \text{.} \end{eqnarray} $$

Elegir un fijo $x_k \in [0,b]$ significa que $x_1,\ldots,x_{k-1}$ tiene que ser inferior a $x_k$ es decir, limitado por $b-1$ y que su suma tiene que ser $m-x_k$ , lo que da como resultado $$ F(m,k,b) = \sum_{i=0}^b F(m - i, k-1, i-1) \text{.} $$ (El rango de la suma para $i$ puede reducirse aún más, pero utilizando las condiciones en las que $F(m-i,k-1,i-1)$ es cero)

Ahora habría que ver si esta recursión se puede llevar a una forma explícita.