Different ways to solve a number sequencing problem Given a integer N greater than zero.
How many sequences of 1's and 2's are there such that sum of the numbers in the sequence = N ?
(not necessary that every sequence must contain both 1 and 2 )
example :
for N = 2 ; 11,2 => ans = 2 sequences of 1's and 2's
for N = 3 ; 111,12,21 => ans = 3 sequences of 1's and 2's
I approached in the following two ways :


*

*Using recurrence relation (dynamic programming) : It is coming out to be same as Fibonacci relation with F(1) = 1 ( N=1 and we have only one possibility 11 )
and F(2) = 2 ( N=2 and we have two possibility 11 and 2 )

*Using domino tiling examples as described in the concrete mathematics book chapter : "Generating Function".


But I would like to know, is there any other way to solve this problem ?
With possible idea and references .
 A: This is just a somewhat more compact notation when using generating functions. We can select either $1$ or $2$ and encode this as exponents in the expression
\begin{align*}
  x^1+x^2
  \end{align*}
Since we want strings built from the alphabet $\{1,2\}$ which sum up to $N$ we consider all expressions $(x^1+x^2)^j$ with $j\geq 0$ and extract the coefficient of terms $x^N$.
We use the coefficient of operator $[x^N]$ to denote the coefficient of $x^N$ of a series.

We obtain this way
  \begin{align*}
[x^N]\frac{1}{1-(x+x^2)}&=[x^N]\sum_{j=0}^\infty(x+x^2)^j\tag{1}\\
&=\sum_{j=0}^N[x^{N-j}](1+x)^j\tag{2}\\
&=\sum_{j=0}^N[x^{N-j}]\sum_{l=0}^j\binom{j}{l}x^l\\
&=\sum_{j=0}^N\binom{j}{N-j}\tag{3}
\end{align*}

Comment:


*

*In (1) we represent all strings built from the alphabet $\{1,2\}$ by a geometric power series.

*In (2) we use the linearity of the coefficient of operator and apply the rule $$[x^{p+q}]A(x)=[x^p]x^{-q}A(x)$$ We also respect that the coefficient is non-negative and restrict the upper limit of the series by $N$.

*In (3) we select the coefficient of $x^{N-j}$. Note the convention $\binom{r}{k}=0$ if $r\in\mathbb{C}$ and $k$ a negative integer (see e.g. (5.1) p. 154 in Concrete Mathematics).
A: If $N$ is even, then each sequence is made of $\color\red{2n}$ ones and $\color\green{N/2-n}$ twos.
Hence the total number of sequences is:
$$\sum\limits_{n=0}^{N/2}\frac{(\color\red{2n}+\color\green{N/2-n})!}{(\color\red{2n})!\times(\color\green{N/2-n})!}$$

If $N$ is even, then each sequence is made of $\color\red{2n+1}$ ones and $\color\green{N/2-n-1/2}$ twos.
Hence the total number of sequences is:
$$\sum\limits_{n=0}^{N/2}\frac{(\color\red{2n+1}+\color\green{N/2-n-1/2})!}{(\color\red{2n+1})!\times(\color\green{N/2-n-1/2})!}$$
