Stars and bars is a solution to many simple counting problems. For example- To find the number of ways one can distribute x number of objects to n number of people.
The solution to this is given by the formula – (x+n-1)C(n-1).
Taking an example question-
Find the number of ways 10 fruits can be distributed to 4 people.
to distribute 10 fruits to 4 people we just need to decide how many fruits go to 3 people the last person will get some number of fruits by default.
• • • • • • • • • • (10 fruits)
we need to divide these fruits in 4 parts for which we require 3 bars
• • •| • • • • •| • |•
• •| • • • |• • • • |•
• |• •| • • |• • • • •
There are multiple different combinations possible, the number of
possible ways in which we can arrange the bars and stars – (number of spots)C(bars)
= (10+3)C(3)
= 13C3
Another variation of the star and bar-
To find the number of positive integral solutions for x1*x2*x3*x4 = 240
Factors of 240 are – 2*2*2*2*5*3
=2^4*5^1*3^1
Assuming powers of x1 as a1 a2 and a3 for 2,5,3
Assuming powers of x2 as b1 b2 and b3 for 2,5,3
Assuming powers of x3 as c1 c2 and c3 for 2,5,3
Assuming powers of x4 as d1 d2 and d3 for 2,5,3
x1=2^a1*3^a2*5^a3
x2=2^b1*3^b2*5^b3
x3=2^c1*3^c2*5^c3
x4=2^d1*3^d2*5^d3
a1+b1+c1+d1=4
using star and bar here –
||| – 3 bars and ••••-4 stars
=>7C3
doing the same for
5 and 3-
for 5- 4C3
for 3-4C3
total number of combinations = 7C3*4C3*4C3