Permutation and Combinations

By Ramesh Chandra

Permutation and Combinations has always been a dreaded chapter in every student s life and they usually have confusion as to which book to follow. There is a large gap between the student s understanding and the presentation of the numerous books available in the market today. To bridge this gap, Ramesh Chandra has come up with this book on P&C written in the best possible sequence. The book is compiled by the author to cover up the difficulties faced by the students. A No.1 success tool that includes all the concepts, samples, subjective & objective exercises, puzzles, IQ tests, easy learning methods and analysis to bring out the best in every student. This is a must-have for students aspiring to make it to the IIT s.

• Language: English
• Publisher: Notion Press
• Release date: Jun 15, 2015
• ISBN: 9789384391478

Book preview

errors

Chapter 1

BASIC REQUIREMENT TO THE TOPIC

FACTORIAL (!)

This is the basic building block of permutation and combination hence knows how to use it.

Factorial n is written as n!.

Its meaning is as the product of first n natural numbers. i.e.

n! = 1×2×3×……..×(n - 2)×(n - 1)×n. Where n ∈ Natural number

Examples

1! = 1.

4! = 1×2×3×4=24.

5! = 1×2×3×4x5 = 5×4×3×2×1=120.

8! = 1 × 2 × 3 × 4 × 5 × 6 × 7 × 8 = 40320

0! Defined as equal to 1 so don’t think why 0! = 1! = 1 just accepts it.

We do not define the factorial of negative integers or proper fractions.

Here I am going to ask some True/False questions. Just answer them.

Here answer to each question is False, Hence from here we get the following results.

Results:

Ex1. Find the values of following.

Sol.

= 1 + 5 + 10 + 10 + 5 + 1 = 32. Here we are using the result . Think! Why? It’s simple to prove.

5! = 5 x 4 x 3 x 2 x 1 = 5(4 x 3 x 2 x 1) = 5 x 4! = 5 x 4 x 3!, and so on.

Now you can say in general provided

Similarly provided

This can also be written as or recursively defined as

is use for multiplication of all the entities. Let us solve some question to get the theory.

Ex2:

Sol:

Ex3:

Sol:

Ex4: Find the remainder when,

is divided by 6.

Sol: i.e. multiple of 6, so remainder for this quantity = 0.

Now remaining

where, I1 is another positive integer, Hence remainder = 3.

SUMMATION

This is the topic, which most student hate at start, I am going to explain it in details so that your fear factor becomes zero. Hence, first understands the meaning of it, only then we can play with the summation type problems.

Ex1: in this case lower limit = 1 and upper limit = 5 and Variable function is

Its meaning is as shown, (Look, how r is changing.)

Now let say then

= 35. Here we are using the formula.

Let us have another example.

Ex2:

Observe the expression, variable m is starting from 2 and end at 10 and variable is increasing by 1 unit each time.

Here we are using the formula.

FORMULA RELATED TO SUMMATION

Ex3:

Ex4:

Note: Observe, how we write

Now answer the next question i.e. formula and remember the result.

Que1: Show that

verify it by taking any suitable example.

Sol. Let us take an example as,

Clearly 20 ≠ 6 x 9, Hence, here we can verify that

Ex5: Find the value of.

Sol.

Ex6: Select the greatest Number.

(A) (10!)². (B) (2!)¹⁰. (C) (5!)⁴. (D) (4!)⁵.

Sol.

Hence correct option is A

Here we have an exercise for you to solve. First complete it and then proceed.

EXERCISE 1

Q1. Find the value of following

and verify that

Is What do you learn from this question?

Q2. Convert the following into factorials:

Q3. Evaluate: for the following

Q4. Prove that

Hence deduce that

ANSWER KEY

AND SOME IMPORTANT FORMULAES

Here, where n and r Whole numbers such that .

Ex1. Find the value of following (1 - 4)

5) Prove that, and hence deduce the Pascal identity

6) Prove that

and hence deduce that

Sol.

Note: This property can be extended more as, provided n ≥ 3, r ≥ 3.

Now we have a question at the moment, if i say that

Then which one is correct?

Here first two options are correct. Observe here 2 + 5 = 7 but 2 + 6 ≠ 7.

From here we leads to the following results

OTHER FORMULAES

If Then, this implies either (i) x = y OR (ii) x + y = n.

{since x = r, y = n – r, x + y = n}

if r > n. It is taken by convention.

so coefficient of xr in

Observe that all the power of x {0, 1, 2, 3,……..,∞} i.e. whole numbers.

A geometric progression a, ar, ar², ar³……… ar(n-1) . Sum of its first n terms

Have you memories the above formulas? Let us have a mind refreshing IQ problem.

IQ 1: An ant wants to go from A to B by travelling on the surface of cube of length 1 cm as shown in figure. Find the shortest distance travel by ant.

Note: See solutions at the end

SOLVED EXAMPLES TO EXPLORE ABOVE FORMULAS

Ex 1: If then find the value of n.

Sol. n = 3 + 7 = 10. {Since Then this implies, either (i) x = y OR (ii) x + y = n.}

Ex 2: If then find the value of n.

Sol. by property

Ex 3: Find the value of

Sol. Apply

We can write

At the end we will get

So

Ex 4: Prove the Newton’s identity for integers

Proof:

It would be good if you remember this identity.

CHAPTER 2

COUNTING

Each branch of mathematics has its own fundamental theorem(s). Counting has two main fundamental principles

1. Addition Principle (The SUM RULE)

2. Multiplication Principle (The PRODUCT RULE)

ADDITION PRINCIPLE

THEOREM - 1

Let E1, E2,..., Ek, be pair-wise mutually exclusive events. If Ei can occur in ni ways, where i = 1, 2, 3……k, then either E1 or E2 or,..., or Ek can occur in n1 + n2 +…..+ nk ways.

Notice here that or is exclusive.

Ex 1: If a junction J is connected with n stations S1, S2, S3, ………., Sn as shown in figure then, how many ways are there to leave the junction J ?

Sol. 1+1+1+1+1+……+1(up-to n) = n ways.

Ex 2: If station S1 is connected to station S2 by 4 different roots as shown in figure. How many ways are there to reach S2 from S1?

Sol. 4 ways

Ex 3: consider the figure as shown. The number of ways to leave S1 station is?

Sol. By addition principle, Total number of ways = 3 + 4 = 7 ways.

Ex 4: Find the number of two digit number which is divisible by 5, if digits do not repeat?

Sol. Any two digit number, divisible by 5 ends with either 0 or 5. The number of 2 digit number end with 0 are 9, the number of 2 digit number ends with 5 are 8. Hence total two digit number either end with 0 or 5 with no digits repeat = 9 + 8 = 17 (ADDITION PRINCIPLE)

Ex 5: A class has 20 students (8 girls and 12 boys). A teacher wants to make a class monitor, in how many ways he can?

Sol. Here is the teacher’s thinking

1. Select a girl among 8 girls OR

2. Select a boy from 12 boys.

Therefore the number of ways to select a student either girl or boy = 8 + 12 = 20.

Ex 6: In a group of 8 men and 9 women we can pick one man or one woman in 8 + 9 = 17 ways. Notice that we are choosing one person.

Note: If an event can happen in x distinct ways and a second which is mutually exclusive to first one can happen in y distinct ways, then the event 1st or 2nd can happen in x + y ways.

Ex 7: There were a total of 1890 digits used in writing all of the page numbers in a book. How many pages does the book have?

Sol. A total of digits are used to write pages 1 to 99, inclusive. We have of 1890−189 = 1701 digits left, which is enough for 1701/3 = 567 extra pages (starting from page 100).

The book has 99 + 567 = 666 pages.

Note: Hope you got the understanding of addition principle. Now we are moving to the next principle.

MULTIPLICATION PRINCIPLE

THEOREM - 2

Suppose that an experiment E can be performed in k stages: E1 first, E2 second,....., Ek last. Suppose moreover that Ei can be done in ni different ways, where i = 1, 2, 3, 4,…k, and that the number of ways of performing Ei is not influenced by any predecessors E1,E2,...,Ei-1. Then E1 and E2 and ... and Ek can occur simultaneously in n1 x n2 x n3 x ……x nk ways.

"If an event can occur in m different ways, following which another event can occur in n different ways, then the total number of occurrence of the events in the given order is m x n."

Ex 1: A person wants to enter in to market and then exit from it. How many such ways are there?

Sol.

So what do you learn from here?

1. Total number of ways = 6.

2. For each entrance there are 2 exit

Number of ways entrance = 3 FOLLOWED by number of ways to exit = 2.

This followed by lead to multiplication. i.e. 3 FOLLOWED by 2 = 3 x 2 = 6 ways.

Ex 2: Consider the figure as shown. In how many ways you can reach station C From Station J if arrow shows the direction of travelling?

Sol. You can go in the following ways

J – A – C in 2 x 5 = 10 ways or

J – C in 6 ways or

J – B – C in 3 x 4 = 12 ways, Hence total number of ways to go from J to C = 2 x 5 + 6 + 3 x 4 = 28. So this is an example of addition and multiplication both.

Ex 3: In a group of 8 men and 9 women we can pick one man and one woman in 8 × 9 = 72 ways. Notice that we are choosing two persons.

Ex 4: A red die and a blue die are tossed, in how many ways can they land?

Sol. If we view the outcomes as an ordered pair (a, b) then by the multiplication principle we have the 6 × 6 = 36 possible outcomes. i.e.

(1, 1) (1, 2) (1, 3) (1, 4) (1, 5) (1, 6) (4, 1) (4, 2) (4, 3) (4, 4) (4, 5) (4, 6)

(2, 1) (2, 2) (2, 3) (2, 4) (2, 5) (2, 6) (5, 1) (5, 2) (5, 3) (5, 4) (5, 5) (5, 6)

(3, 1) (3, 2) (3, 3) (3, 4) (3, 5) (3, 6) (6, 1) (6, 2) (6, 3) (6, 4) (6, 5) (6, 6)

Ex 5: How many numbers between 10 and 10,000 can be formed by using the digits 1, 2, 3, 5, & 7 if

1. No any digit repeats in any number.

2. Digits can be repeated

Sol. 1. Number of two digit number is of the form TU, here T = ten place, U = unit place.

1. Ten’s place has 5 choices to fill followed by the unit place having remaining 4 choices to fill. Hence, number of two digit number = 5 x 4 = 20.

2. Similarly, three digits numbers type HTU = 5 x 4 x 3 = 60.

3. Number of four digits numbers type THTU = 5 x 4 x 3 x 2 =120.

Hence, required total numbers = 20 + 60 + 120 = 200.

2. If digits can be repeated

1. Number of two digits number = 5 x 5 = = 25.

2. Number of three digits number = 5 x 5 x 5 = = 125.

3. Number of four digits number = 5 x 5 x 5 x 5 = = 625.

Hence, required total numbers = 25 + 125 + 625 = 775.

Ex 6: A multiple-choice test consists of 20 questions, each one with 4 choices. There are 4 ways of answering the first question, 4 ways of answering the second question, etc.

Thus, there are 4²⁰ = 1099511627776 ways to answer the exam

Ex 7: There are 9 · 10 · 10 = 900 positive 3 - digit integers: i.e. 100, 101, 102, . . . , 998, 999.

Since the leftmost integer cannot be 0, there are only 9 choices {1, 2, 3, 4, 5, 6, 7, 8, 9} for it,

There are 10 choices for the second digit and 10 choices to the third digit.

Ex 8: Find the number of non-zero number formed by using the digits 0, 1, 2, 3, 4 less than 4444?

Sol. Numbers of single non-zero digit number = 4.

Numbers of two digits number = 4 x 5 = 20. Since ten’s place can’t be zero.

Numbers of three digits number = 4 x 5 x 5 = 100. Since hundred place can’t be zero.

Numbers of four digits number = 4 x 5 x 5 x 5 = 500. This includes the number 4444.

Hence, number of required number = 4 + 20 + 100 + 500 – 1 = 630.

Ex 9: Find the sum of all the 3 digit number formed by digits 2, 3, 4, 5, if repetition of digit not allowed?

Sol. Number of three digit number formed by digits 2, 3, 4, 5, if repetition of digit not allowed = 4 x 3 x 2 = 24.

I am writing the numbers starting with 2 as shown. Similarly you can write the other number starting with 3, 4, 5 respectively. As you can see, you have written the all possible ways, so frequency of each digit must be same. There are 24 number formed. Number of time digit 2 appear at hundred place = 6, similarly 3, 4, 5 can be came 6 times. Hence sum of digits at hundred place = (2 + 3 + 4 + 5) x 6 = 84. Same situation is happening at unit and ten’s place.

So sum of all the digits = 84 x 100 + 84 x 10 + 84. Think!, So, sum = 9324

Note: PALINDROMES

A palindrome is a symmetric word, phrase, number, or other sequence of symbols or elements, whose meaning may be interpreted the same way in either forward or reverse direction. i.e. ABA, 12321, 22122, 546010645, 112211.

Ex10: How many palindromes of 5 digits are even?

Sol. A five digit even palindrome has the form ABCBA, where A belongs to {2, 4, 6, 8}, and B, C belong to {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Thus there are 4 choices for the first digit, 10 for the second, and 10 for the third. Once these digits are chosen, the palindrome is completely determined. Therefore, there are 4 × 10 × 10 = 400 even palindromes of 5 digits.

Ex11: How many 4 - digit integers can be formed with the set of digits {0, 1, 2, 3, 4, 5} such that no digit is repeated and the resulting integer is a multiple of 3?

Sol. A number is said to be divisible by 3 if sum of its digits divisible by 3. The desired integers have the form D1D2D3D4 with D1 ≠0. Under the stipulated constraints, we must have sum = D1 + D2 + D3 + D4 {6, 9, 12}. We thus consider three cases.

Case I: D1+D2+D3+D4 = 6.

Here we have {D1, D2, D3, D4} = {0, 1, 2, 3}, D1 ≠0.

There are then 3 choices for D1. After D1 is chosen, D2 can be chosen in 3 ways, D3 in 2 ways, and D1 in 1 way. There are thus 3 × 3 × 2 × 1 = 3 · 3! = 18 integers satisfying case I.

Case II: D1+D2+D3+D4 = 9.

Here we have {D1, D2, D3, D4} = {0, 2, 3, 4}, D1 ≠0. or {D1, D2, D3, D4} = {0, 1, 3, 5}, D1 ≠0. Like before,

Reviews for Permutation and Combinations

[Nalinikumar Adapa · Rating: 4 out of 5 stars]

good one for freshers and very helpful for teaching tanqu

[Ritisha Singh · Rating: 5 out of 5 stars]

Awsome book i have ever seen.
Book explain concepts in very easy way. every level is given. I love the way of presentation and the talking of author to the readers. Gr8 Book

[Abha Singh · Rating: 5 out of 5 stars]

Great work by Author!
Permutation and combination is the most difficult topic that i have ever experienced to understand and I went through few books available in market but they all lacked the basic concepts that are very important for this topic.
This book explained every little concepts in very creative and easy way and build my concepts in such way that now i am confident about any PnC problem.

[Ramesh Chandra · Rating: 5 out of 5 stars]

Easy Learning. Quality Work. Now Permutation and combination or Combinatorics is simple!. Must Buy it. :) :)
Book contains the following.
1. Basic Concepts
2. Solved Examples
3. Subjective + Objective Exercise
4. Psychology of students brain
5. Pictorial view of problems
6. IQ – problems to get energy while studying
7. Puzzles to keep interest of students
8. Archive (IIT JEE Main/Advanced, CAT, CBSE Board NCERT + HSC Board) fully solved exercise
9. Ultimate Finish for top order students who have caliber of top 500 Rank.
10. 2 full syllabus Sample papers for IIT JEE Main + IIT JEE Advanced (Indian toughest exam for engineering where 18 Lakh students appear) + Building block Test.
11. Competitive edge.
12. New Generation thinking.
13. Easy way of learning.