Different ways to solve a number sequencing problem

Question

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 :

1. 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 )
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 .

Answer 1

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})!}$$

Answer 2

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).