7
$\begingroup$

Prove $\Pi_{k=1}^\infty(1+q^k)=\Pi_{k=1}^\infty\frac{1}{(1-q^{(2k-1)})}$ are equivalent generating series using a combinatorial proof.

The LHS of the equation is the generating series of partitions where distinct parts appear only once.

The RHS looks similar to the equation for the generating series for all partitions which is $\Pi_{k=1}^\infty\frac{1}{1-q^k}$. In the original generating series, the exponent for $q$ would take the following values $\{1,2,3,4,\dots \}$. However, when we replace the exponent in the equation we are trying to prove, it takes the values $\{1,3,5,7,\dots \}$. The part I can't figure out is how this small change makes these equivalent with an explanation.

$\endgroup$
0

3 Answers 3

3
$\begingroup$

It is known that the number of partitions of an integer into distinct parts (LHS) equals the number of partitions into odd parts (RHS).
For the various ways to prove it, see e.g. this excellent lecture, where at pag. 9 and 10 these two approaches are provided, which I am going to summarize herewith.

  1. conversion of the o.g.f. $$ \begin{gathered} \text{o}\text{.g}\text{.f}\text{.}\;\text{DISTINCT} = \left( {1 + x} \right)\left( {1 + x^{\,2} } \right)\left( {1 + x^{\,3} } \right) \cdots = \hfill \\ = \frac{{\left( {1 - x^{\,2} } \right)}} {{\left( {1 - x} \right)}}\frac{{\left( {1 - x^{\,4} } \right)}} {{\left( {1 - x^{\,2} } \right)}}\frac{{\left( {1 - x^{\,6} } \right)}} {{\left( {1 - x^{\,3} } \right)}} \cdots = \hfill \\ = \frac{1} {{\left( {1 - x} \right)}}\frac{1} {{\left( {1 - x^{\,3} } \right)}}\frac{1} {{\left( {1 - x^{\,5} } \right)}} \cdots = \text{o}\text{.g}\text{.f}\text{.}\;\text{ODD} \hfill \\ \end{gathered} $$
  2. Bi-jective correspondence
    Given one partition of $n$ into distinct parts (i.e., sum of strictly decreasing sequence) $$ n = d_{\,1} + d_{\,2} + \cdots + d_{\,m} $$ Consider that each integer can univocally be written as a power of $2$ (incl. $2^0$) multiplied by an odd integer (factoring of less significant $0$s in the binary representation), so $$ n = 2^{\,\alpha _{\,1} } O_{\,1} + 2^{\,\alpha _{\,2} } O_{\,2} + \cdots + 2^{\,\alpha _{\,m} } O_{\,m} $$ where the $O_j$ are odd numbers, possibly repeated (but in that case with a different $\alpha_j$).
    We can then group for the different values of the odd numbers, as $$ \begin{gathered} n = \left( {0 + 2^{\,\alpha _{\,1,1} } + 2^{\,\alpha _{\,1,2} } + \cdots } \right)1 + \left( {0 + 2^{\,\alpha _{\,2,1} } + 2^{\,\alpha _{\,2,2} } + \cdots } \right)3 + \left( {0 + 2^{\,\alpha _{\,q,1} } + 2^{\,\alpha _{\,q,2} } + \cdots } \right)5 + \cdots \quad \left| {\;\alpha _{\,q,j} \ne \alpha _{\,q,k} } \right. = \hfill \\ = \mu _{\,1} 1 + \mu _{\,3} 3 + \mu _{\,5} 5 + \cdots \hfill \\ \end{gathered} $$ Therefore, each partition into distinct parts can be made to correspond bijectively to the binary representation of the $\mu$ vector, hence to a partition into odd parts (repetition allowed).
$\endgroup$
3
  • $\begingroup$ Perfect ref. (+1) $\endgroup$
    – epi163sqrt
    Nov 14, 2016 at 8:24
  • 1
    $\begingroup$ @MarkusScheuer: glad of your appreciation: I found Wilf's paper to be in fact a good introduction to Partitions (of integers). $\endgroup$
    – G Cab
    Nov 14, 2016 at 12:41
  • $\begingroup$ @user1952009, it is not aceptable to call someone's answer a joke here. If you do not like it, downvote it. But this site requires of its users ato be nice. I will delete the off topic comments. $\endgroup$ Nov 15, 2016 at 20:09
2
$\begingroup$

Hint: This is not combinatorial, but notice that $$ 1+q^k=\frac{1-q^{2k}}{1-q^k} $$ Take the product and cancel.

$\endgroup$
1
$\begingroup$

(everything converges absolutely on the unit disk) $$\prod_{m=0}^\infty (1+z^{2^m})= \sum_{n=0}^\infty z^n = \frac{1}{1-z}$$

$$\prod_{k= 1}^\infty \frac{1}{1-q^{2k-1}} = \prod_{m\ge0,k\ge 1} (1+q^{2^m (2k-1)}) = \prod_{k = 1}^\infty (1+q^k)$$

$\endgroup$
6
  • $\begingroup$ Notice that the question asks for a combinatorial proof of the equality, based on interpreting both sides as generating functions of something. $\endgroup$ Nov 15, 2016 at 20:01
  • $\begingroup$ @MarianoSuárez-Álvarez $n = 2^m (2k-1)$ is combinatorial, as well as $\prod_m (1+z^{2^m}) = \sum_n z^n$. Also, this is the most intuitive proof, IMO, but if you don't agree, feel free to explain why $\endgroup$
    – reuns
    Nov 15, 2016 at 20:07
  • $\begingroup$ There is a well established meaning for interpreting a series as a generating function. Your argument does not do that, and that is simply a fact. You may like your argument, I may like your argument, but it is clearly not what the OP was asking for. $\endgroup$ Nov 15, 2016 at 22:59
  • $\begingroup$ @MarianoSuárez-Álvarez I think you are wrong. The OP cannot know by advance the proof he prefers without having seing the proofs. And the other proofs are just the same as the one I wrote, translated with other words making it less obvious (see G Cab's answer) $\endgroup$
    – reuns
    Nov 15, 2016 at 23:03
  • $\begingroup$ Your argument is arithmetical: it shows that the equality the OP is asking for is a result of the facts (I) that every number has a unique expression as a sum of powers of two, and that (ii) every number is a product of a power of two and an odd number. The combinatorial interpretation of the equality, in the other hand, is that a number has as many partitions into different parts as it has into odd parts. You surely appreciate the difference. $\endgroup$ Nov 15, 2016 at 23:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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