Permutation And Combination

Permutations and Combination, the various ways in which objects from a set may be selected, generally without replacement, to form subsets. This selection of subsets is called permutation when the order of selection is a factor, a combination when order is not a factor.

Factorial:

The product of ‘n’ natural number 1, 2, 3.—-n is denoted by n! and read as n factorial

0! is defined to equal 1.

n! = 1 x 2 x 3 x …….x (n – 1) x n

1! = 1

0! = 1

n! = n. (n-1)! = n (n-1)(n-2)….etc

Permutation

The concepts and differences between permutations and combinations can be illustrated by an examination of all the different ways in which a pair of objects can be selected from five different objects—

such as the letters A, B, C, D, and E. If both the letters selected and the order of selection are considered, then the following 20 outcomes are possible:

Here, each of these 20 different possible selections is called a permutation. They are called the permutations of five objects taken two at a time, and the number of such permutations possible is denoted by the symbol:

5P2, read – 5 permute 2.

Permutations are the different ways in which a collection of items can be arranged.

If there are n objects available from which to select, and permutations (P) are to be formed using k of the objects at a time, the number of different permutations possible is denoted by the symbol nPk or P(n ,r) .

nPk = n!(n − k)!

where n! is “n factorial

Properties of Permutation

1). nPk = n(n – 1)(n – 2)……1 = n!
2). nP0 = 1
3). nP1 = n
4). nPn-1 = n!
5). nPrnPr-1 = n – r + 1

For Example:

12!= 12 x 11 x 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1

The permutations of 2, 3, 4, 5 are:
• 5432, 5423, 5324, 5342, 5234, 5243, 4532, 4523, 4325, 4352, 4253, 4235, 3542, 3524, 3425, 3452, 3254, 3245, 2543, 2534, 2435, 2453, 2354, 2345.

Some Examples:

1). A boy has nine trousers and 12 shirts. In how many different ways can he select a trouser and a shirt?

Solution: The boy can select one trouser in nine ways.
The boy can select one shirt in 12 ways.
The number of ways in which he can select one trouser and one shirt is 9 x 12 = 108 ways.

2). How many three-letter words are formed using the letters of the word TIME?

Solution: The number of letters in the given word is four.
The number of three-letter words that can be formed using these four letters is ⁴P₃ = 4x 3 x 2 = 24.

3). Using all the letters of the word “THURSDAY”, how many different words can be formed?

Solution: Total number of letters = 8
Using these letters the number of 8 letters words formed is ⁸P₈ = 8!.

Combination

For combinations, k objects are selected from a set of n objects to produce subsets without ordering. The previous permutation example:

The corresponding combination, the AB and BA subsets are no longer different selections;
So by eliminating such cases there remain only 10 different possible subsets—AB, AC, AD, AE, BC, BD, BE, CD, CE, and DE.
The number of such subsets is denoted by:
nCk or C(n ,r) , read n choose k. For combinations, since k objects have k! arrangements, there are k! identical permutations for each choice of k objects;
hence dividing the permutation formula by k! : the following combination formula:

nCk = n!k! (n − k)! , (0 ≤ k ≤ n)

Properties of Combination

1). nCn = 1
2). nC0 = 1
3). nC1 = n
4). nCr = nC(n-r)
5). nCr = nPrr!
6). nCr + nCr-1 = n+1Cr
7). nC0 + nC1 + nC2 + —-+ nCn = 2n
8). nC0 + nC2 + nC4+—- = nC1 + nC3 + nC5+—- = 2n-1
9). If nCr = nCp then either
r = p or r + p = n

Some Examples:

1).In how many ways can a coach choose three swimmers from among five swimmers?

Solution:
There are 5 swimmers to be taken 3 at a time.
C(5,3) = P(5,3)/3! =5 x 4 x 3/3 x 2 x1= 10
The coach can choose the swimmers in 10 ways.

2). Six friends want to play enough games of chess to be sure everyone plays everyone else. How many games will they have to play?

Solution:
There are 6 players to be taken 2 at a time.
C(6,2)=P(6,2)/2!=6 x 5/2 x 1=15.
They will need to play 15 games.

3). Out of 7 consonants and 4 vowels, how many words of 3 consonants and 2 vowels can be formed?

Solution:
Number of ways of selecting 3 consonants from 7 = 7C3
Number of ways of selecting 2 vowels from 4 = 4C2

Number of ways of selecting 3 consonants from 7 and 2 vowels from 4
= 7C3 × 4C2
=(7×6×5/3×2×1)×(4×3/2×1)=210

we can have 210 groups where each group contains total 5 letters :
3 consonants and 2 vowels.

Number of ways of arranging 5 letters among themselves
=5!=5×4×3×2×1=120

Hence, the number of ways
=210×120=25200

4). In a group of 6 boys and 4 girls, four children are to be selected. In how many different ways can they be selected such that at least one boy should be there?

Solution: In a group of 6 boys and 4 girls, four children are to be selected such that at least one boy should be there.

We can select 4 boys …(1)
Number of ways to this = 6C4

We can select 3 boys and 1 girl …(2)
Number of ways to this = 6C3 × 4C1

We can select 2 boys and 2 girls …(3)
Number of ways to this = 6C2 × 4C2

We can select 1 boy and 3 girls …(4)
Number of ways to this = 6C1 × 4C3

Total number of ways:
= 6C4 + 6C3 × 4C1 + 6C2 × 4C2 + 6C1 × 4C3
= 6C2 + 6C3 × 4C1 + 6C2 × 4C2 + 6C1 × 4C1 [∵ nCr = nC(n-r)]
=(6×5/2×1)+(6×5×4/3×2×1)×4+(6×5/2×1)×(4×3/2×1)+6×(4)
=15+80+90+24=209

Leave a Reply

Your email address will not be published. Required fields are marked *