4
$\begingroup$

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.

$\endgroup$

1 Answer 1

5
$\begingroup$

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!

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

Your Answer

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