Número total de soluciones para una ecuación dada con un valor mínimo $0$ y un valor máximo de $m$

Question

Cuál es el número total de soluciones para la siguiente ecuación

$$x_1+x_2+x_3+.....+x_k=n$$

con un valor máximo de $m$ , donde $0\leq x \leq m$ . Ninguna de las dos variables debe contener un valor máximo $m$ .

Ejemplo: $x_1+x_2+x_3=3$ con un valor máximo $2$ ( $n=3$ , $m=2$ , $k=3$ )

El total de formas posibles es $7$ : $$\{1,1,1\}, \{0,1,2\}, \{0,2,1\}, \{1,0,2\}, \{1,2,0\}, \{2,0,1\}, \{2,1,0\}$$

Lo he hecho manualmente pero no se como llegar a una fórmula. He estado luchando durante la última semana. ¿Hay alguna fórmula?

Answer 1

Pista: Puedes dividir las soluciones en dos grupos. Uno, las que alcanzan el valor máximo ( $x_i = m$ para algunos $i$ y $x_j < m$ para todos $j\ne i$ ); la otra, en la que $x_i < m$ para todos $i$ .

Luego se puede contar la cardinalidad de cada conjunto mirando en esta pregunta .

En concreto, la adaptación de la pdf (fórmula E, página 441), obtenemos que el número de composiciones de $k$ números $0\le x_i<m$ con $\sum x_i = n$ viene dada por

$$F(n,m,k)= \sum_{j=0}^{\lfloor n/m \rfloor} (-1)^j {k \choose j}{n+k - j \, m -1 \choose k-1}$$

Entonces tenemos

$$C(n,m,k) = k \, F(n-m,m,k-1) + F(n,m,k) $$

En su ejemplo:

$$C(3,2,3) = 3 \, F(1,2,2) + F(3,2,3) = 3 \times 2 + 1 = 7$$