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!