Hi,
Stars and Bars theorem come up with the solution to the distribution of identical items into distinct blocks. Stars and Bars doesn't refer to the name of mathematicians instead it refers to the concept that makes complex questions trivial. If you have come across this theorem for first time it might be quite confusing for you to grasp it in one go.But Once you get the concept it won't take you long to tackle problems based on this theorem.
Stars And Bars theorem
To begin with,Read the example and Understand what problem Stars and Bars actually solves .
Example 1 : Suppose you want to distribute 3 identical balls(same Colour balls) among 3 diffrent containers A,B and C and all the containers are of different colours.Now you have to find the numbers of ways by which you can complete this task.Also the condition is that each container must contain either 0 Ball or greater than 0 Ball.
solution : Let's use traditional method to distribute 3 identical balls into three 3 distinct containers we will also be solving it through applying formula Once we discuss about.
The number of Possible distributions for container A ,B and C are:
Container A = 0 , B= 0 and C = 3
Container A= 0 , B= 3 and C=0
Container A= 3 , B= 0 , and C = 0
Container A= 0, B= 1, and C =2
Container A =1 , B = 0 and C=2
Container A = 2, B= 0 and C = 1
Container A = 2 , B =1 and C =0
Container A = 0, B = 2 and C =0
Container A = 1, B =2 and C = 0
Container A = 1 , B = 1 and C =1
If we count all the above distributions they all sum up to 10. Now you may have got the Idea about what we want to solve.
From our calculation we have 10 ways to distribute 3 identical balls into 3 distinct containers
This time we had only 3 identical balls and 3 distinct containers but think what if you have 50 ,100 or higher number of balls and you have to distribute them into 3 or more than three distinct containers then it is formidable task to do it through traditional method. We need a quick approach to find a solution to this problem and Stars and Bars is there to tackle it.
Why It Named Stars and Bars
Considering the above example we had three identical balls and 3 distinct containers AB and C.
In stars and bars these 3 identical balls are like three stars and 3 distinct containers equal 2 Bars ( || ) as 2 bars create 3 distinct containers or three columns.
Let's three stars are denoted by N
Number of containers required = k
So the number of ways to distribute 3 identical balls into the three containers
= \( {}^{N+k-1}C_{k-1} \)
This formula is applicable only if each container contains either zero or greater than zero balls.
The formula gets changed slightly if the condition changes. If the condition is
- Each container contains at least one ball which means no container is to be allowed zero ball.
The Number of ways to distribute N balls into three distinct containers provided each container takes at least one ball
= \( {}^{N-1} C_{k-1} \)
Now it is time to put our learning into practice and see how Stars and Bars is instrumental in the solution for several problems.
Solution For The Problem in Example 1
In example 1 we have the number of identical balls(N) = 3
Number of containers(k) = 3
Condition I : A \( \ge \) 0, B \( \ge \) 0, C \( \ge \) 0,
The number of distributions = \( {}^{3+3-1}C_{3-1} \)
= \( {}^{5}C_{2} \)
= \( 5! \times 4 \times 3! \over {2! \times 3! } \)
= 10 ways.
The result is the same as we got from the traditional method.
Condition II : Now the condition is Each container contains at least one ball i.e No container is to be empty.
In mathematical terms
A \( \ge \) 1, B \( \ge \) 1, C \( \ge \) 1,
In this case, we can see from our traditional method, There is only one way. If each each container has one ball.
A= 1 ,B = 1 and C = 1.
Using the formula:
Number of identical balls (N)= 3
Number of distinct containers(k) = 3
= \( {}^{N-1} C_{k-1} \)
= \( {}^{3-1} C_{3-1} \)
= \( {}^{2} C_{2} \)
= 1 way
Number of Integer Solutions Using Stars and Bars
To find the number of Integer Solutions for a linear equation with two or more than two variables is One of the very interesting applications of Stars and Bars theorem. Let's go at with an example that will make sense to you.
Example: Find the number of Integer Solutions for the equation \( x +y =12 \) provided \( x \ge 1, y \ge 1\)
Ans : Number of identical things (N) = 12
Number of different containers= 2
The number of Integer Solutions for the given equation is :
= \( {}^{12-1} C_{2-1} \)
= \( {}^{12} C_{1} \)
= \( 12! \over {1! 11!} \)
=12