4
$\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
    If something is repeated $d$ times then it must also be divisible by $d$ by definition. So, it seems like you are using alternate definitions of divisbility in the two situations and hence the partitions should be the same.2011-12-15
  • 2
    @tards : You're missing nearly everything. The partitions of $6$ in which no part is divisible by 2 are $5+1$, $3+3$, $3+1+1+1$ and $1+1+1+1+1+1$. There are four of them. The partitions of $6$ in which no part occurs 2 or more times are $6$, $5+1$, $4+2$, and $3+2+1$. There are four of them. Think about that and maybe you will come to understand the question.2011-12-15
  • 1
    Integer Partitions by George Andrews and Kimmo Eriksson (Cambridge U. Press, 2004) is a nice introduction to the topic of partitions2011-12-15
  • 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

5

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
    Thanks Phira for the bijection.2011-12-16
  • 0
    I like the following description for the forward construction slightly more: while there is any part whose size is divisible by $d$, choose one and break it up into $d$ equal parts. This avoids talking about the highest power, and also adds a bit of surprise that the procedure has an inverse (which indeed is not a step-by-step inverse).2011-12-17
  • 0
    @MarcvanLeeuwen I agree, but then I would have had to explain *why* it is bijective.2011-12-18
  • 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