Función generadora para contar composiciones de $n$ con partes de un conjunto determinado

Question

Me tocó la siguiente pregunta:

$A_n$ está marcado para ser el número de todas las secuencias de un subconjunto de las naturales a $\{1,2,3,4,5,6\}$ tal que su suma es $n$ (un número natural) ** lo que significa que el orden importa

Por ejemplo: para $A_5$ alguna parte de las secuencias son <1,1,1,1> , <1,2,2> , <2,2,1>

Me han pedido que encuentre la función generadora que se adapte a este problema, y lo que quiero decir con esto es encontrar la función $f$ tal que $f$ = $A_0$ + $A_1x$ + $A_2x^2$ +...

Me gustaría que me ayudaran con esta pregunta, ¡muchas gracias!

p.d: $A_0=0$

Answer 1

Observamos: $$\frac{x}{1-x}=x^1+x^2+x^3+\ldots$$ lleva como exponentes las posibles soluciones $1,2,3,\ldots$ de una $x_i$ en $$x_1+x_2+x_3+\ldots+x_k=n\qquad k\geq 1, n\geq k$$ Por lo tanto, el número de composiciones de $n$ con $k$ variables $x_1,x_2,\ldots,x_k$ es el coeficiente de $x^n$ de $$\left(\frac{x}{1-x}\right)^k$$

Como queremos restringir las soluciones a elementos de $\{1,2,3,4,5,6\}$ tomamos \begin {align*} \frac {x-x^7}{1-x}=x^1+x^2+x^3+x^4+x^5+x^6 \end {align*}

Dado que el número de variables es al menos $1$ hasta $n$ para $A_n$ obtenemos como función generadora \begin {align*} f(x)&= \sum_ {n=1}^ \infty A_nx^n \\ &= \sum_ {n=1}^ \infty \left ( \frac {x-x^7}{1-x} \right )^n \\ &= \frac {x-x^7}{1-x} \cdot\frac {1}{1- \frac {x-x^7}{1-x}} \\ &=x+2x^2+4x^3+8x^4+ \color {blue}{16}x^5+32x^6+63x^7+ \cdots \end {align*}

por lo que la última línea se obtuvo con la ayuda de Wolfram Alpha.

$$ $$

Ejemplo: Encontramos por ejemplo $A_5=16$ que representa el $\color{blue}{16}$ composiciones de $5$ \begin {align*} &<1,1,1,1,1,1>, \\ &<1,1,1,2>,<1,1,2,1>,<1,2,1,1>,<2,1,1,1>, \\ &<1,1,3>,<1,3,1>,<3,1,1> \\ &<1,2,2>,<2,1,2>,<2,2,1> \\ &<1,4>,<4,1> \\ &<2,3>,<3,2> \\ &<5> \end {align*}