CAT 2025 Lesson : Permutations & Combinations - Identical Elements

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.



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



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.

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}$

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}$