Combinatorics DPP - RACE 5 - COMBINATORICS : MULTINOMIAL THEOREM, DEARRANGEMENT AND EXPONENT OF PRIME NUMBER IN n!

Prerequisite: Stars and bars method and Dearrangements.

Q1. In a bakery 8 different brands of biscuits are available. In how many ways 6 biscuits can be selected if biscuits of same brand are identical.
Solution:
Objects are identical, categories(buckets) are different.
Use stars and bars method here.
n = 6
k = 8
(n+k-1)C(k-1) = 13C7 = 1716

Q2. Find the number of solutions of the equation x + y + z + w = 20 under the following restrictions:

(i) x,y,z,w are whole numbers.
Again stars and bars.
n = 20
k = 4
(24-1)C(3) = 23C3

(ii) x,y,z,w are natural numbers.
Each bucket would get at least one object.
Remaining objects = 16
n = 16
k = 4
19C3

(iii) x and y are odd natural numbers while z & w are even natural numbers.
x = 2a + 1, y = 2b + 1, z = 2c, w = 2d
a,b >= 0 and c,d >= 1
2a + 1 + 2b + 1 + 2c + 2d = 20
=> 2(a+b+c+d) = 18
=> a+b+c+d = 9
Now we can apply stars and bars here but the problem is that c,d start from 1 while a,b start from 0.
Let c' = c - 1, d' = d - 1
a + b + c' + d' = 7
Now all 4 buckets can have 0 elements.
n = 7
k = 4
(7+4-1)C(4-1) = 10C3 = 120

(iv) x > 1, y >= -1, z > 2
x >= 2, y>= -1, z >= 3
x' = x - 2, z' = z - 3, y' = y + 1 => x' >= 0, y' >= 0, z' >= 0
x + y + z + w = 20
=> x - 2 + y + 1 + z - 3 + w = 20 - 4 = 16
=> x' + y' + z' + w = 16 (and each var is zeroable now).
n = 16
k = 4
Answer: (16 + 4 - 1)C(4 - 1) = 19C3

(v) x,y,z,w belong to{1,2,3,...,10}
4 <= x + y + z + w <= 40
Let x' = x-1, y' = y-1, z' = z-1, w' = w-1
=> x' + y' + z' + w' = 16
Total solutions to this (16+4-1)C(4-1) = 19C3
Now we have to subtract the cases when any variable exceeds 10.
Which means that in the modified equation, any variable exceeds 9.
Note that only one variable can exceed 9, else the sum will exceed 16.
Let's say x' >= 10.
Let x'' = x' - 10 => x'' >= 0
x'' + y' + z' + w' >= 6
This has (6+4-1)C(4-1) solutions, which is 9C3.
This has to be counted 4 times due to 4 vars, so 4.9C3
Answer: 19C3 - 4.9C3

Q3. Find the number of positive integral solutions of xyz = 120
Solution:
A wrong way to solve this:

Factors: 2,2,2,3,5
So in total there are 5 numbers which need to be distributed in x,y,z.
If they receive 0 numbers, it means they are 1.
For e.g.
120.1.1

So stars and bars with n  = 5 and k = 3
(5+3-1)C(3-1) = 7C2 = 21

What's the problem here?
Problem is that we are treating the factors (2,2,2,3,5) as identical objects which is not true.
Remember in stars and bars, 'n' identical objects are distributed in 'k' distinct buckets.
So here we have to apply Stars and bars 3 times on each factor separately.
For 2, we have n = 3, k = 3 so (3+3-1)C(3-1)  = 5C2 = 10 ways.
For 3, we have n = 1, k = 3 so (1+3-1)C(3-1)  = 3C2 = 3 ways.
For 5, we have n = 1, k = 3 so (1+3-1)C(3-1)  = 3C2 = 3 ways.
Total: 10*3*3 = 90 ways.

Q4. A person throws a fair dice four times. In how many ways he can score a total of 16.
Solution:
x + y + z + w = 16
1 <= x,y,z,w <= 6
Let x' = x-1 and similarly for others, so:
x' + y' + z' + w' = 12

Let's first find total possible solutions and then we will discard the cases when one or more variables > 6.
Total solutions: (12+4-1)C(4-1) = 15C3 = 455

Now the invalid case will happen when one or more of the original vars >= 7
Or for the new vars >= 6
Let's say x' >= 6 and let x'' = x' - 6, so x'' >= 0
x'' +  y' + z' + w' = 6
Number of ways for the above: (6+4-1)C(4-1) = 9C3 = 84
But this can happen 4 times: 4*84 = 336

There is another way for illegal cases to creep in. When 2 vars >= 6. That will happen when 2 vars are exactly 6. This can happen in 4C2 = 6 ways. Now these cases were counted twice in our last calculation. Because we did this for each variable. So we have to subtract it from 336.

So total illegal = 336 - 6 = 330.
Final answer: 455 - 330 = 125.

Q5. There are n seats in a classroom. A group of 'n' students is assigned seats for 2 subjects in this classroom. In how many different ways can the students sit in the class so that no student sits on the same seat for both subjects.
n!. Dn (Derangements)
Dn = !n = n!(1 - 1/1! + 1/2! - 1/3!..... + (-1)^n.1/n!)

Q6 - A person writes letters to five friends and addresses on the corresponding envelopes. In how many ways can the letters be placed in the envelopes so that

(i) All letters are in the wrong envelopes.
!5 = (1 - 1/1! + 1/2! - 1/3! + 1/4! - 1/5!) = 44

(ii) At least three of them are in the wrong envelopes.
Exactly 3 wrong: 5C3*D3 = 10*2 = 20
Exactly 4 wrong: 5C4*D4 = 5*9 = 45
Exactly 5 wrong: 5C5*D5 = 44

Total: 109

Q7.
(i) Find the exponent of 3 in 50!
1 3 1
2 6 1
3 9 2
4 12 1
5 15 1
6 18 2
7 21 1
8 24 1
9 27 3
10 30 1
11 33 1
12 36 2
13 39 1
14 42 1
15 45 2
16 48 1
We have total 16 numbers divisible by 3.
Each of them has one 3.
Additionally, every third one has an extra 3.
Every ninth one has 2 extra 3's.
If this continues, every 27th number would have 3 extra 3's.
So to put it clearly:
[50/3] + [50/9] + [50/27] = 16 + 5 +1 = 22

(ii) Find the exponent of 12 in 15!
Number of 3's = [15/3] + [15/9] = 5 + 1 = 6
There are six 3's.
Similarly to count Number of 2's:
[15/2] + [15/4] + [15/8] = 7 + 3 + 1 = 11
From 11 2's we can make 5 fours.
From five 4's and six 3's we can make five 12's.
Answer: 5

(iii) Find number of zero's in the end of 100!
We have to find Number of 2's and 5's.
Number of 5's = [100/5] + [100/25] = 24.
Number of 2's = [100/2] + [100/4] + [100/8] + 100/16 + 100/32 + 100/64 = 50 + 25 + 12 + 6 + 3 + 1 = 97
Number of zeroes = 24 = min(24,97).

Q8. There are 100 different books in a shelf. Number of ways in which 3 books can be selected so that no two are neighbors is:
Solution:
Let's say you have already picked those 3 books and now you want to put them back.
If those 3 books were not neighbors then we have to put them in gaps around those 97 remaining books.
98C3 is the answer.

Q9. If x1, x2, x3 are the whole numbers and gives remainders 0,1 and 2 when divided by 3, then the total number of solutions of the equation x1 + x2 + x3 = 33 are:

Solution:
x1 = 3x, x2 = 3y + 1, x3 = 3z + 2 where x,y,z are whole numbers.
3(x+y+z) = 30
x+y+z = 10
Stars and bars => (10+3-1)C(3-1) = 12C2 = 66

Q10. The number of ways in which 10 identical apples and 8 identical mangoes can be distributed among 6 children such that each child receives at least one fruit of each species, is:
Solution:
Stars and bars has to be applied twice.
For apples:  k = 6, n = 10 - 6 = 4 => (4+6-1)C(6-1) = 9C5 = 126
For mangoes: k = 6, n = 8-6 = 2 => (6+2-1)C(6-1) = 7C5 = 21
Final: 126*21 = 2646

Q11. Number of integral solutions of the equation XYZ = 216, are:
Solution:
Factors: 2^3*3^3
Now we have to apply stars and bars once each for 2's and 3's.
k = number of buckets = 3(X,Y,Z)
n = 3 for 2's
(3+3-1)C(3-1) = 5C2 = 10
Similarly for 3's.
Patterns so far: 10*10 = 100.
Now we need to add sign patterns.
If X,Y,Z all positive then final sign: +, 3C3
If 2 of them negative then final sign: +, 3C2 = 3
So total number of ways = 1 + 3 = 4.
Finally: 4*100 = 400.

Q12. Six cards are drawn one by one from a set of unlimited number of cards, each card is marked with numbers –1, 0, or 1. Number of different ways in which they can be drawn if the sum of the numbers shown by them vanishes, is:
Solution:
Case 1: All zeroes: 1
Case 2: 1,-1,0,0,0,0: 6!/4!
Case 3: 1,-1,1,-1,0,0:6!/2!2!2!
Case 4: 1,1,1,-1,-1,-1:6!/3!3!
Total: 1 + 30 + 90 + 20 = 141

Q14. For the positive numbers {1,2,3,....(n–1), n} there are 396 different dearrangements in which the numbers 1,2,3,4 appear in the first 4 positions. Then the value of n is:
Solution:
For the first 4 scrambled positions, D4 = 9.
Total dearrangements = D4*Dn-4 = 396 => Dn-4 = 44
D5 = 44 => n-4 = 5 => n = 9.

Q15. There are six letters L1, L2, L3, L4, L5, L6 and their corresponding six envelopes E1, E2, E3, E4, E5, E6. Letters having odd value can be put into odd value envelopes and even value letters can be put into even value envelopes so that no letter goes into the right envelope, then number of arrangements is equal to:
Solution:
D3*D3 = 4

Q15. 4 balls numbered 1, 2, 3, 4 are to be placed in 5 boxes numbered 1, 2, 3, 4, 5, such that exactly one box remains empty & no ball goes to its own numbered box. The number of ways in which this can be done is:
A very simple solution:
Assume there are 5 balls numbered 1,2,3,4,5.
Now there are 2 cases:
Case 1: Ball 5 goes into box 5 => D4 (since we need to dearrange only 4 balls now).
Case 2: Ball 5 does NOT go into box 5 => D5 (since we need to dearrange all 5 balls now).
Answer: D4 + D5 = 9 + 44 = 53.

A very long solution:
There are 5 ways to choose boxes:
Case 1: 1,2,3,4 => D4 = 9
Case 2(other 3 cases are also same): 1,2,3,5
Case 2a: 1,2,3 go into 1,2,3 and 4 goes to 5 => D3 = 2
Case 2b(2c,2d are also same):
1,2,4 go into 1,2,3 and 3 goes to 5.
Now if 1,2 go into 1,2 there is 1 way.
if 1,2 go into 1,3 there is 1 way.
if 1,2 go into 2,3 there is 1 way.
Total: 3 ways.
Case 2 total = 2 + 3*3 = 11
Case 2,3,4,5 total = 44
Case 1 + Case 2,3,4,5 = 53 

Q16. Number of zero's at the end of 2002C1001 is:
Solution:
2002!/1001!1001!
We should ideally count number of 5's and 2's in each number but it's enough to count 5's because that will be lesser.
Number of 5's in 1001  = [1001/5] + 1001/25 + 1001/125 + 1001/625 = 200 + 40 + 8 + 1 = 249

Number of 5's in 2002  = [2002/5] + 2002/25 + 2002/125 + 2002/625  = 400 + 80 + 16 + 3 = 499
499 - 249*2 = 1
Answer: 1