25
$\begingroup$

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

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

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

$\endgroup$
  • $\begingroup$ Could you help me with my newer stars and bars problem? Noone has seen it $\endgroup$ – Partly Putrid Pile of Pus Aug 28 '14 at 12:52
  • 1
    $\begingroup$ 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)? $\endgroup$ – inggumnator Feb 21 '15 at 22:54
  • $\begingroup$ See how I've defined n, k. See Wikipedia $\endgroup$ – Namaste Feb 21 '15 at 23:36
  • 1
    $\begingroup$ @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}$$ $\endgroup$ – Namaste Dec 2 '16 at 22:39
  • 1
    $\begingroup$ How did you decide what is $n$ and what is $k$? $\endgroup$ – Abcd Dec 18 '17 at 8:55
16
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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^*$. $\endgroup$ – idm Aug 27 '14 at 13:30
  • $\begingroup$ @idm Did you know how to solve my newest question? It is a continuation of this one $\endgroup$ – Partly Putrid Pile of Pus Aug 28 '14 at 8:35
  • $\begingroup$ What is the new question ? I don't see it. $\endgroup$ – idm Aug 28 '14 at 8:37
  • $\begingroup$ @idm math.stackexchange.com/questions/911618/… $\endgroup$ – Partly Putrid Pile of Pus Aug 28 '14 at 8:43
4
$\begingroup$

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

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