Proving that $t_n = r_n$

Question

Given a non-negative integer $n,$ let $t_n$ be the number of ways to partition $n$ using only powers of $2$ where each power is used at most three times, and let $r_n$ be the number of ways to partition $n$ using $1,2,3,9$ where $1$ and $3$ are used at most twice. Prove that $t_n = r_n.$

---

For $t_n,$ I let $n = \sum_i c_i2^i$ such that $0 \leq c_i \leq 3$ and then applied generating functions to give me $t_n = \lfloor \frac{n}{2} \rfloor + 1.$ However, I don't quite know how to calculate $r_n.$

Answer 1

Using $1$ and $3$ alone and at most twice each, we can write each of $0,1,2,3,4,5,6,7,8$ and in a unique way.

Hence $r_n$ is obtained by taking any suitable number $n_2$ of $2$'s, which allows $n_2=0,1,2,\ldots, \lfloor\frac n2\rfloor$ (so $\lfloor \frac n2\rfloor +1$ ways); then use $1$'s and $3$'s as above to get down to the nearest multiple of $9$; and finally use an according amount of $9$'s. We conclude $$r_n=\left\lfloor \frac n2\right\rfloor +1.$$

Answer 2

The generating function for $t_n$ is \begin{align} &\quad\prod_{k \ge 0} (z^{0\cdot2^k}+z^{1\cdot2^k}+z^{2\cdot2^k}+z^{3\cdot2^k}) \\ &=\prod_{k \ge 0} (1+z^{2^k})(1+z^{2^{k+1}}) \\ &=\prod_{k \ge 0} (1+z^{2^k}) \prod_{k \ge 0} (1+(z^2)^{2^k}) \\ &=\frac{1}{1-z}\cdot \frac{1}{1-z^2} \quad \text{by uniqueness of binary expansion} \\ &=\frac{1}{(1+z)(1-z)^2}. \end{align}

The generating function for $r_n$ is \begin{align} &\quad(z^{0\cdot1}+z^{1\cdot1}+z^{2\cdot1}) (z^{0\cdot2}+z^{1\cdot2}+z^{2\cdot2}+z^{3\cdot2}+\cdots) (z^{0\cdot3}+z^{1\cdot3}+z^{2\cdot3}) (z^{0\cdot9}+z^{1\cdot9}+z^{2\cdot9}+z^{3\cdot9}+\cdots) \\ &= (1+z+z^2) \left(\frac{1}{1-z^2}\right) (1+z^3+z^6) \left(\frac{1}{1-z^9}\right)\\ &=\frac{1}{(1+z)(1-z)^2}. \end{align}

Hence $t_n=r_n$ for all $n \ge 0$.

Answer 3

Let me add (another) generating function solution to this problem. As it works out, these match the number of partitions $a(n)$ with parts from $\{1,2\}$ (which, by conjugation, is the number of partitions with up to 2 parts). The generating function for $a(n)$ is $$ \sum_{n=0}^\infty a(n)q^n = \frac{1}{(1-q)(1-q^2)}.$$

The connection to $r(n)$ is pretty direct. Its generating function is $$ \sum_{n=0}^\infty r(n)q^n = \frac{(1+q+q^2)(1+q^3+q^6)}{(1-q^2)(1-q^9)}.$$ Your favorite computer algebra system can tell you that $1-q^9$ factors as $(1-q)(1+q+q^2)(1+q^3+q^6)$ so that $$ \sum_{n=0}^\infty r(n)q^n = \frac{(1+q+q^2)(1+q^3+q^6)}{(1-q^2)(1-q)(1+q+q^2)(1+q^3+q^6)} = \frac{1}{(1-q)(1-q^2)} = \sum_{n=0}^\infty a(n)q^n.$$

The connection to $t(n)$ is a little trickier. Its generating function is $$ \sum_{n=0}^\infty t(n)q^n = \prod_{i=0}^\infty \left(1 + q^{2^i} + q^{2\cdot 2^i} + q^{3\cdot 2^i}\right).$$ Now $\left(1 + q^{2^i} + q^{2\cdot 2^i} + q^{3\cdot 2^i}\right) = \left(1+q^{2^i}\right)\left(1+q^{2\cdot 2^i}\right)$ so that $$\sum_{n=0}^\infty t(n)q^n = \prod_{i=0}^\infty \left(1 + q^{2^i}\right)\left(1 + q^{2^{i+1}}\right)$$ where each power of 2 starting at 2 arises twice, therefore $$\sum_{n=0}^\infty t(n)q^n = (1+q)\prod_{i=1}^\infty \left(1 + q^{2^i}\right)^2.$$ Now multiply top & bottom by $(1-q)$ to get the telescoping product \begin{align*} \sum_{n=0}^\infty t(n)q^n & = \frac{(1-q)(1+q)(1 + q^2)^2(1 + q^4)^2(1 + q^8)^2\cdots}{(1-q)} \\ & = \frac{(1-q^2)(1 + q^2)^2(1 + q^4)^2(1 + q^8)^2\cdots}{(1-q)} \\ & = \frac{(1+q^2)(1 - q^4)(1 + q^4)^2(1 + q^8)^2\cdots}{(1-q)} \\ & = \frac{(1+q^2)(1 + q^4)(1 - q^8)(1 + q^8)^2\cdots}{(1-q)} \\ & = \frac{(1+q^2)(1 + q^4)(1 + q^8)\cdots}{(1-q)}. \end{align*} Multiplying top & bottom by $(1-q^2)$ completes the collapse: \begin{align*} \sum_{n=0}^\infty t(n)q^n & = \frac{(1-q^2)(1+q^2)(1 + q^4)(1 + q^8)\cdots}{(1-q)(1-q^2)} \\ & = \frac{(1-q^4)(1 + q^4)(1 + q^8)\cdots}{(1-q)(1-q^2)} \\ & = \frac{(1-q^8)(1 + q^8)\cdots}{(1-q)(1-q^2)} \\ & = \frac{1}{(1-q)(1-q^2)} = \sum_{n=0}^\infty a(n)q^n. \end{align*}