Writing $11$ by sum of $3$s and $1$s

Question

We want to find number of ways for writing $11$ by sum of $3$s and $1$s. For example $11 = 3 + 3 + 3 + 1 + 1$ and $11= 1 + 3 + 3 + 1 + 3$ are two ways for writing $11$ . I tried to use the diophantine equation but I don't know whether it is useful or not . It is very hard to write all of them situations . Also if there is a general way for questions like this , I will glad to know it .

Answer 1

Generating function approach

If $a_n$ is the number of ways to write $n$ as the sum of $1s$ and $3s$, then $a_0=a_1=a_2=1$ and $a_{n+3}=a_{n+2}+a_{n}$. If $f(x)=\sum_{n} a_nx^n$ then $$f(x)=\frac{1}{1-x-x^3} = \sum_{k=0}^{\infty} (x+x^3)^k$$

If $k$ is even, then there is no $x^{11}$ term in $(x+x^3)^k$. When $k$ is odd, you need the coeffient of $x^{11-k}$ in $(1+x^2)^k$, which ie $\binom{k}{(11-k)/2}$.

Letting $k=2j+1$, the result is $$\sum_{j=0}^{5} \binom{2j+1}{5-j}=\binom{1}{5}+\binom{3}{4}+\binom{5}{3}+\binom{7}{2}+\binom{9}{1}+\binom{11}{0}$$

Basically, $k$ is the number of values in the sum, which must be odd since the sum must be odd. Then $(11-k)/2$ is the number that must be $3$, and $\binom{k}{(11-k)/2}$ is the number of ways to place that $3$s in the sum.