# How many solutions are there in this equation?

$$x_{1}+...+x_{k}=n$$ Let $n$ and $k$ be integers with $n \geq k$ and $x_{k} \geq 1$ and are all integers.

all x values are equal or larger than 1

I have my proof here, can someone verify it. I feel like I didn't subtract all the possible ways that a bit string 1 can be next to a bit string one. Anyways here my proof:

In order to solve this problem, we can present our equation $x_{1}+x_{2}+x_{3}=n$ as bit strings. I will allocate the following:\ Let $S = x_{1},..,x_{k}$ be the set of $k$ amount of zeros for each $x_{k} \geq 1$.\ Since all $x$ variables are greater than zero, I will use bit string 1's to separate each $x_{k}$ value. The amount of 1's must always be $k-1$ since $x_{k} \geq 1$. \ The sum of my $x$ values must always be greater or equal to the amount of $x_{k}$.\ Now choose all the possible you can sum up $n$. Another way to look at this is to choose all the possible way I can arrange my ones as we know there must be at least one zero bit string between any one. I have to eliminate the possibility by choosing a 1 in the front or back of my bit string, therefore taking away 2 possible slots in my bit string. This will decrease the available slots in my bit string to $k-2$. The size of my bit string should be $n+k-1$, for the total $n$ zeros plus $k-1$ amount of ones:$${n+k-1 \choose k-2}$$ The formula above shows the number of ways I can choose $k-2$ positions (no ones at the start and end of my bit string) from a $n+k-1$ length bit string.

This is called an integer partition of $n$. Specifically, what you're looking at is a combinatorial composition. The number of such compositions is ${n-1 \choose k-1}$.
For weak compositions, which are compositions in which $x_k$ is allowed to equal $0$, the number of compositions is ${n+k-1 \choose k-1}$.
I'm not sure if I follow your bit-string proof (try to be more clear/formal), but you come close --- it seems like you've messed up in two parts though: you appear to calculate the number of weak compositions, not the number of compositions s.t. $x_k \geq 1$. You're also off with $k-2$: it should be $k-1$. Try to make your proof more clear, and then the mistake should become apparent.
• Suppose if $x_{k}$ must be 1 or larger. How can you write that out? – GivenPie Jan 24 '14 at 4:32