6.4 Selecting identical elements

Identical elements are those that cannot be distinguished from one another. The different selections will be the different number of elements that we could select.

For instance, from $\bm{n}$ identical elements we can select $0$ elements, $1$ element, $2$ elements, ..., $n$ elements. As selecting $0$ elements is also a way, we can select from $n$ identical elements in $\bm{(n + 1)}$ ways.

If $\bm{1}$ or more items are to be selected from $\bm{n}$ identical elements, then we can select in $\bm{n}$ ways.

In other words, from $\bm{n}$ identical elements, the number of ways to make
- $0$ or more selections is $\bm{n + 1}$ ways; and
- 1 or more selections is $\bm{n}$ ways.

The following example is for selecting from $1$ set of identical elements.

Example 46

A bag contains $8$ identical red balls. In how many different ways can
(I) John pick balls from the bag?
(II) Josie pick balls from the bag, such that she picks at least $1$ ball?

Solution

Case I: John can pick $0, 1, 2, 3, 4, 5, 6, 7$ or $8$ balls.
Number of ways $= 8 + 1 = 9$

Case II: Josie can pick $1, 2, 3, 4, 5, 6, 7$ or $8$ balls.
Number of ways $= 8$

Answer: (I) $9$ ways; (II) $8$ ways

The following examples pertain to selection of different sets of identical elements.

Example 47

Jaggu has $3$ red, $4$ black and $5$ blue balls, wherein the balls of each colour are identical. In how many ways
(I) can Jaggu select the balls?
(II) can Jaggu select the balls such that at least one ball is selected?
(III) can Jaggu select the balls such that at least one ball of each colour is selected?

Solution

Case I: Ways of selecting from $3$ red and $4$ black and $5$ blue balls $= (3 + 1) \times (4 + 1) \times (5 + 1) = \bm{120}$

Case II: In the Case I, there is $1$ way where none of the balls are selected. This needs to be removed.

$\therefore$ Number of ways to select $1$ or more of these balls $= 120 - 1 = \bm{119}$

Case III: As selecting none of any of the colours is not allowed, Jaggu can select the $3$ red, $4$ black and $5$ blue balls in $3, 4$ and $5$ ways respectively.

$\therefore$ Number of ways to select $1$ or more of each colour $= 3 \times 4 \times 5 = \bm{60}$

Answer: (I) $120$; (II) $119$; (III) $60$

This concept of selecting identical elements also applies for finding the number of factors of a number (also covered in the Factors & Remainders lesson). When the number is prime factorised, the identical elements are the prime numbers and the number of such identical primes is its exponent/power.

Example 48

How many different factors does the number $18000$ have?

Solution

Prime factorising $18000 =$ $2^{4} \times 3^{2} \times 5^{3}$

As there are $4$ identical $2$s, $2$ identical $3$s and $3$ identical $5$s,

Number of factors $= (4 + 1) \times (2 + 1) \times (3 + 1) = 60$

Answer: $60$

6.5 Selecting identical elements into non-identical groups

Number of ways $\bm{n}$ identical items can be divided into $\bm{r}$ distinct groups is $^{n + r - 1}C_{r - 1}$.

Let's understand this with an example.

Example: How many solutions for $a + b + c = 8$ exist, where $a, b$ and $c$ are non-negative integers?

As $a, b$ and $c$ are non-negative integers, they can take values between $0$ and $8$.

Let's take the constant to be an $8$ letter word, all of which are the same letter - $x$. Say, $x x x x x x x x$.
Now, we place two dividers (letter '$y$') in this block. So, lets say the block is $y y x x x x x x x x$.

We can now define the number of $x$ before the first $y$ as the value for $a$, number of $x$ between the first and second $y$ as the value of $b$. Lastly, the number of $x$ after the second $y$ as the value of $c$.

If the word is $y y x x x x x x x x$, we have a solution of $a = 0, b = 0$ and $c = 8$.
If the word is $x x y x x x x x y x$, we have a solution of $a = 2, b = 5$ and $c = 1$.

Now, all we need to do is treat this as a $10$-letter word and compute the number of possible arrangements. As this is a $10$-letter word with $8 x$ and $2 y$, the solution is

$\dfrac{10!}{8! \times 2!} = \bm{45}$

Note that the above is nothing but $^{n + r - 1}C_{r - 1}$, where $n$ is the total $8$ and $r$ is the $3$ variables $(a, b, c)$.
Number of non-negative integral solutions $=$ $^{8 + 3 - 1}C_{3 - 1} =$ $^{10}C_{2} = \bm{45}$

Example 49

In how many ways can $15$ identical balls be placed in $3$ bags of different colours, such that
(I) each bag contains any number of balls?
(II) each bag has at least $1$ ball?
(III) red and blue coloured bags have at least $2$ balls each and black coloured bag has at least $1$ ball?

Solution

Let $a, b$ and $c$ represent the $3$ bags of different colours.

(I) With no other condition, we can apply the formula directly. Let $n$ be the total $15$ and $r$ be the $3$ variables.
$a + b + c = 15$
Number of ways balls can be distributed $=$ $^{15 + 3 - 1}C_{3 - 1} =$ $^{17}C_{2} = 136$

(II) Since there should be at least one ball in each bag, we can begin by placing one ball in each bag. We are now left with $12$ balls.
$a + b + c = 12 $
Number of ways balls can be distributed $=$ $^{12 + 3 - 1}C_{3 - 1} =$ $^{14}C_{2} = 91$

(III) Once again, we satisfy the conditions by placing $2, 2$ and $1$ balls in red, blue and black bags respectively. Now, we can apply the formula, where $a + b + c = 10$
$^{10 + 3 - 1}C_{3 - 1} =$ $^{12}C_{2} = 66$

Answer: (I) $136$; (II) $91$; (III) $66$

Example 50

In how many ways can one or more of $15$ identical balls be placed in $3$ bags of different colours?

Solution

The difference in this question (as compared to the earlier ones) is that there is no conditions for all $15$ balls to be placed. Let's create a dummy variable, say D, which holds the leftover/unplaced balls.
$\therefore$ The equation now is $a + b + c + D = 15$

Number of ways balls can be assigned $=$ $^{15 + 4 - 1}C_{4 - 1} =$ $^{18}C_{3} = 816$

As the questions requires us to find the cases where $1$ or more balls are placed, we need to remove the $1$ case where $a, b$ and $c$ are $0$ and the dummy variable $D = 15$.

$\therefore$ Number of ways in which balls can be assigned $= 816 - 1 = \bm{815}$

Answer: $815$

Example 51

In how many ways can $15$ identical balls be placed in either red, blue or black bags, such that
(I) each bag has an odd number of balls?
(II) the number of balls in the black bag is a multiple of $4$?

Solution

Case I: Odd numbers are of the form $2k + 1$.
$\therefore$ Let the number of balls in the red, blue and black bags be $(2a + 1), (2b + 1)$ and $(2c + 1)$ respectively.
$(2a + 1) + (2b + 1) + (2c + 1) = 15$
⇒ $2(a + b + c) = 12$
⇒ $a + b + c = 6$

$\therefore$ Number of ways $=$ $^{5 + 3 - 1}C_{3 - 1} =$ $^{8}C_{2} =$ $\bm{28}$

Case II: In this question we have to note that there is no requirement for each bag to have at least one ball. So, there can also be $0$ balls in a bag. Let $c$ be the number of balls in the black bag.

Different cases where balls in the black bag is a multiple of $\bm{4:}$

$c$ =	Number of ways
$0$	$a + b = 15$ ⇒ $^{15 + 2 - 1}C_{2 - 1} =$ $^{16}C_{1} = 16$
$4$	$a + b = 11$ ⇒ $^{11 + 2 - 1}C_{2 - 1} =$ $^{12}C_{1} = 12$
$8$	$a + b = 7$ ⇒ $^{7 + 2 - 1}C_{2 - 1} =$ $^{8}C_{1} = 8$
$12$	$a + b = 3$ ⇒ $^{3 + 2 - 1}C_{2 - 1} =$ $^{4}C_{1} = 4$

Total ways of assigning the balls $= 16 + 12 + 8 + 4 = \bm{40}$

Answer: (I) $28$; (II) $40$

Example 52

In how many ways can $15$ identical balls be placed in either red, blue or black bags, such that none of the bags contain more than $8$ balls?

Solution

This can be solved by subtracting the ways where the condition is breached from the total number of ways.

$a + b + c = 15$
$\therefore$ Total ways $=$ $^{15 + 3 - 1}C_{3 - 1} =$ $^{17}C_{2} = 136$
Breach in condition occurs if a bag has $9$ balls. Let's first place $9$ balls in the red bag, which leaves us with $6$.
$a + b + c = 6$

$\therefore$ Breaches where red has $9$ or more balls $=$ $^{6 + 3 - 1}C_{3 - 1} =$ $^{8}C_{2} = 28$

Likewise, $28$ such breaches can occur in each of blue and black bags.
$\therefore$ Total breaches $= 28 \times 3 = 84$

Total possible cases $= 136 - 84 = 52$

Answer: $52$

6.6 Number of terms in algebraic expansion

Where $a_{1}$, $a_{2}$, $a_{3}$, .., $a_{r}$ are different variables, the number of terms in the expansion of $(a_{1} + a_{2} + ... + a_{r})^{n}$ is the same as the number of different non-negative integral solutions for $a_{1} + a_{2} + ... + a_{r} = n$.

∴ Number of terms in the expansion of $(a_{1} + a_{2} + ... + a_{r})^{n}$ = $\bm{^{n + r - 1}C_{r - 1}}$

Where there is only $1$ variable with different powers such as $a^{0}, a^{1}, a^{2}$, etc.,

Number of terms in the expansion of $(1 + a + a^{2} + ... + a^{r})^{n} = \bm{nr + 1}$

Example 53

What is the number of distinct terms in the expansion of $(a + b + c)^{20}$?
[CAT 2008]

(1) $231$ (2) $253$ (3) $242$ (4) $210$ (5) $228$

Solution

The powers of $a, b$ and $c$ in each term of the expansion will add up to $20$.
Let $x, y$ and $z$ be the respective powers.
$x + y + z = 20$

Number of different terms $= ^{20 + 3 - 1}C_{3 - 1} = ^{22}C_{2} = 231$

Answer: (1) $231$