Para cada partición $\pi$ fijo entero $n$, $\sum{F(\pi)}=\sum{G(\pi)}$

Question

Tengo que probar la siguiente pregunta.

Para cada partición $\pi$ fijo entero $n$, definir $F(\pi)$=número de repeticiones de 1 como un sumando, y $G(\pi)$=no. de los distintos sumandos en la partición. Demostrar que $\sum{F(\pi)}=\sum{G(\pi)}$.

Yo estaba tratando de resolver esta tomando un ejemplo de 5 con Ferrers gráfico, pero no se cómo llegar a probarlo.

Answer 1

La siguiente prueba de los usos ordinarios de la generación de funciones (bivariado). La partición de generación de función, donde están marcados es $$Q_1(z, u) = \frac{1}{1-uz} \prod_{k\ge 2} \frac{1}{1-z^k}.$$ Si queremos que la suma de las ocurrencias de uno como un sumando para todas las particiones de $n$ tenemos que calcular el $$\left.\frac{d}{du} Q_1(z, u) \right|_{u=1} = \left. -1\times \frac{1}{(1-uz)^2} \times -z \times \prod_{k\ge 2} \frac{1}{1-z^k} \right|_{u=1} = \frac{z}{1-z} \prod_{k\ge 1} \frac{1}{1-z^k}.$$ Por otro lado, el marcado de distintos sumandos se parece a esto: $$Q_2(z,u) = \prod_{k\ge 1}\left(1 + u z^k + u z^{2k} + u z^{3k} + \cdots\right).$$ Una vez más la diferenciación y establecimiento $u=1$ da esta vez $$\left.\frac{d}{du} Q_2(z, u) \right|_{u=1} = \left.\prod_{k\ge 1}\left(1 + u z^k + u z^{2k} + u z^{3k} + \cdots\right) \times \sum_{k\ge 1} \frac{z^k + z^{2k} + z^{3k} + \cdots} {1 + u z^k + u z^{2k} + u z^{3k} + \cdots}\right|_{u=1} \\= \prod_{k\ge 1}\frac{1}{1-z^k} \sum_{k\ge 1} \frac{z^k/(1-z^k)}{1/(1-z^k)} = \prod_{k\ge 1}\frac{1}{1-z^k} \sum_{k\ge 1} z^k = \frac{z}{1-z} \prod_{k\ge 1}\frac{1}{1-z^k}.$$ Las dos funciones de generación son exactamente los mismos, QED.

Hay similar cálculos en este MSE enlace que te puse y esta MSE vínculo II.

Answer 2

Un recuento de argumento atribuido a Richard Stanley aparece aquí.

Brevemente, que es como sigue:

$$\displaystyle\sum_{\pi\,\vdash n} {F(\pi)}=\displaystyle\sum_{i=1}^n p(n-i)\textrm,$$

debido a $p(n-i)$ es el número de particiones de $n$, con al menos$i$. La suma cuenta el número de particiones con $k$ ones $k$ veces: una vez en $p(n-1)$, una vez en $p(n-2)$, y así hasta llegar a un final el tiempo en $p(n-k)$.

A continuación, $\displaystyle\sum{G(\pi)}$ se muestra a ser lo mismo, por una inteligente observación.

Deje $True(P)$ valor $1$ si $P$ es verdadera y $0$ si $P$ es falso, y deje $H(i)$ el número de particiones de $n$ que contienen (al menos uno) $i$. Entonces

$$\sum_{\pi\,\vdash n}{G(\pi)}=\sum_{\pi\,\vdash n}\sum_{i=1}^nTrue\left(\pi \textrm{ contains an }i \right) = \sum_{i=1}^n\sum_{\pi\,\vdash n}True\left(\pi \textrm{ contains an }i \right) = \sum_{i=1}^n H(i)\textrm.$$

La observación de que $H(i)=p(n-i)$ completa la prueba.