$$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.

  • $\begingroup$ Suppose if $x_{k}$ must be 1 or larger. How can you write that out? $\endgroup$ – GivenPie Jan 24 '14 at 4:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.