Skip to content
← Mathematics

Mathematics · Class 11 Science

Ch 4Combinatorics and Mathematical Induction — Class 11 Mathematics, concept-first.

Combinatorics is the branch of mathematics concerned with counting — with arrangements of objects and with enumerating objects that share a specific property. Its roots go back roughly to 2800 BCE, when it was used to study magic squares and the patterns within them.

134

Q&A

6

Concepts

~7m

Unit weightage

Start learning — read this chapter →

Key concepts

Hover a concept to preview it and jump to its most relevant Q&A.

Fundamental Principles of Counting

Imagine you're getting dressed. You have 3 shirts (red, blue, green) and 2 pairs of pants (black, white). How many different outfits can you make?

Most relevant Q&A

Start with this concept →

Chapter contents

The NCERT structure, section by section. Open a section to see its questions, then read the concept-first solution.

Introduction

Combinatorics is the branch of mathematics concerned with counting — with arrangements of objects and with enumerating objects that share a specific property.

4.2

Fundamental principles of counting

Three basic rules let us count the number of ways of carrying out a task, without listing every possibility.

4.3

Factorials

Factorial of a natural number , written and read " factorial" (or "factorial of "), is the product of the first natural numbers: The notation was introduced by the French mathematician Christian Kramp…

+Exercise 4.1i16 questions
  1. Q1(i) A person went to a restaurant for dinner. In the menu card, the person saw 10 Indian and 7 Chinese food items. In how many ways the pers…Free
  2. Q2(i) A mobile phone has a passcode of 6 distinct digits. What is the maximum number of attempts one makes to retrieve the passcode? (ii) Give…Free
  3. Q3Four children are running a race. (i) In how many ways can the first two places be filled? (ii) In how many different ways could they finish…Free
  4. Q4Count the number of three-digit numbers which can be formed from the digits $2,4,6,8$ if (i) repetitions of digits is allowed. (ii) repetiti…Preview
  5. Q5How many three-digit numbers are there with 3 in the unit place? (i) with repetition (ii) without repetition.Preview
  6. Q6How many numbers are there between 100 and 500 with the digits $0,1,2,3,4,5$? if (i) repetition of digits allowed (ii) the repetition of dig…Preview
  7. Q7How many three-digit odd numbers can be formed by using the digits $0,1,2,3,4,5$? if (i) the repetition of digits is not allowed (ii) the re…Preview
  8. Q8Count the numbers between 999 and 10000 subject to the condition that there are (i) no restriction. (ii) no digit is repeated. (iii) at leas…Preview
  9. Q9How many three-digit numbers, which are divisible by 5, can be formed using the digits $0,1,2,3,4,5$ if (i) repetition of digits are not all…Preview
  10. Q10To travel from a place $A$ to place $B$, there are two different bus routes $B_1, B_2$, two different train routes $T_1, T_2$ and one air ro…Preview
  11. Q11How many numbers are there between 1 and 1000 (both inclusive) which are divisible neither by 2 nor by 5?Preview
  12. Q12How many strings can be formed using the letters of the word LOTUS if the word (i) either starts with L or ends with S? (ii) neither starts…Preview
  13. Q13(i) Count the total number of ways of answering 6 objective type questions, each question having 4 choices. (ii) In how many ways 10 pigeons…Preview
  14. Q14Find the value of (i) $6!$ (ii) $4!+5!$ (iii) $3!-2!$ (iv) $3!\times 4!$ (v) $\dfrac{12!}{9!\times 3!}$ (vi) $\dfrac{(n+3)!}{(n+1)!}$Preview
  15. Q15Evaluate $\dfrac{n!}{r!(n-r)!}$ when (i) $n=6, r=2$ (ii) $n=10, r=3$ (iii) For any $n$ with $r=2$.Preview
  16. Q16Find the value of $n$ if (i) $(n+1)! = 20(n-1)!$ (ii) $\dfrac{1}{8!}+\dfrac{1}{9!} = \dfrac{n}{10!}$.Preview
4.4

Permutations

A permutation is an ordered arrangement of objects. Suppose three friends A, B, C must stand in a line for a photograph — some possible orderings (left to right) are A,B,C; A,C,B; B,A,C; B,C,A; C,B,A;…

4.4.1

Permutations of distinct objects

Viewed as a function, a permutation of a finite set is a bijective mapping of onto itself; the number of permutations of therefore equals the total number of bijections from to , which is .

4.4.2

Properties of Permutations

Three algebraic identities connect permutations of related orders, each proved directly from .

4.4.3

Objects always together (String method)

Objects that must always stay together — the 'string' (block) method.

4.4.4

No two things are together (Gap method)

No two of a group of objects may be adjacent — the 'gap' method.

4.4.5

Permutations of not all distinct objects

So far every object being permuted was distinct. When some objects repeat, naive over-counts, because swapping two identical copies produces an arrangement that looks the same.

+Exercise 4.2i20 questions
  1. Q1If $(n-1)P_3 : {}^nP_4 = 1:10$, find $n$.Free
  2. Q2If $^{10}P_{r-1} = 2\times {}^6P_r$, find $r$.Free
  3. Q3(i) Suppose 8 people enter an event in a swimming meet. In how many ways could the gold, silver and bronze prizes be awarded? (ii) Three men…Free
  4. Q4Determine the number of permutations of the letters of the word SIMPLE if all are taken at a time?Preview
  5. Q5A test consists of 10 multiple choice questions. In how many ways can the test be answered if (i) Each question has four choices? (ii) The f…Preview
  6. Q6A student appears in an objective test which contain 5 multiple choice questions. Each question has four choices out of which one correct an…Preview
  7. Q7How many strings can be formed from the letters of the word ARTICLE, so that vowels occupy the even places?Preview
  8. Q88 women and 6 men are standing in a line. (i) How many arrangements are possible if any individual can stand in any position? (ii) In how ma…Preview
  9. Q9Find the distinct permutations of the letters of the word MISSISSIPPI?Preview
  10. Q10How many ways can the product $a^2b^3c^4$ be expressed without exponents?Preview
  11. Q11In how many ways 4 mathematics books, 3 physics books, 2 chemistry books and 1 biology book can be arranged on a shelf so that all books of…Preview
  12. Q12In how many ways can the letters of the word SUCCESS be arranged so that all Ss are together?Preview
  13. Q13A coin is tossed 8 times, (i) How many different sequences of heads and tails are possible? (ii) How many different sequences containing six…Preview
  14. Q14How many strings are there using the letters of the word INTERMEDIATE, if (i) The vowels and consonants are alternative (ii) All the vowels…Preview
  15. Q15Each of the digits 1, 1, 2, 3, 3 and 4 is written on a separate card. The six cards are then laid out in a row to form a 6-digit number. (i)…Preview
  16. Q16If the letters of the word GARDEN are permuted in all possible ways and the strings thus formed are arranged in the dictionary order, then f…Preview
  17. Q17Find the number of strings that can be made using all letters of the word THING. If these words are written as in a dictionary, what will be…Preview
  18. Q18If the letters of the word FUNNY are permuted in all possible ways and the strings thus formed are arranged in the dictionary order, find th…Preview
  19. Q19Find the sum of all 4-digit numbers that can be formed using digits 1, 2, 3, 4, and 5 repetitions not allowed?Preview
  20. Q20Find the sum of all 4-digit numbers that can be formed using digits 0, 2, 5, 7, 8 without repetition?Preview
4.5

Combinations

Suppose four people must have three of them selected to serve on a committee. Unlike a permutation, here order doesn't matter — is exactly the same selection as or .

4.5.1

Properties of Combinations

Five standard identities let a combination be simplified or compared without full expansion.

+Exercise 4.3i25 questions
  1. Q1If $^nC_{12} = {}^nC_9$ find $^{21}C_n$.Free
  2. Q2If $^{15}C_{2r-1} = {}^{15}C_{2r+4}$, find $r$.Free
  3. Q3If $^nP_r = 720$, and $^nC_r = 120$, find $n, r$.Free
  4. Q4Prove that $^{15}C_3 + 2\times {}^{15}C_4 + {}^{15}C_5 = {}^{17}C_5$.Preview
  5. Q5Prove that $^{35}C_5 + \displaystyle\sum_{r=0}^{4} {}^{(39-r)}C_4 = {}^{40}C_5$.Preview
  6. Q6If $^{(n+1)}C_8 : {}^{(n-3)}P_4 = 57:16$, find the value of $n$.Preview
  7. Q7Prove that $^{2n}C_n = \dfrac{2^n \times 1\times 3\times 5 \cdots (2n-1)}{n!}$.Preview
  8. Q8Prove that if $1\le r\le n$ then $n\times {}^{(n-1)}C_{r-1} = (n-r+1)\,{}^nC_{r-1}$.Preview
  9. Q9(i) A Kabaddi coach has 14 players ready to play. How many different teams of 7 players could the coach put on the court? (ii) There are 15…Preview
  10. Q10Find the total number of subsets of a set with [Hint: $^nC_0+{}^nC_1+{}^nC_2+\cdots+{}^nC_n = 2^n$] (i) 4 elements (ii) 5 elements (iii) $n$…Preview
  11. Q11A trust has 25 members. (i) How many ways 3 officers can be selected? (ii) In how many ways can a President, Vice President and a Secretary…Preview
  12. Q12How many ways a committee of six persons from 10 persons can be chosen along with a chair person and a secretary?Preview
  13. Q13How many different selections of 5 books can be made from 12 different books if, (i) Two particular books are always selected? (ii) Two part…Preview
  14. Q14There are 5 teachers and 20 students. Out of them a committee of 2 teachers and 3 students is to be formed. Find the number of ways in which…Preview
  15. Q15In an examination a student has to answer 5 questions, out of 9 questions in which 2 are compulsory. In how many ways a student can answer t…Preview
  16. Q16Determine the number of 5 card combinations out of a deck of 52 cards if there is exactly three aces in each combination.Preview
  17. Q17Find the number of ways of forming a committee of 5 members out of 7 Indians and 5 Americans, so that always Indians will be the majority in…Preview
  18. Q18A committee of 7 peoples has to be formed from 8 men and 4 women. In how many ways can this be done when the committee consists of (i) exact…Preview
  19. Q197 relatives of a man comprises 4 ladies and 3 gentlemen, his wife also has 7 relatives; 3 of them are ladies and 4 gentlemen. In how many wa…Preview
  20. Q20A box contains two white balls, three black balls and four red balls. In how many ways can three balls be drawn from the box, if at least on…Preview
  21. Q21Find the number of strings of 4 letters that can be formed with the letters of the word EXAMINATION?Preview
  22. Q22How many triangles can be formed by joining 15 points on the plane, in which no line joining any three points?Preview
  23. Q23How many triangles can be formed by 15 points, in which 7 of them lie on one line and the remaining 8 on another parallel line?Preview
  24. Q24There are 11 points in a plane. No three of these lies in the same straight line except 4 points, which are collinear. Find, (i) the number…Preview
  25. Q25A polygon has 90 diagonals. Find the number of its sides?Preview
4.6

Mathematical induction

40 Q

Consider the sum of the first positive odd numbers: — the right-hand sides are exactly the perfect squares , suggesting the conjecture A pattern noticed on a handful of cases is not yet a proof for ev…

+Exercise 4.4i15 questions
  1. Q1By the principle of mathematical induction, prove that, for $n\ge 1$ $$1^3+2^3+3^3+\cdots+n^3 = \left(\dfrac{n(n+1)}{2}\right)^2$$Free
  2. Q2By the principle of mathematical induction, prove that, for $n\ge 1$ $$1^2+3^2+5^2+\cdots+(2n-1)^2 = \dfrac{n(2n-1)(2n+1)}{3}.$$Free
  3. Q3Prove that the sum of the first $n$ non-zero even numbers is $n^2+n$.Free
  4. Q4By the principle of Mathematical induction, prove that, for $n\ge 1$ $$1.2+2.3+3.4+\cdots+n.(n+1) = \dfrac{n(n+1)(n+2)}{3}.$$Preview
  5. Q5Using the Mathematical induction, show that for any natural number $n\ge 2$, $$\left(1-\dfrac{1}{2^2}\right)\left(1-\dfrac{1}{3^2}\right)\le…Preview
  6. Q6Using the Mathematical induction, show that for any natural number $n\ge 2$, $$\dfrac{1}{1+2}+\dfrac{1}{1+2+3}+\dfrac{1}{1+2+3+4}+\cdots+\df…Preview
  7. Q7Using the Mathematical induction, show that for any natural number $n$, $$\dfrac{1}{1.2.3}+\dfrac{1}{2.3.4}+\dfrac{1}{3.4.5}+\cdots+\dfrac{1…Preview
  8. Q8Using the Mathematical induction, show that for any natural number $n$, $$\dfrac{1}{2.5}+\dfrac{1}{5.8}+\dfrac{1}{8.11}+\cdots+\dfrac{1}{(3n…Preview
  9. Q9Prove by Mathematical Induction that $$1!+(2\times 2!)+(3\times 3!)+\cdots+(n\times n!) = (n+1)!-1.$$Preview
  10. Q10Using the Mathematical induction, show that for any natural number $n$, $x^{2n}-y^{2n}$ is divisible by $x+y$.Preview
  11. Q11By the principle of Mathematical induction, prove that, for $n\ge 1$ $$1^2+2^2+3^2+\cdots+n^2 > \dfrac{n^3}{3}.$$Preview
  12. Q12Use induction to prove that $n^3-7n+3$, is divisible by 3, for all natural numbers $n$.Preview
  13. Q13Use induction to prove that $5^{n+1}+4\times 6^n$ when divided by 20 leaves a remainder 9, for all natural numbers $n$.Preview
  14. Q14Use induction to prove that $10^n+3\times 4^{n+2}+5$, is divisible by 9, for all natural numbers $n$.Preview
  15. Q15Prove using the Mathematical induction $$\sin(\alpha)+\sin\left(\alpha+\dfrac{\pi}{6}\right)+\sin\left(\alpha+\dfrac{2\pi}{6}\right)+\cdots+…Preview
+Exercise 4.5i25 questions
  1. Q1The sum of the digits at the $10^{\text{th}}$ place of all numbers formed with the help of $2,4,5,7$ taken all at a time is (1) $432$ (2) $1…Free
  2. Q2In an examination there are three multiple choice questions and each question has 5 choices. Number of ways in which a student can fail to g…Free
  3. Q3The number of ways in which the following prize be given to a class of 30 boys first and second in mathematics, first and second in physics,…Free
  4. Q4The number of 5 digit numbers all digits of which are odd is (1) $2^5$ (2) $5^5$ (3) $5^6$ (4) $625$.Preview
  5. Q5In 3 fingers, the number of ways four rings can be worn is $\cdots$ ways. (1) $4^3-1$ (2) $3^4$ (3) $6^8$ (4) $6^4$Preview
  6. Q6If $^{(n+5)}P_{(n+1)} = \left(\dfrac{11(n-1)}{2}\right){}^{(n+3)}P_n$, then the value of $n$ are (1) $7$ and $11$ (2) $6$ and $7$ (3) $2$ an…Preview
  7. Q7The product of $r$ consecutive positive integers is divisible by (1) $r!$ (2) $(r-1)!$ (3) $(r+1)!$ (4) $r^r$.Preview
  8. Q8The number of five digit telephone numbers having at least one of their digits repeated is (1) $90000$ (2) $10000$ (3) $30240$ (4) $69760$.Preview
  9. Q9If $^{(a^2-a)}C_2 = {}^{(a^2-a)}C_4$ then the value of $a$ is (1) $2$ (2) $3$ (3) $4$ (4) $5$Preview
  10. Q10There are 10 points in a plane and 4 of them are collinear. The number of straight lines joining any two points is (1) $45$ (2) $40$ (3) $39…Preview
  11. Q11The number of ways in which a host lady invite 8 people for a party of 8 out of 12 people of whom two do not want to attend the party togeth…Preview
  12. Q12The number of parallelograms that can be formed from a set of four parallel lines intersecting another set of three parallel lines. (1) $6$…Preview
  13. Q13Everybody in a room shakes hands with everybody else. The total number of shake hands is 66. The number of persons in the room is $\cdots$ (…Preview
  14. Q14Number of sides of a polygon having 44 diagonals is $\cdots$ (1) $4$ (2) $4!$ (3) $11$ (4) $22$Preview
  15. Q15If 10 lines are drawn in a plane such that no two of them are parallel and no three are concurrent, then the total number of points of inter…Preview
  16. Q16In a plane there are 10 points are there out of which 4 points are collinear, then the number of triangles formed is (1) $110$ (2) $^{10}C_3…Preview
  17. Q17In $^{2n}C_3 : {}^nC_3 = 11:1$ then $n$ is (1) $5$ (2) $6$ (3) $11$ (4) $7$Preview
  18. Q18$^{(n-1)}C_r + {}^{(n-1)}C_{(r-1)}$ is (1) $^{(n+1)}C_r$ (2) $^{(n-1)}C_r$ (3) $^nC_r$ (4) $^nC_{r-1}$.Preview
  19. Q19The number of ways of choosing 5 cards out of a deck of 52 cards which include at least one king is (1) $^{52}C_5$ (2) $^{48}C_5$ (3) $^{52}…Preview
  20. Q20The number of rectangles that a chessboard has $\cdots$ (1) $81$ (2) $99$ (3) $1296$ (4) $6561$Preview
  21. Q21The number of 10 digit number that can be written by using the digits 2 and 3 is (1) $^{10}C_2+{}^9C_2$ (2) $2^{10}$ (3) $2^{10}-2$ (4) $10!…Preview
  22. Q22If $P_r$ stands for $^rP_r$ then the sum of the series $1+P_1+2P_2+3P_3+\cdots+nP_n$ is (1) $P_{n+1}$ (2) $P_{n+1}-1$ (3) $P_{n-1}+1$ (4) $^…Preview
  23. Q23The product of first $n$ odd natural numbers equals (1) $^{2n}C_n\times {}^nP_n$ (2) $\left(\dfrac12\right)^n\times {}^{2n}C_n\times {}^nP_n…Preview
  24. Q24If $^nC_4, {}^nC_5, {}^nC_6$ are in AP the value of $n$ can be (1) $14$ (2) $11$ (3) $9$ (4) $5$Preview
  25. Q25$1+3+5+7+\cdots+17$ is equal to (1) $101$ (2) $81$ (3) $71$ (4) $61$Preview

Sample & Board Papers

Sample papers and previous-year board questions for this subject.

+Show 33 questions33 questions
  1. Q1The number of diagonals that can be drawn by joining the vertices of an octagon is: (a) 20 (b) 28 (c) 24 (d) 48Preview
  2. Q2How many numbers divisible by 5 and lying between 5000 and 6000 can be formed from the digits 5, 6, 7, 8 and 9 ?Preview
  3. Q3How many different signals can be made by hoisting 6 differently coloured flags one above the other, when any number of them may be hoisted…Preview
  4. Q4(a) Prove by mathematical induction that $7^{2n} + 16n - 1$ is divisible by 64 for all $n \in N$. **OR** (b) Using binomial theorem, find th…Preview
  5. Q5The number of five digit numbers in which all digits are even, is: (a) $4\times 5^4$ (b) $4\times 5^5$ (c) $5^5$ (d) $5\times 5$Preview
  6. Q6Write the relationship between Permutation and Combination.Preview
  7. Q7Count the number of positive integers greater than 6000 and less than 7000 which are divisible by 5, provided that no digits are repeated.Preview
  8. Q8(a) Prove that for any natural number $n$, $a^n-b^n$ is divisible by $a-b$, where $a>b$. **OR** (b) Evaluate: $\int \dfrac{2x+4}{x^2+4x+6}\,…Preview
  9. Q9There are 15 points in a plane and 5 of them are collinear. The number of straight lines joining any two points is: (a) 45 (b) 86 (c) 76 (d)…Preview
  10. Q10Find the number of ways of arranging the letters of the word 'BANANA'.Preview
  11. Q11If $(n+2)C_8 : (n-2)P_4 = 57 : 16$, find $n$.Preview
  12. Q12(a) By the principle of Mathematical Induction, prove that for $n \ge 1$, $1\cdot2 + 2\cdot3 + 3\cdot4 + \ldots n(n+1) = \dfrac{n(n+1)(n+2)}…Preview
  13. Q13The number of 5 digit numbers all digits of which are odd is: (a) $5^6$ (b) 25 (c) 625 (d) $5^5$Preview
  14. Q14Find the distinct permutations of the letters of the word ACCESSIBILITY.Preview
  15. Q15(a) By the principle of mathematical induction, prove that, for $n \ge 1$, $1^3+2^3+3^3+....+n^3 = \left(\dfrac{n(n+1)}{2}\right)^2$. **OR**…Preview
  16. Q16There are 8 points in a plane and 4 of them are collinear. The number of straight lines joining any 2 points is: (a) 39 (b) 45 (c) 38 (d) 23Preview
  17. Q17Number of sides of a polygon having 44 diagonals is: (a) 11 (b) 4 (c) 22 (d) 4!Preview
  18. Q18If $n \in N$, then $7^{2n} + 3^{3n-3}\cdot 3^{n-1}$ is always divisible by: (a) 45 (b) 25 (c) 55 (d) 35Preview
  19. Q19If $^{n-1}C_3 + {}^{n-1}C_4 > {}^{n}C_3$ then: (a) $n > 7$ (b) $n > 5$ (c) $n > 4$ (d) $n > 6$Preview
  20. Q20If $^{n}C_4 = 495$, find the value of $n$.Preview
  21. Q21If $^{n}C_{r-1} = 36$, $^{n}C_r = 84$ and $^{n}C_{r+1} = 126$ then find the value of $r$.Preview
  22. Q22There are n locks and n matching keys. If all the locks and keys are to be perfectly matched, then the maximum number of trials is: (a) $n(n…Preview
  23. Q23${}^nC_0+{}^nC_1+......+{}^nC_n=$ (a) $2^{n+1}$ (b) $2^n$ (c) $2^{n-1}$ (d) $2n$Preview
  24. Q24If $\dfrac{1}{7!}+\dfrac{1}{8!}=\dfrac{A}{9!}$ then find the value of A.Preview
  25. Q25Find the number of ways of arranging the letters of the word INDIA.Preview
  26. Q26If ${}^nP_r=720$ and ${}^nC_r=120$ find n, r.Preview
  27. Q27The number of 5 digit numbers, all digits of which are odd is: (a) $5^6$ (b) $25$ (c) $625$ (d) $5^5$Preview
  28. Q28What is the unit digit of the sum $3! + 4! + \ldots + 20!$?Preview
  29. Q29If $(n+2)P_4 = 42 \times {}^nP_2$, find $n$.Preview
  30. Q30(a) By the principle of mathematical induction, prove that, for $n \geq 1$ : $1^3+2^3+3^3+\ldots+n^3 = \left(\dfrac{n(n+1)}{2}\right)^2$ **O…Preview
  31. Q31Number of sides of a polygon having 44 diagonals is: (a) 11 (b) 4 (c) 22 (d) $4!$Preview
  32. Q32If ${}^nC_{12} = {}^nC_9$, find ${}^{21}C_n$.Preview
  33. Q33Prove that $\dfrac{(2n)!}{n!} = 2^n(1.3.5\ldots(2n-1))$Preview