5
$\begingroup$

Is there a quick explanation of why the number of partitions of $n$ such that no parts are divisible by $d$ is the same as the number of partitions of $n$ where no part is repeated $d$ or more times, for all $n$ and $d$?

I'm having difficulty jumping from the conditions of one to the other to see why they should give the same number of partitions. Cheers.

  • 0
    This result is known as [Glaisher’s theorem](http://en.wikipedia.org/wiki/Glaisher%27s_theorem), and the bijection given by Phira below is known as _Glaisher’s bijection_; see [here](http://math.georgiasouthern.edu/~asills/talks/bij-p.pdf) for an exposition.2011-12-16

2 Answers 2

6

I don’t know of a nice intuitive argument; the usual proof is by generating functions. The generating function for the number of partitions with no part divisible by $d$ is $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}$

Then $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)$.

To see why $(1)$ and $(2)$ are the desired generating functions, note that $\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$ times.

6

A bijective argument:

On the side without too many repetitions, you break up parts divisible by $d^k$ into $d^k$ parts (where $d^k$ is the highest power of $d$ dividing the size of the part). This gets you a partition without parts divisible by $d$.

To go back, you write the multiplicities in base $d$ and if you have $\sum_i a_i d^i$ parts of size $s$, then you glue them, to get $a_i$ parts of size $sd^i$.

  • 0
    @Phira: The explanation is still the same as the one you gave: uniqueness of the expression of natural numbers in base $d$. Any multiset of parts of the form $sd^i$ where $s$ is not divisible by $d$ will eventually break up into parts of size $s$ only, and if multiplicities are required to be less than $d$ initially, this is a bijection to the collection of multisets of parts $s$. No difference, really.2011-12-18