Number of solution of a linear diophantine equation

Question

Let $k>n\ge1$. Let then $x_1,\dots,x_n$ be integers $\ge1$.

How can we compute the number of solution of $$ x_1+\cdots+x_n=k\;\;\;\;\;\;? $$ I think combinatoric could help but I don't know how.

Can somebody help me?

Answer 1

This is a standard problem of stars and bars. Represent each solution as a sequence of stars and bars. $(x_1,x_2,x_3,x_4)=(2,1,3,3)$ for example would be represented as $\star\star\mid\star\mid\star\star\star\mid\star\star\star$. Recognize now that due to the condition that each $x_i$ be at least one that bars cannot be placed next to one another and cannot be placed at the ends. Place your $k$ stars in a row first and then pick which spaces between the stars have bars in them.

A total of $k$ stars will be used. A total of $n-1$ bars will be used. There are $k-1$ spaces between stars available for bars to be in.

There are then $\binom{k-1}{n-1}$ valid sequences of stars and bars. We see that these are in direct bijection with the Diophantine solutions of the system.