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?
 A: 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$.
A: 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
