calendarBack
Quant

/

Modern Maths

/

Permutations & Combinations
ALL MODULES

CAT 2025 Lesson : Permutations & Combinations - Concepts & Cheatsheet

bookmarked
Note: The video for this module contains a summary of all the concepts covered in this lesson. The video would serve as a good revision. Please watch this video in intervals of a few weeks so that you do not forget the concepts. Below is a cheatsheet that includes all the formulae but not necessarily the concepts covered in the video.

9. Cheatsheet

1) n!=1×2...×nn! = 1 \times 2 ... \times n

2) nPr=n!(n−r)!^{n}P_{r} = \dfrac{n!}{(n - r)!} and nCr=^{n}C_{r} = n!r!(n−r)!\dfrac{n!}{r! (n - r)!}

4) Permutation of n\bm{n} elements where a\bm{a} elements are of one kind, b\bm{b} of another kind, etc. is n!a!b!c!...\dfrac{n!}{a! b! c! ...} ways.

5) Similar to the point above, if in an n\bm{n}-letter word, if 11 letter occurs a\bm{a} times, another letter occurs b\bm{b} times, etc., then number of different n\bm{n}-letter words that can be formed =n!a!b!c!...= \dfrac{n!}{a! b! c! ...}

6) Using Blanks: Identify the number of elements that can occupy each blank and multiply them.

7) While using blanks, address or fill up the blanks which have conditions first. E.g., in digits-related questions, the first digit from the left will have to be a digit other than zero.

8) As a general rule, multiply when And is used and add when Or is used. (Note: Exceptions exist)

9) If n\bm{n} distinct items can each be assigned in r\bm{r} different ways, then this can be done in rn\bm{r^{n}} ways.

10) Slotting: We arrange elements without conditions first and then select the slots and then arrange the rest.

11) Conditional Permutation: One approach is to first select the items and then arrange. The other approach is to use blanks and apply the conditions.

12) Sum of all nn-digit numbers using nn distinct non-zero digits =(n−1)!×= (n - 1)! \times sum of digits ×(111...n times)\times (111... _{n\space times})

13) Path Movement: Use letters to represent the steps or movements and then permute the letters of the word.

14) nn distinct elements can be circularly arranged in (n−1)!\bm{(n - 1)!} ways

15) If this circle can be reversed, number of such arrangements is (n–1)!2\bm{\dfrac{(n – 1)!}{2}}

16) In a total of n\bm{n} objects, if r\bm{r} are wrongly assigned,
Number of such derangements =nCr×D(r)= ^{n}C_{r} \times D(r) = nCr×r!×(1−11!+12!−13!+...)^{n}C_{r} \times r! \times \left( 1 - \dfrac{1}{1!} + \dfrac{1}{2!} - \dfrac{1}{3!} + ... \right)

17) nCr=nCn−r=nPrr!^{n}C_{r} = ^{n}C_{n - r} = \dfrac{^{n}P_{r}}{r!}

The greatest value of nCr^{n}C_{r} is r=n2r = \dfrac{n}{2}, when nn is even and r=(n+1)2r = \dfrac{(n + 1)}{2} or (n−1)2\dfrac{(n - 1)}{2} when, nn is odd.

18) nC0+nC1+nC2+...+nCn=2n^{n}C_{0} + ^{n}C_{1} + ^{n}C_{2} + ... + ^{n}C_{n} = 2^{n}
nC0+nC2+nC4+...=^{n}C_{0} + ^{n}C_{2} + ^{n}C_{4} + ... = nC1+nC3+nC5+...=^{n}C_{1} + ^{n}C_{3} + ^{n}C_{5} + ... = 2n−12^{n - 1}
When nn is odd, nC0+nC1+nC2+...+nC(n−1)/2=^{n}C_{0} + ^{n}C_{1} + ^{n}C_{2} + ... + ^{n}C_{(n - 1)/2} = nC(n+1)/2+nC(n+3)/2+...+nCn=2n−1^{n}C_{(n + 1)/2} + ^{n}C_{(n + 3)/2} + ... + ^{n}C_{n} = 2^{n - 1}

19) Selecting Distinct Elements: If n\bm{n} distinct elements are to be divided into groups with a\bm{a} elements, b\bm{b} elements, c\bm{c} elements, etc., number of possible selections is n!a!b!c!...\dfrac{n!}{a! b! c! ...}

20) Selecting Identical Elements: From n\bm{n} identical elements, the number of ways to make
- 00 or more selections is n+1\bm{n + 1} ways; and
- 11 or more selections is n\bm{n} ways.

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

22) Number of terms in the expansion of (a1+a2+...+ar)n=n+r−1Cr−1(a_{1} + a_{2} + ... + a_{r})^{n} = \bm{^{n + r - 1}C_{r - 1}}.

Number of terms in the expansion of (1+a+a2+...+ar)n(1 + a + a^{2} + ... + a^{r})^{n} is nr−1\bm{nr - 1}.

23) When elements have to be divided into similar groups, then it needs to manually done.

24) Maximum Intersection points of nn circles of different radii =n(n−1)= \bm{n (n - 1)} and nn non-concurrent lines =nC2= \bm{^{n}C_{2}}

25) Maximum lines that can be drawn through 22 or more of non-collinear points =nC2= \bm{^{n}C_{2}}
Number of straight lines drawn where through 22 or more of nn points where rr are collinear =nC2−rC2+1= \bm{^{n}C_{2} - ^{r}C_{2} + 1}

26) Number of triangles drawn from n\bm{n} non-collinear points =nC3= \bm{^{n}C_{3}}
Number of triangles drawn from n points, where r points are collinear =nC3−rC3= \bm{^{n}C_{3} - ^{r}C_{3}}

27) Number of diagonals of an nn-sided polygon =n(n−3)2= \bm{\dfrac{n (n - 3)}{2}}

28) From two sets of mm parallel lines and nn parallel lines, number of parallelograms formed =mC2×nC2= \bm{^{m}C_{2} \times ^{n}C_{2}}

29) From a larger rectangle with mm rows and nn columns,
Number of rectangles that can be formed =(1+2+..+m)(1+2+...+n)== (1 + 2 + .. + m) (1 + 2 + ... + n) = m(m+1)2×n(n+1)2\bm{\dfrac{m (m + 1)}{2} \times \dfrac{n (n + 1)}{2}}

Number of squares that can be formed =mn+(m−1)(n−1)+(m−2)(n−2)+...= \bm{mn + (m - 1) (n - 1) + (m - 2) (n - 2) + ...}

30) From a larger square with nn rows and nn columns,
Number of rectangles that can be formed =(n(n+1)2)2= \bm{\left( \dfrac{n (n + 1)}{2} \right)^{2}}

Number of squares that can be formed =n2+(n−1)2+...+1== n^{2} + (n - 1)^{2} + ... + 1 = n(n+1)(2n+1)6\bm{\dfrac{n (n + 1) (2n + 1)}{6}}

Loading...Loading Video....