¿El mismo número de particiones de un determinado tipo?

Question

¿Hay una explicación rápida de por qué el número de particiones de $n$ tal que ninguna parte sea divisible por $d$ es igual al número de particiones de $n$ donde ninguna parte se repite $d$ o más veces, para todos $n$ y $d$ ?

Me cuesta saltar de las condiciones de uno a otro para ver por qué deberían dar el mismo número de particiones. Saludos.

Answer 1

No sé de un buen argumento intuitivo; la prueba usual es mediante la generación de funciones. La generación de la función para el número de particiones con ninguna parte divisible por $d$ es $$g(x)=\prod_{k\ge 1,\,d\nmid k}\frac1{1-x^k}\;,\tag{1}$$ and the generating function for the number of partitions with no part repeated $d$ or more times is $$h(x)=\prod_{k\ge 1}(1+x^k+x^{2k}+\cdots+x^{(d-1)k})=\prod_{k\ge 1}\frac{1-x^{dk}}{1-x^k}\;.\tag{2}$$

Entonces $$g(x)\prod_{k\ge 1}(1-x^k)=\prod_{k\ge 1,\,d\mid k}(1-x^k)=\prod_{k\ge 1}(1-x^{dk})=h(x)\prod_{k\ge 1}(1-x^k)\;,$$ so $h(x)=g(x)$.

Para ver por qué se $(1)$ $(2)$ son las deseadas funciones de generación, tenga en cuenta que $$\frac1{1-x^k}=1+x^k+x^{2k}+x^{3k}+\cdots\;.$$ Thus, in the product in $(1)$ there is one $x^n$ term for every way of writing $n$ as a sum of numbers not divisible by $d$, and the coefficient of $x^n$ must therefore be the number of ways of writing $n$ as a sum of numbers not divisible by $d$. In the product in $(2)$ there is one $x^n$ term for every way of writing $n$ as a sum $n_1k_1+n_2k_2+\cdots+n_mk_m$ in which the $k_i$ are distinct and the coefficients $n_i$ are all less than $d$. Such a decomposition of $n$ corresponds to a partition with $n_i$ parts of size $k_i$ for $i=1,\dots,m$, so the coefficient of $x^n$ in $h(x)$ must be the number of partitions of $n$ in which every part appears at most $d-1$ veces.

Answer 2

Un argumento biyectivo:

En el lado sin demasiadas repeticiones, se dividen las partes divisibles por $d^k$ en $d^k$ partes (donde $d^k$ es la mayor potencia de $d$ dividiendo el tamaño de la pieza). Así se obtiene una partición sin partes divisibles por $d$ .

Para volver atrás, se escriben las multiplicidades en base $d$ y si tiene $\sum_i a_i d^i$ partes de tamaño $s$ y luego los pegas, para conseguir $a_i$ partes de tamaño $sd^i$ .