# Interesting Partition Questions

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!

• thats a great answer. thanks.
– user780994
Jun 25, 2020 at 21:12
• @robert08 No problem! Don’t forget to $\checkmark$! :) Jun 25, 2020 at 21:12
• of course . i will do it:)
– user780994
Jun 25, 2020 at 21:13
• clever approach ! Jun 25, 2020 at 21:14