Stars and bars method - combinatorics
If we have to distribute n identical objects into k distinct buckets, we use stars and bars.(AKA Fictitious method)
Note that objects are identical but buckets are distinct.
Assume that objects are stars and buckets are bars.
To divide the objects into k buckets we have to place k-1 bars among the stars so that they get divided into k groups.
Here we are assuming that a bucket can have 0 objects(stars) also.
For e.g. 3 bins and 4 objects.
*|*|** => the 3 bins have 1,1,2 objects each.
||**** => the 3 bins have 0,0,4 objects each.
The formula to count the ways of doing so is:
$$ {}^{n+k-1}C_{k-1} $$
Why?
Because there are n + k - 1 total slots including stars and bars.
We have to figure out number of ways to arrange them.
Simplest way to do so is to choose k - 1 slots from total available slots.
And that gives us the above formula.
So if you have to divide 6 apples into 3 kids:
$$ {}^{6+3-1}C_{3-1} $$ which is:
$$ {}^{8}C_{2} $$
Now, what if there is a constriant that each bucket gets at least a certain number of objects?
For e.g. in the above problem, each kid should get at least one apple.
Then first allocate one apple to each and apply stars and bars on the remaining objects.
So here we will have 3 apples remaining after giving 1 to each kid.
And final number of ways:
$$ {}^{3+3-1}C_{3-1} $$ which is:
$$ {}^{5}C_{2} $$ There is another way to see the solution for the case when each bucket has to get at least one object.
Now the bars have to be placed between the objects. They can't be placed on the edges on left and right.
So there are only n-1 slots available for k-1 bars.
Which is:
$$ {}^{n-1}C_{k-1} $$ But keep in mind this is specifically for the case when each bucket has to get at least one object.
But what if the n objects are not identical .
Then we try to solve using other approaches.
For e.g. distribute 6 apples among 3 kids when all the apples are distinct.
Case 1: When one or more kids can get 0 apples.
Now each apple can be given to any of the 3 kids. So answer is 3*3*3*3*3*3 = 3^6 = 729.
Case 2: When each kids has to get at least one apple.
Now subtract those cases when 1 or more kids get 0 apples.
Case 2a: When 1 kid gets 0 apples.
$$ {}^{3}C_{1}.2^6 $$ because there are 3 ways to choose 1 kid who gets 0 apples and each apple has only 2 kids to choose from.
Case 2b: When 2 kids get 0 apples.
$$ {}^{3}C_{2}.1^6 $$ because there are 3 ways to choose 2 kids who get 0 apples and each apple has only 1 kid to choose from.
Finally:
$$ 3^ 6 - {}^{3}C_{1}.2^6 - {}^{3}C_{2}.1^6 = 540 $$
More example problems:
Note that objects are identical but buckets are distinct.
Assume that objects are stars and buckets are bars.
To divide the objects into k buckets we have to place k-1 bars among the stars so that they get divided into k groups.
Here we are assuming that a bucket can have 0 objects(stars) also.
For e.g. 3 bins and 4 objects.
*|*|** => the 3 bins have 1,1,2 objects each.
||**** => the 3 bins have 0,0,4 objects each.
The formula to count the ways of doing so is:
$$ {}^{n+k-1}C_{k-1} $$
Why?
Because there are n + k - 1 total slots including stars and bars.
We have to figure out number of ways to arrange them.
Simplest way to do so is to choose k - 1 slots from total available slots.
And that gives us the above formula.
So if you have to divide 6 apples into 3 kids:
$$ {}^{6+3-1}C_{3-1} $$ which is:
$$ {}^{8}C_{2} $$
Now, what if there is a constriant that each bucket gets at least a certain number of objects?
For e.g. in the above problem, each kid should get at least one apple.
Then first allocate one apple to each and apply stars and bars on the remaining objects.
So here we will have 3 apples remaining after giving 1 to each kid.
And final number of ways:
$$ {}^{3+3-1}C_{3-1} $$ which is:
$$ {}^{5}C_{2} $$ There is another way to see the solution for the case when each bucket has to get at least one object.
Now the bars have to be placed between the objects. They can't be placed on the edges on left and right.
So there are only n-1 slots available for k-1 bars.
Which is:
$$ {}^{n-1}C_{k-1} $$ But keep in mind this is specifically for the case when each bucket has to get at least one object.
But what if the n objects are not identical .
Then we try to solve using other approaches.
For e.g. distribute 6 apples among 3 kids when all the apples are distinct.
Case 1: When one or more kids can get 0 apples.
Now each apple can be given to any of the 3 kids. So answer is 3*3*3*3*3*3 = 3^6 = 729.
Case 2: When each kids has to get at least one apple.
Now subtract those cases when 1 or more kids get 0 apples.
Case 2a: When 1 kid gets 0 apples.
$$ {}^{3}C_{1}.2^6 $$ because there are 3 ways to choose 1 kid who gets 0 apples and each apple has only 2 kids to choose from.
Case 2b: When 2 kids get 0 apples.
$$ {}^{3}C_{2}.1^6 $$ because there are 3 ways to choose 2 kids who get 0 apples and each apple has only 1 kid to choose from.
Finally:
$$ 3^ 6 - {}^{3}C_{1}.2^6 - {}^{3}C_{2}.1^6 = 540 $$
More example problems:
Q1 - 10 identical coins, 4 beggars = 13C3
Q2 - 100 identical coins, 5 beggars, at least 6 coins per beggar = 74C4
Q3 - 30 marks to be allotted to 8 questions, each question has at least 2 marks = 21C7
Q4 - Integral solutions of x + y + z = 2028
(i) x,y,z are whole numbers:
2030C2
2030C2
(ii) natural numbers
2027C2
2027C2
(iii) x >= 1, y>= 2, z >= 3
2024C2
2024C2
(iv) x >= -3, y >= -2 z >= 4
2031C2
Q5 - Number of non negative integral solutions of
x + y + z <= 2026
Introduce w so that: x + y + z + w = 2026
So 2029C3
Another way to solve that is
x + y + z = 0 => 2C2
x + y + z = 1 => 3C2
x + y + z = 2 => 4C2
......
x + y + z = 2026 => 2028C2
And now add all these. But to simplify this sum you need to sum formulae
Q6 - Natural solutions of x + y + z < 2026:
=> x + y + z <= 2025
Add w>=0 such that:
x + y + z + w = 2025
Let x' = x - 1, y' = y - 1, z' = z - 1
=> x' + y' + z' + w = 2022
Now all are zeroable
=> (2022 + 4 - 1)C(4 - 1) = 2025C3
Introduce w so that: x + y + z + w = 2026
So 2029C3
Another way to solve that is
x + y + z = 0 => 2C2
x + y + z = 1 => 3C2
x + y + z = 2 => 4C2
......
x + y + z = 2026 => 2028C2
And now add all these. But to simplify this sum you need to sum formulae
Q6 - Natural solutions of x + y + z < 2026:
=> x + y + z <= 2025
Add w>=0 such that:
x + y + z + w = 2025
Let x' = x - 1, y' = y - 1, z' = z - 1
=> x' + y' + z' + w = 2022
Now all are zeroable
=> (2022 + 4 - 1)C(4 - 1) = 2025C3
Comments
Post a Comment