How to use stars and bars?

How to use the stars and bars method?

Say I want to find number of combinations I can get with $x_1+x_2+x_3+x_4=22$, where $x_i\in\mathbb{N}$.

Is this the correct time to apply the method?

This is being repurposed in an effort to cut down on duplicates, see here:

Coping with abstract duplicate questions

and here: List of abstract duplicates

• Do the $x_i$ need to be all positive, or just non-negative? – Namaste Aug 27 '14 at 11:39
• Sorry, yes they are natural numbers – Partly Putrid Pile of Pus Aug 27 '14 at 11:41

Yes, the Stars-and-Bars approach works great here, but you should know that there are two "versions" of the Stars-and-Bars approach. In both versions, we look for the number of distinct integer solutions to an equation such as yours.

In the first version, we require that every $x_i$ must be a positive integer.

In the second version, the restriction eases to include all non-negative $x_i$.

So, for example in your case, $x_1= 0, x_2=9, x_3=0, x_4=13$ would be one distinct solution in the second version, but would not be a solution in the first version.

I. positive integers $x_i$

For any pair of positive integers n and k, the number of distinct k-tuples of positive integers whose sum is $n$ is given by the binomial coefficient $${n - 1\choose k-1}.$$

In your case, $k = 4, n=22$. So the number of distinct solutions $(x_1, x_2, x_3, x_4)$ where the $x_i \in \mathbb Z, x_i>0$ is given by $$\binom{22-1}{4-1} = \binom{21}{3} = \frac{21!}{3!18!} = 1330$$

II. non-negative integers $x_i$

For any pair of natural numbers n and k, the number of distinct k-tuples of non-negative integers (which includes the possibility that one or more of the $x_i$ are zero) whose sum is $n$ is given by the binomial coefficient $$\binom{n + k - 1}{n} = \binom{n+k-1}{k-1}.$$

In your problem, $k = 4, n = 22.$ Here, the distinct solutions $(x_1, x_2, x_3, x_4)$ will include those from $I.$, but also allows 4-tuples in which one or more of the $x_i$ are zero: $x_i \in \mathbb Z, x_i\geq 0$.

$$\binom{22 + 4 -1}{22} = \binom{25}{22} = \dfrac{25!}{22!3!} = 2300$$

• Could you help me with my newer stars and bars problem? Noone has seen it – Partly Putrid Pile of Pus Aug 28 '14 at 12:52
• Isn't the formula (n+k-1) choose k and not choose n? The equivalent would be (n+k-1) choose (n+k-1-k = n-1)? – inggumnator Feb 21 '15 at 22:54
• See how I've defined n, k. See Wikipedia – Namaste Feb 21 '15 at 23:36
• @inggumnator No, sorry. I think you're mixing up $n$ and $k$. The desired sum is $n$; $k$ is the number of $x_i$ (variables) whose sum is $n$. Go to the link I've posted above to re-educate yourself. Note that $$\binom{n+k-1}{n} = \binom{n+l -1}{k-1}$$ – Namaste Dec 2 '16 at 22:39
• How did you decide what is $n$ and what is $k$? – Abcd Dec 18 '17 at 8:55

The star method: consider 22 balls and 3 separations (because you have 4 boxes). I denote $*$ for the balls and $\Big |$ for the separation. Then it's the number of permutation of:

$$\left\{\underbrace{*\ *\ \cdots *\ }_{22\ balls}\Big|\hspace{0.5cm}\Big|\hspace{0.5cm} \Big|\hspace{0.5cm}\right\}$$

There is $25!$ permutations but the permutation of the balls together and the permutations of the separation together doesn't give a new combinaison, so you have to divide $25!$ by $3!22!$ and it gives $$\frac{25!}{3!22!}=\binom{25}{3}$$ different solutions.

• To me, $\mathbb N=\{0,1,2,3,...\}$ and so $0\in\mathbb N$. If $0$ wouldn't be included, he would write $x_i\in\mathbb N^*$. – idm Aug 27 '14 at 13:30
• @idm Did you know how to solve my newest question? It is a continuation of this one – Partly Putrid Pile of Pus Aug 28 '14 at 8:35
• What is the new question ? I don't see it. – idm Aug 28 '14 at 8:37
• – Partly Putrid Pile of Pus Aug 28 '14 at 8:43

How to use the stars and bars method?

For $x_i\ (i=1,2,3,4)\in\mathbb N$, we have $$x_1+x_2+x_3+x_4=22\iff (x_1-1)+(x_2-1)+(x_3-1)+(x_4-1)=18.$$

Here, note that $x_i-1\ (i=1,2,3,4)$ are non-negative integers.

Choosing $4-1=3$ places (for bars) from $18+(4-1)$ places (for bars and stars) leads the answer is $\binom{18+(4-1)}{4-1}=\binom{21}{3}=1330.$

• Why does your answer differ to that of idm? – Partly Putrid Pile of Pus Aug 27 '14 at 12:28
• @user1341841914820412812412: If I'm note mistaken, idm thinks that $x_i$ are non-negative integers. – mathlove Aug 27 '14 at 12:30
• So he has permitted $0$, and you have not? – Partly Putrid Pile of Pus Aug 27 '14 at 12:30
• @user1341841914820412812412: Yes, exactly. – mathlove Aug 27 '14 at 12:30
• That's fine, having the contrast is actually quite nice. – Partly Putrid Pile of Pus Aug 27 '14 at 12:32