Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  tards Dec 15 '11 at 18:36
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. –  Michael Hardy Dec 15 '11 at 18:42
1  
Integer Partitions by George Andrews and Kimmo Eriksson (Cambridge U. Press, 2004) is a nice introduction to the topic of partitions –  Joseph Malkevitch Dec 15 '11 at 18:45
    
This result is known as Glaisher’s theorem, and the bijection given by Phira below is known as Glaisher’s bijection; see here for an exposition. –  David Bevan Dec 16 '11 at 18:18
add comment

2 Answers

up vote 3 down vote accepted

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.

share|improve this answer
    
Thanks Brian Scott. –  Noel Dec 15 '11 at 22:30
add comment

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

share|improve this answer
    
Thanks Phira for the bijection. –  Noel Dec 16 '11 at 22:21
    
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). –  Marc van Leeuwen Dec 17 '11 at 10:24
    
@MarcvanLeeuwen I agree, but then I would have had to explain why it is bijective. –  Phira Dec 18 '11 at 13:21
    
@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. –  Marc van Leeuwen Dec 18 '11 at 13:45
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.