The number of integer solution $x_1+x_2+\cdots+x_k=n$ such that $x_i\in \{1,2\}$

Question

I am trying to find a combinatorial interpretation for the number of integer solution of the equation $$x_1+x_2+\cdots+x_k=n$$ such that $x_i\in \{1,2\}$.

I know that the number of this solution is ${k \choose n-k}$. Also $$\sum_{k=0}^n {k\choose n-k}=F_{n+1},$$ where $F_n$ is $n^{th}$-Fibonacci number.

Is it possible to find the solution for this system with the expression of Balls In Bins With Limited Capacity?

Answer 1

It’s an especially easy version of that problem.

First put one ball in each of the $k$ bins; you now have $n-k$ balls left to distribute amongst the $k$ bins. You can put at most one of them into any bin, so you just have to choose which $n-k$ bins will get these extra balls, and you can do this in $\binom{k}{n-k}$ different ways. Each of those ways corresponds to a solution of the equation, and vice versa.

Answer 2

Each of the $k$ values will either be $1$ or $2$. Let's say there are $m$ values equal to $2$, and the rest, $k-m$, are equal to $1$.

This means that $x_1+\cdots + x_k = m\cdot 2 + (k-m) \cdot 1 = k+m$, and since you also know that $x_1+\cdots x_k = n$, you have $k+m = n$ and so $m = n-k$.

---

Every solution to your problem matches directly with one selection of $m$ out of the $k$ values (i.e., you choose which of the $k$ values will be equal to $2$, and the rest will be equal to $1$), and therefore, there are ${k\choose m}$ of them.

Answer 3

Let $y_i:=x_k-1\in\{0,1\}$. The sum of the $y_i$ must be $n-k$ so you must pick $n-k$ ones among $k$.

$$\binom k{n-k}.$$