Encontrar el número de tuplas de $0, 1$ y $3$

Question

Cómo puedo encontrar el número de tuplas $(k_1, k_2, ...,k_{26})$ tal que cada $k_i$ es igual a % o $0, 1$ $3$y $k_1 + k_2 + ... + k_{26} = 15$.

Puedo reducir este problema al encontrar el coeficiente de $x^{15}$ $(1 + x + x^3)^{26}$ de la expresión, pero lo hago ahora no cualquier simple forma.

Answer 1

Podemos sucesivamente utilizar el teorema del binomio para extraer el coeficiente. Es conveniente utilizar el coeficiente de operador $[x^k]$ para denotar el coeficiente de $x^k$ en un polinomio.

Obtenemos $$\begin{align*} [x^{15}](1 + x + x^3)^{26}&=[x^{15}]\sum_{k=0}^{26}\binom{26}{k}x^{3k}(1+x)^{26-k}\\ &=\sum_{k=0}^{5}\binom{26}{k}[x^{15-3k}](1+x)^{26-k}\tag{1}\\ &=\sum_{k=0}^{5}\binom{26}{k}[x^{15-3k}]\sum_{j=0}^{26-k}\binom{26-k}{j}x^{j}\\ &=\sum_{k=0}^{5}\binom{26}{k}\binom{26-k}{15-3k}\tag{2}\\ &=853423740 \end{align*}$$

Comentario:

• En (1) utilizamos la linealidad del coeficiente de operador y la regla de $$[x^{n-k}]P(x)=[x^n]x^kP(x)$$ También nos hemos fijado en el límite superior del índice de $k$$5$, ya que el exponente de a $x^{15-3k}$ es no negativo.

• En (2) seleccionamos el sumando con $j=15-3k$ para obtener el coeficiente de $x^{15-3k}$.

Answer 2

Bueno, por lo que tiene opciones: digamos que usted tiene $a$ 1 $b$ 3s, y el resto son ceros. Así que usted tiene que $a+3b = 15$. Esto le da la siguiente colección de $(a,b)$ parejas de soluciones: $$(15,0), (12, 1), (9,2), (6,3), (3,4), (0,5),$$ o, equivalentemente, $(15-3k, k)$$0 \leq k \leq 5$.

Ahora, a partir de un par de $(a,b)$ usted obtener soluciones de la ecuación original por la elección, a partir del 26 de posiciones, $a$ lugares para poner un 1, y del resto de las $26-a$ posiciones, $b$ lugares para poner una $0$. En otras palabras, usted tiene la contribución de ${26 \choose a}{26-a \choose b}$ a partir de los par $(a,b)$. Esto da un total de $$\sum_{k=0}^{5} {26 \choose 15 -3k}{26-3k \choose k}.$$ Esto da el mismo resultado que en la respuesta de Markus.