Combinatoria: Función generatriz relacionados con composiciones de un número

Question

Mi objetivo es encontrar los coeficientes de la generación de la función para la siguiente situación:

El número de $f(n)$ es la suma sobre todas las composiciones de $n$ a $3$ partes del producto de esas partes. Por ejemplo, si $n=5$, puede ser escrito como suma de tres números enteros en seis formas: $$1+3+1, 3+1+1, 1+1+3, 2+2+1, 2+1+2, 1+2+2.$$

Tomando la suma de los productos de estos grupos, se obtiene un número de $f(5)$: $$3+3+3+4+4+4 = 21.$$

Necesito encontrar una fórmula para estos números. He resuelto algunos por la fuerza bruta y he determinado que son los números en la 6 de la diagonal del triángulo de Pascal, pero no quiero poner esto como una explicación. Hay una manera fácil de hacer esto con la generación de funciones? Supongo que es lo que se espera de mí.

Cualquier visión se agradece.

Muchas gracias!

Edit: El número de piezas es siempre tres, y sí, estos son composiciones, no particiones. Pido disculpas por cualquier confusión.

Answer 1

Hint: $(2\cdot 2\cdot 1)\cdot x^{2+2+1} = (2x^2)(2x^2)(x)$. Así que ¿qué podría la función generar aspecto?

Información: Si $a_n$ es tu cuenta, entonces podemos escribir:

$$\sum a_nx^n = (x+2x^2+3x^3\dots + nx^n+\dots)^3$$

¿Conoces una forma cerrada para $\sum nx^n$?

Answer 2

SUGERENCIA: Usted está interesado en

$$\large\sum_{a+b+c=n\atop{a,b,c\ge1}}abc\;,$$

la suma de todos los productos de tres enteros positivos cuya suma es $n$. Que se parece mucho a la de convolución, o el tipo de coeficiente por el que se obtendría en el producto de Cauchy de tres centrales de la serie. Y $a,b$, e $c$ parecen ser tratados de forma idéntica, así que es probable que el cubo de un poder único de la serie. ¿Qué serie?

Por el camino, usted puede hacerlo sin generar funciones. Supongamos a continuación que $a,b$, e $c$ siempre, al menos,$1$.

$$\begin{align*} \sum_{a+b+c=n}abc&=\sum_{a+b\le n}ab(n-ab)\\ &=n\sum_{a+b\le n}ab-\sum_{a+b\le n}a^2b^2\\ &=n\sum_{k=2}^n\sum_{a=1}^{k-1}a(k-a)-\sum_{k=2}^n\sum_{a=1}^{k-1}a^2(k-a)^2\\ &=n\sum_{k=2}^n\left(\frac{k^2(k-1)}2-\frac{k(k^2-1)}6\right)-\dots \end{align*}$$

Yo shan no terminar este pequeño monstruo, ya que es la manera difícil, pero claramente se puede acabar.

Answer 3

El número de composiciones de $n$ en tres partes se da en ${n-1 \choose 3-1}$ que puede ser demostrado por un argumento de estrellas y barras . Piensa en $n$ estrellas en una fila. Es necesario poner dos barras en los espacios de $n-1$ entre ellos para hacer su composición. Hay ${n-1 \choose 2}$ formas de seleccionar las dos posiciones de las barras.