There is a good question here.

My question is;

"x is a positive integer and $\lfloor x\rfloor$ denote the largest integer smaller than or equal to $x$. Prove that $\lfloor n / 3\rfloor+1$ is the number of partitions of $n$ into distinct parts where each part is either a power of two or three times a power of two."

There is a Theorem related with this question.

Theorem: $ p(n \mid \text {parts in } N)=p(n \mid \text { distinct parts in } M) \quad \text { for } n \geq 1 $

where $N$ is any set of integers such that no element of $N$ is a power of two times an element of $N,$ and M is the set containing all elements of $N$ together with all their multiples of powers of two.

Can anyone help? thanks.


Let’s use a generating function.

If $p(n)$ is the number of partitions of $n$ into numbers of the form $2^k$ or $3\cdot 2^k$, then we have the following generating function:

$$\sum_{n=0}^\infty p(n)x^n = \prod_{k=0}^\infty (1+x^{2^k})(1+x^{3\cdot 2^k})$$

Recall the following identity, which follows from the fact that every nonnegative integer has a unique binary representation:

$$\prod_{k=0}^\infty (1+x^{2^k})=1+x+x^2+...=\frac{1}{1-x}$$

From this, it follows that our generating function is given by

$$\sum_{n=0}^\infty p(n)x^n=\frac{1}{(1-x)(1-x^3)}$$

On the other hand, we have that

$$\begin{align} \sum_{n=0}^\infty (\lfloor n/3\rfloor +1)x^n &= 1+x+x^2+2x^3+2x^4+2x^5+3x^6+... \\ &= (1+x+x^2)(1+2x^3+3x^6+4x^9+...) \\ &= \frac{1+x+x^2}{(1-x^3)^2} \\ &= \frac{1}{(1-x)(1-x^3)} \end{align}$$

Well, whaddaya know?! The two generating functions are equal to each other! Thus, we have the desired result:

$$p(n)=\lfloor n/3\rfloor +1$$

QED! Thanks for the fun problem!

| cite | improve this answer | |
  • 1
    $\begingroup$ thats a great answer. thanks. $\endgroup$ – robert08 Jun 25 at 21:12
  • 1
    $\begingroup$ @robert08 No problem! Don’t forget to $\checkmark$! :) $\endgroup$ – Franklin Pezzuti Dyer Jun 25 at 21:12
  • $\begingroup$ of course . i will do it:) $\endgroup$ – robert08 Jun 25 at 21:13
  • 1
    $\begingroup$ clever approach ! $\endgroup$ – G Cab Jun 25 at 21:14

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.