Partitions in which no part is a square?

I asked a similar question earlier about partitions, and have a suspicion about another way to count partitions.

Is it true that the number of partitions of $n$ in which each part $d$ is repeated fewer than $d$ times is equal to the number of partitions of $n$ where no part is a square?

I tried this out for $n=2,3,4$, and so far it checks out. Is there a way to prove it more generally?

-
The natural thing to do in such a case is to write generating functions for the two cases and see if they look similar. Even if you can't decide, computing a number of terms of the series is much faster than testing cases by hand. Did you try? – Marc van Leeuwen Dec 17 '11 at 19:04

As mentioned in the comment above, generating functions are the standard tool for proving such statements. If you can write down the proper generating functions, proofs sometimes just fall right out.

Let $S = \{ \ell^2 \;|\; \ell \in \mathbb{N} \}$ be the set of perfect squares.

In the following generating function: the coefficient of $x^k$ is the number of partitions of $k$ which do not involve $d$ or more copies of $d$ for each $d$.

$$\prod\limits_{d=1}^\infty \left(\sum\limits_{j=0}^{d-1} x^{jd}\right) =$$

$$(1+x^2)(1+x^3+x^6)(1+x^4+x^8+x^{12})\cdots (1+x^d+x^{2d}+\cdots+x^{d(d-1)}) \cdots$$

$$=((1-x^2)^{-1}-x^{2^2}(1-x^2)^{-1})((1-x^3)^{-1}-x^{3^2}(1-x^3)^{-1})\cdots ((1-x^k)^{-1}-x^{k^2}(1-x^k)^{-1}) \cdots$$

$$=\left(\frac{1-x^{1^2}}{1-x^1}\right)\left(\frac{1-x^{2^2}}{1-x^2}\right)\left(\frac{1-x^{3^2}}{1-x^3}\right)\cdots \left(\frac{1-x^{k^2}}{1-x^k}\right) \cdots$$

$$=\prod\limits_{k = 1}^\infty \frac{1-x^{k^2}}{1-x^k} = \prod\limits_{k = 1}^\infty \frac{\frac{1}{1-x^k}}{\frac{1}{1-x^{k^2}}} =\frac{\prod\limits_{k = 1}^\infty \frac{1}{1-x^k}}{\prod\limits_{k=1}^\infty\frac{1}{1-x^{k^2}}} = \prod\limits_{k\in\mathbb{N}-S} \frac{1}{1-x^k}$$

In the final generating function: the coefficient of $x^k$ counts the number of partitions not involving perfect squares.

Edit For a bit more about generating functions here is a link to another question I answered: partitions and generating functions

-
Thank you Bill, this is a great answer. – Noel Dec 18 '11 at 6:18
@Bill: In the last line, wouldn't you prefer just cancelling the terms $1-x^{k^2}$ against their counterparts in the denominator right away? – Marc van Leeuwen Dec 18 '11 at 17:13
@MarcvanLeeuwen I guess that would have been a bit more efficient. Oh well. :) Since it doesn't make a big difference, I'll just leave it alone. – Bill Cook Dec 18 '11 at 18:46

Now that you have a generating function proof (so you know the result is true), you may wonder if you can actually map partitions of one kind bijectively to those of the other kind. Motivated by this other question, the following idea comes to mind: starting with a partition in which no part $d$ is repeated $d$ times or more, in order to get rid of square parts, break any part $x^2$ into $x$ parts equal to $x$, and repeat. Since there were no parts equal to $1$ this terminates, producing a partition without square parts.

We must show that every partition of without square parts is produced exactly once from a partition in which no part $d$ is repeated more $d$ times or more. We can treat non-squares separately: if $k>1$ is a non-square, then the parts in the original partition that would have been broken up eventually into parts of size $k$ are those of size $k$, $k^2$, $k^4$, $k^8$, ..., $k^{2^i}$,... Supposing the multiplicity of $k$ in the final partition is $m$, we must decompose $$mk=c_0k+c_1k^2+c_2k^4+\cdots+c_ik^{2^i}+\cdots \quad\text{with c_i<k^{2^i} for all i\in\mathbf N}$$ But this is uniquely possibly by the expression of $mk$ in the mixed radix number system with place values $1,k,k^2,k^4,k^8,\ldots$ (the initial $1$ is only there to have a number system capable of expressing all natural numbers; $mk$ being a multiple of $k$ has digit $0$ on this least significant position.) Concretely one can find the $c_i$ either in order of increasing $i$ by taking remainders modulo the next $k^{2^{i+1}}$, or by decreasing $i$ by allocating the largest chunks first and then using smaller chunks for what is left of $mk$.

-
Thanks for this other argument, Marc van Leeuwen. – Noel Dec 19 '11 at 7:05
See Wilf's Lectures on Integer Partitions for more on bijections like this. – David Bevan Dec 19 '11 at 8:56
@David Bevan: Thank you for the reference. So apparently this bijection, as well as the one in the question I linked to, are special cases of a general construction of partition maps proved to be bijective by Kathleen O'Hara. – Marc van Leeuwen Dec 21 '11 at 14:26