Permutation and Combination Grade-12

 

 

 Permutation And Combination

Unit 1: Permutation and Combination 

 

 

Basic principle of counting,

Permutation of

A.set of objects all different

B.set of objects not all different

C.circular arrangement

D.repeated use of the same object.

 

Combination of things all different, Properties of combination

Multiplication Principle of Counting

 

Statement: If one activity can be performed in m different ways, following which another activity can be performed in n different ways and the events are independent then both the activities together can be performed in: 𝑚×𝑛ways

Remarks: This counting principle can be extended to any finite number of tasks.

Example 1 :

Rohan has 3 shirts and 2 pants in how many ways can he select a shirt and a pant ?

Task 1st: Selection of a T-shirt. There are 3 choices.

Task 2nd: Selection of a Pants. There are 2 choices.

Multiplication Principle of Counting

Hence by multiplication principle of counting there 3×2=6ways

Addition Principle of counting

Mutually Exclusive Activities

 

Two or more activities are said to be mutually exclusive if they can not be accomplished at the same time.

Remarks: This counting principle can be extended to any finite number of tasks.

Example: with one throw of a die you can not score a three and a five at the same time.

Statement: if two task are mutually exclusive, but one can be accomplished in m ways and other in n ways then either of the task can be accomplished in 𝑚+𝑛ways.

Addition Principle of counting

 

Example: Suppose there are 5 red pens and 3 black pens in a stationary. In how many ways can a student  purchase either a red or black pen, if he wants to buy only one pen.

Soln:

Task A: Purchase a black pen

Task B: Purchase a red pen

Since there are 5 red pens, so the student can purchase a red pen in 5 ways. Similarly he can purchase a black pen in 3 ways. Since these two task are mutually exclusive So, using the addition principle of counting the student can purchase either of the pen in 5+3=8 ways

Theorem 1:Total no of permutation of n distinct object taken r at a time with out repetition is 𝑃𝑛,𝑟=𝑛!𝑛−𝑟!, n≥𝑟

Proof:

The number of permutations  of n distinct object taken r at a time is equivalent to the number of ways in which r  positions can be filled of by  these n distinct objects.

To Fill the 1stposition we have n no. of choices

After filling up the 1st position there remains n-1 objects. So, the 2ndposition can be filled up in n-1 ways.

After filling up the 2nd  position there remains n-2 objects. So, the 3rdposition can be filled up in n-2 ways.

Similarly, the rthposition can be filled up in n-(r-1) ways.

 

By multiplication principle of counting all the r positions can be filled one after another in 𝑛𝑛−1𝑛−2𝑛−3…𝑛−𝑟+1ways. Therefore the number of permutation of n distinct objects taken r at a time is given by ;

𝑃𝑛,𝑟=𝑛𝑛−1𝑛−2𝑛−3…𝑛−𝑟+1

=𝑛(𝑛−1)(𝑛−2)(𝑛−3)…(𝑛−𝑟+1)(𝑛−𝑟)(𝑛−𝑟−1)…3.2.1(𝑛−𝑟)(𝑛−𝑟−1)…3.2.1

=𝑛!𝑛−𝑟!

Hence proved

Remarks: total no of permutations of n distinct object taken all at a time is given by:

𝑃𝑛,𝑛=𝑛𝑃𝑛=𝑛!𝑛−𝑛!=𝑛!0!=𝑛!1=𝑛!

Theorem 2:Total no of permutation of n distinct object taken r at a time with repetition is 𝑃𝑛,𝑟=𝑛𝑟

Proof:

The number of permutations  of n distinct object taken r at a time with repetition is equivalent to the number of ways in which r  positions can be filled of by  these n distinct objects and each object can be use as often as we wants.

Anyone of the n given object can be put in 1st position. So, the 1stposition can be filled up in n ways.

After filling up the 1st position the 2ndposition can also be filled up in n ways as the object occupying the first place may occupy the second place. Hence the second place can be filled in n ways.

Similarly, each of the remaining positions can be filled up in n ways. Hence by multiplication principle of counting the r positions can be filled in 𝑛×𝑛×𝑛×𝑛×⋯×𝑛=𝑛𝑟

Theorem 3:

If there are n objects of which p objects are one kind q objects are a second kind, r objects of third kind and all the rest (if any) are different, then the number of permutation of these objects taken all at a time is :

𝑛!𝑝!𝑞!𝑟!

Example: In how many ways can the letters of the words MISSISSIPPI be arranged?

Solution

There are 11 letters in the word MISSISSIPPI in which there are 4 I’s 4 S’s and 2 P’s

Setting n=11, p=4 ,q=4 & r=2

Total no of arrangements=11!4!4!2!

Circular permutation

 

Theorem 4: Total no of permutations of n distinct objects arranged in a line is n!

Example: In how many ways can the letters A, B, C & D be arranged in a line?

Solution: Total no of letters (n)=4. These 4 letters can be arranged in a line in 4!=24 ways