Online Class Saturday Aug 1, 2020

Combinatorics - Learning how to count (Day 2)

Problem 1. How many 6 digit numbers are there with at least one odd digit?

Solution: The no. of 6 digit numbers are there with at least one odd digit is the
total no. of 6 digit numbers - the no. of 6 digit numbers with only even digits.
The total no. of 6 digit numbers = 9 × 10 × 10 × 10 × 10 × 10 = 9 × 105.
The no. of 6 digit numbers with only even digits = 4 × 5 × 5 × 5 × 5 × 5 = 4 × 55 .
Therefore, the required counting will be 9 × 105 - 4 × 55 = 887500.

Problem 2. Suppose that 3 students of class I, 4 students of class II and 5

Solution: If the students of same class are to be seated together, then essentially
we would have 3 blocks, one for each class. Now the ordering of these blocks can
be done in 3! ways and within the blocks, we can also permute the students of
that class. Hence the required count will be 3! × 3! × 4! × 5!. (Here blue
corresponds to the permutations within the blocks and red corresponds to the
permutation of the blocks.)

Problem 3. In how many ways can one move from A (0, 0) to B (6, 4) if he is
allowed to move only one step to the right or one step upwards at every move ?
(One sample path is shown in red below.)

Solution: What are the common characteristics of all such paths? Some of you told
me that they all have 10 steps. Can we be a little more precise? All these paths
have 6 right steps and 4 up steps. Thus, each path is essentially a permutation of
6 R’s and 4 U’s. For example, the path shown in the above figure can be coded as:
R R R R U U U R U R. Thus, the number of paths is essentially the number of
permutations of 6 R’s and 4 U’s. The no. of such permutations is 10C4 (see below).

Page 1 of 4
In how many ways can we permute 6 R’s and 4 U’s?
One way of thinking: Among the 10 places in total, we can select 4 places (which
can be in 10C4 ways) to put the 4 U’s and then the remaining 6 places will be filled
up by the 6 R’s. Therefore the no. of such permutations is 10C4.
Another way of thinking: Among the 10 places in total, we can select 6 places
(which can be in 10C6 ways) to put the 6 R’s and then the remaining 4 places will
be filled up by the 4 U’s. Therefore the no. of such permutations is 10C6. This does
not contradict the above, because 10C4 = 10!/6!4! = 10C6.

Problem 4. In how many ways can you permute the letters of the word ‘RUSSEL’?

Solution: If the two S’s were different, then the number of permutations would
have been 6!. But here USLSER and USLSER are the same. In a similar manner, for
any fixed permutation of RUSSEL, we can reshuffle the two S’s, yielding the same
permutation (but they would have been different had the two S’s were different).
Hence, the actual number of permutations should be 6!/2.

Problem 5. In how many ways can you permute the letters of ‘honeybee’?

Solution: If the three e’s were different, then the number of permutations would
have been 8!. But here the three e’s are same, so permuting them results in no
new permutation. Thus, every permutation with 3 identical e’s correspond to 3!
many permutations with 3 distinct e’s. Hence, the actual number of permutations
should be 8!/3!.

Problem 6. (a) In how many ways can you permute the letters of ‘RUSSELL’?

Solution: If the two S’s and the two L’s were different, then the number of
permutations would have been 7!. But here we have two identical S’s and two
identical L’s. Hence we have to divide by 2! and 2!, giving the no. of permutations
to be = 7!/2!2!.

(b) In how many ways can you permute the letters of the word ‘RUSSELL’ such that
the two S’s are not adjacent?

Solution: It equals the total no. of permutations (which is 7!/2!2!) minus the no. of
permutations where the two S’s are adjacent. If the two S’s are to be adjacent we
can consider the ‘SS’ as one block, hence the no. of permutations where the two
S’s are adjacent is given by = no. of permutations of (R,U,SS,E,L,L) = 6!/2!.
Hence the number of permutations of the letters of the word ‘RUSSELL’ such that
the two S’s are not adjacent is given by = 7!/2!2! - 6!/2!.

Page 2 of 4
(c) In how many ways can you permute the letters of the word ‘RUSSELL’ such that
the two L’s are not adjacent?

Solution: Same as above (part (b)).

(d) In how many ways can you permute the letters of the word ‘RUSSELL’ such that
the two L’s are not adjacent and the two S’s are not adjacent?

Solution: This would be given by the total no. of permutations - the no. of
permutations containing SS - the no. of permutations containing LL + the no. of
permutations where SS and LL are both present = 7!/2!2! - 6!/2! - 6!/2! + 5!.
(The last one is calculated in this way: no. of permutations of {R, U, SS, E, LL},
which is 5!.)

(e) In how many ways can you permute the letters of the word ‘RUSSELL’ such that
no two among the L’s and S’s are adjacent (i.e., no SS, SL, LS, or LL)?

Solution: Here S, S, L, L must be placed between the gaps around R, U, and E. First
place the letters R, U, E, which can be done in 3! ways. After placing R, U, and E,
we can place the two S’s and the two L’s in 4!/2!2! ways. Ans: 3! × 4C2 = 36.
Another way of doing the last part:
__ R __ U __ E __
4 gaps, choose two, where S’s will be placed and in remaining two L’s will be
placed, so this can be done in 4C2 ways.

Problem 7. In how many ways can you permute the letters A, B, C, D, E, F, F, G, G,

Solution: A, B, C, D, E, F, F, G, G → __ A __ B __ C __ D __ E __ → 5! × 6C2 × 4C2.

Problem 8. Suppose you go to a shop to buy 5 ice-cream cups. The shop has ice-
cream cups of 3 flavours, say {Chocolate, Mango, Vanilla}. In how many ways can
you buy 5 ice-cream cups? Note that the cups of same flavour are identical.

Solution: Note that once we fix the combination to be chosen, the ice-creams of
that combination can be bought in only one way. For example, the no. of ways we
can buy the combination {M, M, V, V, C} is just 1. So only what matters is the
composition, i.e., how many ice-creams of each flavour are to be chosen.
Now we shall find the total number of such composition. Suppose that the number
of ice-creams of flavours Mango, Chocolate and Vanilla are x, y, and z,
respectively. Then all we need to find is the number of non-negative integer
Page 3 of 4
solutions to the equation x + y + z = 5. (Each solution correspond to a unique
composition.) How to find the number of non-negative integer solutions to the
equation x + y + z = 5? Each solution can be represented as a permutation of 2
sticks and 5 balls, as shown below.

Conversely, each permutation of 2 sticks and 5 balls give us a valid solution (also
shown above). Thus the number of solutions equals the number of ways to
permute 2 sticks and 5 ones, which is given by 7C2 = 7!/2!5!, because among 7
empty places, we have to choose 2 places to put the sticks and the remaining 5
places would be filled up by the balls. Hence the number of ways to buy 5 ice-
creams from the shop is given by 7C2 = 7 × 6/2 = 21.

Here are some problems that you must try at home:

P1. There are 8 CCTV cameras in a shop. Find the number of ON-OFF patterns of
the cameras if at least three cameras have to be ON all the times.
P2. In how many ways can you permute the letters of the word ‘MISSISSIPPI’? In
how many of them no two S’s are adjacent?
P3. Find the number of 6-digit natural numbers whose digits are chosen from the
set {1, 2, 3, 4, 5} and each digit (that appears) appears at least twice. For instance,
123213, 111144 are valid, but 111223 is not.
P4. Suppose 5 friends go to a shop to buy ice-cream cups. The shop has ice-
cream cups of 4 flavours, say {Chocolate, Mango, Vanilla, Strawberry}. In how
many ways can they buy 5 ice-cream cups (1 for each)? Note that the cups of
same flavour are identical.

Counting is best learnt by solving problems on your own. Practice from:

Page 4 of 4