Why does this combinatorics formula work? I'm trying to figure out why this formula works. If you want to find the number of non negative integer solutions to 
$$x_1 + \cdots + x_k=n$$
where 
$$x_i \ge a_i \ge 0$$
The formula is given by
$$\binom{n-a_1-a_2\cdots a_k+k-1}{k-1}$$
I was wondering if someone could prove this formula or explain the logic behind why this works?
 A: If you already know about standard integer compositions, this may help:
If $x_1+\dots+x_k=n$, with $x_i\geq a_i\geq0$ for all $i$, then 
$$
(x_1-a_1+1)+(x_2-a_2+1)+\dots+(x_k-a_k+1)=n-a_1-a_2-\dots-a_k+k,
$$
is a standard integer composition of $n-a_1-\dots-a_k+k$ into $k$ parts. Moreover, every standard integer composition of  $n-a_1-\dots-a_k+k$ into $k$ parts can be modified a composition of $n$ satisfying the desired restrictions in the obvious way. Thus the number of compositions you are counting is the same as the number of standard integer compositions of  $n-a_1-\dots-a_k+k$ into $k$ parts. From classical results, this number is 
$$
\binom{n-a_1-\dots -a_k+k-1}{k-1}.
$$
Edit: Standard Integer Compositions
A standard integer composition of $n$ into $k$ parts is a sequence of strictly positive integers $(m_1,\dots,m_k)$ with $m_1+m_2+\dots m_k=n$. Note that order matters, i.e. $1+2=3$ and $2+1=3$ are two distinct compositions of $3$ into $2$ parts. It turns out that the number of $k$ compositions of $n$ is $\binom{n-1}{k-1}$; there are several ways to see this. One such way is the "stars and bars" argument, another way is through a bijection between $k$ compositions and $k$ subsets of $\{1,2,\dots,n-1\}$, namely you send $(m_1,m_2,\dots,m_k)$ to the subset $\{m_1,m_1+m_2,\dots,m_1+m_2+\dots+m_{k-1}\}$. 
So once we have established a nice understanding of standard integer compositions, all you have to do is translate your question into one regarding standard integer compositions, which can be done as described above (by subtracting off the $a_i$s. I find this area very interesting, for more info see here: https://en.wikipedia.org/wiki/Composition_(combinatorics) 
A: Write $x_i=a_i+y_i$ with $y_i\geq0$. Then a solution of the original problem amounts to solving
$$y_1+y_2+\ldots+y_k=n':=n-\sum_{i=1}^k a_i$$
in nonnegative integers $y_i$, resp., finding the number of admissible solutions $(y_1,\ldots,y_k)$. This is a standard "stars and bars" problem. The number in question is
$${n'+k-1\choose k-1}\ .$$
A: If you would like to use a physical model to think about this,
set out $k$ numbered bins or boxes in a row, 
and collect a pile of $n$ identical balls.
Your question is then equivalent to, how many different ways can I distribute
the $n$ balls into the $k$ boxes so that 
box $i$ contains at least $a_i$ balls ($a_i \geq 0$) for each $i$
in $\{1,2,\ldots,k\}$?
You have to put at least $a_1$ balls in the first bin,
so you might as well put exactly $a_1$ balls there right away.
Those balls will be there no matter what; you have no choice about that.
Now put exactly $a_2$ balls in the second bin, $a_3$ balls in the third bin,
and so forth, finally placing $a_k$ balls in the $k$th bin.
You now have a pile of $n - a_1 - a_2 - \cdots - a_k$ balls left over
that have not been placed in bins, and complete freedom over which
bins to place them in (since you have already satisfied
the minimum number of balls in each bin).
Each unique arrangement of the remaining $n - a_1 - a_2 - \cdots - a_k$ balls
in the $k$ bins produces a unique arrangement of the original $n$
balls in the $k$ bins, and vice versa.
In how many unique ways can you put the remaining
$n - a_1 - a_2 - \cdots - a_k$
indistinguishable balls in the $k$ numbered bins?
The same number of ways as $m$ indistinguishable balls in $k$ initially empty
numbered bins, where $m = n - a_1 - a_2 - \cdots - a_k$.
There is a well-known formula for counting these ways,
$$\binom{m + k - 1}{k - 1}.$$
The idea of the formula is that you lay out the balls in a line along with
$k - 1$ "walls" that you can place between balls; that is, you have a
sequence of $m + k - 1$ objects, $m$ of one type and $k - 1$ of another,
which can be arranged in $\binom{m + k - 1}{k - 1}$
unique ways, and each of those arrangements gives you a unique way
to decide how many balls to put in each box: put any balls to the left of
the first "wall" in the first box, then the balls between the first and
second "walls" in the second box, and so forth. (The last box gets whatever
balls are to the right of the last "wall".)
But in this case we substitute $m = n - a_1 - a_2 - \cdots - a_k$,
so the number of ways to put the balls in the bins is
$$\binom{n - a_1 - a_2 - \cdots - a_k + k - 1}{k - 1}.$$
