Stars and Bars – An Intuitive Explanation

Clasic Problem

The classic Stars and Bars problem asks:
Given n identical items (stars) and r boxes, in how many ways can you distribute the items among the boxes?
There are no restrictions — any box can have zero or more items.

Think of it as N stars (5 in this example). Now, if you use 2 sticks to act as barriers between stars, it will divide the stars into 3 regions, depending on the placement of the barriers. We can assume the stars in each region are stars in the boxes. so if we have to distribute into 3 boxes we need 2 sticks to divide into 3 regions; consequently, to divide into r regions we would need r-1 sticks.

Now to find the number of ways we can just permutate all of these by (n+r-1)! and then remove the repetitive permutations by dividing by = $$$(n!)(r-1)!$$$.

So the Number of ways becomes = $$$\frac{(n+r-1)!}{n!(r-1)!}$$$.

Now, we can also represent this with the equation = $$$x_1 + x_2 + x_3 ... x_r = n$$$ where $$$x_i$$$ represents the number of stars $$$ith$$$ box got and in this case $$$ 0 \lt = x_i$$$, and the solution for this is $$$\frac{(n+r-1)!}{(n!)(r-1)!}$$$.

stars and bars with lower bounds :

Keeping the above formula in mind, now what if, there is a constraint saying we cannot have any box with less than $$$l$$$ $$$(l \lt = n)$$$ stars. which means now constraint on $$$x_i$$$ is $$$ l \lt = x_i $$$, so to solve this now we can use substitution, we can say $$$x_i = y_i + l$$$ where $$$ 0 \lt = y_i$$$.

so if we substitute this in the equation $$$x_1 + x_2 + x_3 .. x_r = n$$$ we get $$$y_1 + y_2 + y_3 .. y_r = n - r*l$$$

so the solution is $$$\frac{(n - r(l-1)-1)!}{(n - r*l)!(r-1)!}$$$.

stars and bars with upper bounds :

Now what if there is a constraint saying we cannot have any box with more than $$$l$$$ $$$(l \lt = n)$$$ stars. which means now the constraint on $$$x_i$$$ is $$$ x_i \lt = l $$$, so to solve this now becomes little tricky. for simplicity we can assume we have r = 3. so $$$x_1 + x_2 + x_3 = n$$$

We can calculate the solution for this with $$$\frac{(n+r-1)!}{n!(r-1)!}$$$ and substract =

• (case when $$$x_1 \gt l$$$)
• (case when $$$x_2 \gt l$$$)
• (case when $$$x_3 \gt l$$$)

and add to compensate for double substraction :

• (case when $$$x_1$$$ and $$$x_2$$$ > l)
• (case when $$$x_1$$$ and $$$x_3$$$ > l)
• (case when $$$x_2$$$ and $$$x_3$$$ > l)

Subtract to compensate for addition :

• (case when $$$x_1$$$ and $$$x_2$$$ and $$$x_3$$$ > l)

How to calculate Cases =

eg - when $$$x_1 \gt l$$$ : $$$y_1 = x_1 - (l+1)$$$ since $$$x_1 \gt l$$$ (ie) $$$x_1 \gt = l+1$$$ so $$$y_1 \gt = 0$$$

$$$x_1 + x_2 + x_3 = n$$$

$$$y_1 + x_2 + x_3 = n - (l + 1)$$$

So $$$n$$$ will become $$$n - (l+1)$$$

So the Number of ways becomes = $$$\frac{(n - (l + 1)+r-1)!}{(n - (l + 1))!(r-1)!}$$$. = $$$\frac{(n - l + 1)!}{(n - (l + 1))!(2)!}$$$

similarly you can calculate for case 2 and 3.

for case 4 5 and 6 :

$$$n$$$ will become $$$n - 2*(l+1)$$$ so: $$$\frac{(n - 2*l)!}{(n - 2l -2))!(2)!}$$$

For case 7 : $$$n$$$ will become $$$n - 3*(l+1)$$$ so: $$$\frac{(n-3l-1)!}{(n-3l-3)!(2)!}$$$.

Hence —

• Case 1,2,3 substract : $$$\frac{(n - l + 1)!}{(n - (l + 1))!(2)!}$$$
• Case 4,5,6 add : $$$\frac{(n - 2*l)!}{(n - 2l -2))!(2)!}$$$
• Case 7substract :$$$\frac{(n-3l-1)!}{(n-3l-3)!(2)!}$$$.

Here is a problem that uses this Approach — Link