CAT Quant : Permutation and Combination (PnC) – Important Formulas and Concepts
Fundamental Rule
The fundamental rule concerning permutation and combination can be stated as follows –
If one operation can be performed in ‘m’ ways and (when, it has been performed in any one of these ways), a second operation then can be performed in ‘n’ ways, the number of ways of performing the two operations will be m x n.
This can be extended to any number of operations.
For Example – If there are three cities A, B and C such that there are 3 roads connecting A and B and 4 roads connecting B and C, then the number of ways one can travel from A to C is 3 x 4, ie., 12.
Permutations
A permutation is an arrangement of objects in a specific order.
Permutation implies “arrangement” or that “order of the items” is important, thus, the words “permutation” and “arrangement” are synonymous and can be used interchangeably.
The number of permutations of n things taking rat time is denoted by ” \( ^{n}P_r \)” (read as “nPr”) and can be calculated as $$ ^{n}P_r = \frac{n!} {(n-r)!}$$ where n! denotes the factorial of n, which is the product of all positive integers less than or equal to n.
Combination
A combination is a selection of objects without regard to the order.
In combinations, the order in which the items are taken is not considered as long as the specific things are included. The words “combination” and “selection” are synonymous.
The number of combinations of n things taking r at time is denoted by \( ^{n}C_r (read as nCr) and calculated as $$^{n}C_r = \frac{n!}{r! \cdot (n-r)!} $$ where n! denotes the factorial of n, which is the product of all positive integers less than or equal to n.
The number of combinations of n dissimilar things taken all at a time is 1.
Certain Properties of Combinations –
\( ^{n}C_0 = 1 \)
\( ^{n}C_1 = ^{n}C_{n-1} = n \)
\( ^{n}C_r = ^{n}C_{n-r} \)
Cases under Permutation
CASE 1 : Number of arrangements of n items of which p are of one type, q are of a second type and the rest are distinct –
The number of ways in which n things may be arranged taking them all at a time, when p of the things are exactly like one kind, q of them exactly like another kind, r of them exactly like of a third kind, and the rest all distinct is $$ \frac{n!}{(p! \ q! \ r!)} $$
CASE 2 : Number of arrangements of n distinct items where each item can be used any number of times (i.e., repetition allowed) –
When selecting items with repetition allowed, each selection can be made independently and has the same number of choices, which is n.
For r selections, each selection can be made in n ways, resulting in a total of \( n \times n \times n \) … (r times) ways, which simplifies to \( n^r \).
Thus, the number of permutations of n things taken r at a time with repetition allowed is \( \longrightarrow n^r \).
Note – When solving questions of such type it is better to grasp the reasoning behind the formula rather than memorizing it directly.
Total number of combinations
Out of n given things, the number of ways of selecting one or more things is where we can select 1 or 2 or 3… and so on n things at a time; hence the number of ways is \( ^{n}C_1+^{n}C_2+^{n}C_3 + … ^{n}C_n \).
This is called “the total number of combinations” and is equal to \( (2^{n}-1) \) where n is the number of things.
Also, the Number of ways of selecting one or more items from n given items is $$ 2^{n}-1 $$
Dividing given items into Groups
Dividing (p+q) items into two groups of p and q items respectively –
Out of (p+q) items, if we select p items (which can be done in \( ^{p+q}C_p \) ways), then we will be left with q items, i.e.. we have two groups of p and q items respectively.
So, the number of ways of dividing (p+q) items into two groups of p and q items respectively is equal to – $$ ^{p+q}C_p = \frac{(p+q)!}{p! \cdot q!}$$
If p = q i.e., if we have to divide the given items into two EQUAL groups, then two cases arise –
when the two groups have distinct identity :
Here, we just have to substitute p=q in the above formula
The number of ways of dividing 2p items into two equal groups of p each is $$ \frac{(2p)!}{(p!)^{2}} $$ where, the two groups have distinct identity.
when the two groups do not have distinct identity :
In the second case, where the two groups do not have distinct identity, we have to divide the above result by 2!.
The number of ways of dividing 2p items into two equal groups of p each is $$\frac{(2p)!}{2!{(p!)}^{2}} $$ where, the two groups do not have distinct identity.
Dividing (p+q+r) items into three groups consisting of p, q and r items respectively –
The number of ways in which (p+q+r) things can be divided into three groups containing p, q and r things respectively is $$ \frac{(p+q+r)!}{p! \cdot q! \cdot r!} $$
If p = q = r, i.e., if we have to divide the given items into three EQUAL groups, then we have two cases where the three groups are distinct and where the groups are not distinct.
When the three groups are distinct, the number of ways is $$ \frac{(3p)!}{(p!)^{3}}$$
When the three groups are not distinct, then the number of ways is $$\frac{(3p)!}{3!(p!)^{3}}$$
Circular Permutations
A circular arrangement involves placing objects around a central point in a closed loop, creating a continuous cycle with rotational symmetry.
In a straight line, arranging n items results in n! permutations, but in a circle, due to rotation, shifting each item by one place doesn’t change the arrangement.
In a circular arrangement, after fixing one item, the remaining (n-1) items can be arranged in (n-1)! ways.
Hence, the number of ways in which n distinct things can be arranged in a circular arrangement is $$(n-1)!$$
The number of circular arrangements of n distinct items is –
(n-1)! \( \longrightarrow \) if there is difference between clockwise and anticlockwise arrangements
(n-1)!/2 \( \longrightarrow \) if there is NO DIFFERENCE between clockwise and anticlockwise arrangements
Sum of all numbers formed from given digits
If n distinct digits are used to make all the possible n-digit numbers, we get n! numbers.
If all the possible n-digit numbers using n distinct digits are formed, the sum of all the numbers so formed is equal to $$(n-1)! \times (sum \ of \ the \ n \ digits) \times (11111…..) n \ times$$
Rank of a word
The rank of a word is its position when all possible words formed by arranging its letters once are sorted alphabetically.
For Example – Consider the word “POINT”. Arrange letters in alphabetical order: I, N, O, P, T. Count words preceding “POINT” alphabetically. Words beginning with I: 4! , Words beginning with N: 4! , Words beginning with O: 4! , Words beginning with PI: 3! , Words beginning with PN: 3! . then we arrive at the word ‘POINT’. \( \\ \) There are \( 3 \times 4!+2 \times 3!= 84 \ words\) that precede the word POINT i.e., POINT is the 85th word. \( \\ \) Hence rank of ‘POINT’ is 85.
The number of diagonals in an n-sided regular polygon
An n-sided regular polygon has n vertices. Joining any two vertices we get a line of the polygon which are \( ^{n}C_2 \) in number: Of these \( ^{n}C_2 \) lines, n of them are sides.
Hence diagonals are $$^{n}C_{2}-n=\frac{n(n-3)}{2} $$
Number of integral solution of the equation x1 + x2 + … + xn = s
In general, if x1 + x2 + … + xn = s where s \( \ge \) n, the number of positive integral solutions is \( \longrightarrow \ ^{s-1}C_{n-1} \)
The number of non-negative integral solutions of the given equation is equal to the number of positive integral solutions of x1 + x2 + … + xn = (s +n) where s \( \ge \) n, which is \( \longrightarrow \ ^{s+n-1}C{n-1} \)
Some Additional Points
Dearrangements –
Suppose there are n letters and n corresponding addressed envelopes. The numbers of ways of placing these letters into the envelopes such that no letter is placed in its corresponding envelope is often referred as derangements.
The number of derangements of n objects is given by $$ D(n)=n! {\LARGE[} 1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+….+(-1)^{n}\frac{1}{n!} {\LARGE]} $$
The total number of ways in which a selection can be made by taking some or all out of p+q+r+…. things where p are like one kind, q like a second kind, r like of a third kind and so on is $$ [\{(p+1)(q+1)(r+1)…..\}-1] $$
One common conclusion in permutation and combination is $$ ^{n+1}C_{r} = ^{n}C_{r} + ^{n}C_{r-1} \ \ and \ \ ^{n}P_{r} = r_{.}^{n-1}P_{r-1} + ^{n-1}P$$
