División y funciones generadoras

Question

Estoy tratando de resolver $$P_k(x) = \sum_{n} p_k(n)x^n$$, lo cual debería dar el número de formas de particionar un conjunto de tamaño $n$ en exactamente $k$ partes. Hasta ahora, he intentado resolver esto simplemente escribiendo $$\frac{1}{(1-x)(1-x^2)...(1-x^k)}$$ ya que esto debería dar el número de formas de particionar un conjunto de tamaño $n$ en $k \geq 1$ partes.

¿Cómo debería agregar la parte de "exactamente $k$ particiones" del problema a esta pregunta? ¡Gracias!

Answer 1

La función generadora $P^{(\leq k)}(x)$ para el número de particiones que consiste en partes cada una $\leq k$ es \begin{align*} P^{(\leq k)}(x)&=(1+x+x^2+x^3+\cdots)\\ &\qquad\cdot(1+x^2+x^4+x^6+\cdots)\\ &\qquad\cdot(1+x^3+x^6+x^9+\cdots)\\ &\qquad\qquad\qquad\cdots\\ &\qquad\cdot(1+x^k+x^{2k}+x^{3k}+\cdots)\\ &=\frac{1}{(1-x)(1-x^2)(1-x^3)\cdots(1-x^k)} \end{align*}

Nota: Un aspecto interesante es que el número de particiones con partes cada una $\leq k$ es el mismo que el número de particiones con a lo sumo $k$ partes.

Si usamos [diagramas de Ferrer](https://en.wikipedia.org/wiki/Partition%5C%28number_theory%5C%29#Ferrersdiagram) para visualizar la situación (aquí con $k=3$ y $n=8$) vemos que cada partición que contiene partes cada una $\leq 3$, reflejada en la diagonal principal, corresponde con una partición que contiene como máximo 3 partes.

                                

Dado que esta correspondencia es biyectiva, la función generadora es la misma en ambos casos.

Concluimos que la función generadora $P^{(=k)}(x)$ para el número de particiones con exactamente $k$ partes es \begin{align*} \color{blue}{P^{(=k)}(x)}&=P^{(\leq k)}(x)-P^{(\leq k-1)}(x)\\ &=\frac{1}{(1-x)(1-x^2)\cdots(1-x^k)}\\ &\qquad-\frac{1}{(1-x)(1-x^2)\cdots(1-x^{k-1})}\\ &=\frac{1}{(1-x)(1-x^2)\cdots(1-x^{k-1})}\left(\frac{1}{1-x^k}-1\right)\\ &=\color{blue}{\frac{x^k}{(1-x)(1-x^2)\cdots(1-x^k)}}\\ \end{align*}