I am stuck with this combinatorics problems –
Let $n$ be a positive integer and let $b_{n}$ denote the number of compositions of $n$ into $k$ parts, where each part is one or two. For example, $(1, 2, 1, 2, 1)$ and $(2, 2, 1, 1, 1)$ are two compositions of $n = 7$ into $k = 5$ parts.
Firstly, we need to find the generating series for $b_{n}$
Secondly, Prove that $b_{n} = {k \choose n-k}$ for $k\le n \le2k$ and $b_{n} = 0$ otherwise.
Best Answer
In order to calculate the generating series -
Let {1,2}$^{𝑘}$ be the set of compositions with k parts, each of which is either 1 or 2.
Then, applying the "Product Lemma" $$\varphi_{s}(x) = (\varphi_{(1,2)} (x))^{k} = (x+x^{2})^{k} $$
Proving -
A composition of n with k parts will have $i$ parts equal to 2, for some $0\le i\le k$. Note that the number of parts equal to 1 is $k-i$, and $n = (k-i) + 2i$, giving $i = n-k$. There are $k$ positions for the $n-k$ parts equal to 2, so there are a total of {k \choose n-k} compositions of $n$ into $k$ parts, each either $1$ or $2$. Note that $0\le i\le k$ implies $k\le n\le 2k$, and the number of compositions is zero otherwise.