divisibility of number of solutions of $x_1+\cdots+x_k=n$ I observed that the number of solutions in positive integers $x_1,\ldots,x_k$ of 
$$x_1+\cdots+x_k=n$$
for fixed $k$ and $n$ is always a multiple of $k$ as long as $\gcd(k,n)=1$. For example,
$$6=2+1+1+1+1,$$
$$6=1+2+1+1+1,$$
$$6=1+1+2+1+1,$$
$$6=1+1+1+2+1,$$
$$6=1+1+1+1+2,$$
i.e. there are $5$ solutions. Is there any combinatorial rationale behind this? (i.e. combinatorial argument, e.g., via bars and stars?)
 A: Let $S$ be the set of all positive solutions of the equation 
$x_0+x_1+\cdots+x_{k-1}=n$. We show by a combinatorial argument, without even counting $S$, that if $k$ and $n$ are relatively prime, then $k$ divides the number of elements of $S$. 
We will say that two elements of $S$ belong to the same family if one is a cyclic permutation of the other. We show that if $k$ and $n$ are relatively prime, then each family has $k$ distinct members. From this it follows that $k$ divides the number of solutions. 
So we need to show that a non-trivial cyclic permutation of a solution yields a different solution. Let $A=(a_0,a_1,\dots,a_{k-1})$ be a solution, and consider the solution $A_t=(a_t,a_{t+1}, \dots, a_{t+k-1})$, where the indices are reduced modulo $k$. 
Suppose that for some $t$, with $1\le t\le k-1$, we have $A_t=A$. Then there is a smallest such $t$, and this $t$ divides $k$. Let $k=dt$. If $k\ne 1$, we have $d\gt 1$. 
Since $A_t=A$, we have $n=d(a_0+\cdots+a_{t-1})$. It follows that $d$ divides $n$, contradicting the fact that $k$ and $n$ are relatively prime.  
Remark: To visualize, imagine the numbers $a_0,a_1,\dots,a_{k-1}$ written around a circle. Two solutions belong to the same family if one can be obtained from the other by a rotation.  
A: The stars-and-bars argument gives us the formula $\binom{n-1}{k-1}$ for the number of positive solutions.
Comparison of this with the formula for $\binom{n}{k}$ shows that if gcd$(n,k)= 1$, then we must have $k$ dividing $\binom{n-1}{k-1}$:
$$ \binom{n}{k} = \frac{n}{k} \binom{n-1}{k-1} $$
A: You are interested in the number of ordered partitions (a.ka. compositions) of $n$ into $k$ parts. See http://en.wikipedia.org/wiki/Composition_(combinatorics)#Number_of_compositions
It tells that this number is $\binom{n-1}{k-1}=\frac{(n-1)!}{(k-1)!(n-k)!}$.
So you study divisibility of these numbers.
