permutation and combination
Permutation and Combination
permutation and combination are ways for the arrangement or selection of a group of persons/ numbers etc. Permutation is an act of rearrangement all the members of a set into same sequence or order.It is one of the different arrangement of a group of items where order / sequence / way matters whereas combination is a way of selecting members from the group such that the order of selection doesn't matter.
Fundamental principle of multiplication
It there are two jobs such that one of them can be completed in m ways and second job can be completed in m×n ways.
e.g. If there are 4 ways in which a person can go from X to Y and 7 ways in which he can go from Y to Z , then possible ways to go from X to Z = 4×7 = 28 ways.
Fundamental principle of addition
If there two jobs such that they can be performed independently in m and n ways respectively , then either of the two jobs performed in (m+n) ways.
Permutation
By permutation we mean an arrangement of objects in a particular order.
e.g. If there are three objects a,b and c, then permutation of these objects, taking two at a time are 6 i.e. ab,bc,ac,ba,cb,and ca .These six arrangements are called permutation of three things taken two at a time.
Type of permutation:-
Permutation is generally of two types.
1.Linear permutation:-
If the things are arranged in a row/line , then a permutation is called linear permutation .It is simply written as a permutation .
Number of permutation of n number of n dissimilar things taken r at a time is nPr
Where n! is the product of the first n natural numbers and called 'n-factorial' or 'factorial' denoted by n!
e.g. 5! = 5 × 4 × 3 × 2 × 1 = 120
When n is the negative integer or a factorial, then n! is not defined. Thus n! is defined only for positive integers.
According to the above definition, 0! makes no sense . However , we defined 0! = 1.
n! = n (n - 1) !
2n! = (2n)(2n - 1)(2n - 2)......5×4×3×2×1
= [1×3×5×7.....(2n - 1)] [2×4×6×8.....2n]
= [1×3×5×7.....2n-1][2×2(2)×2(3)....2(n)]
= [1×3×5×7.....2n-1] 2n [1×2×3×4....n]
= 2n n![1×3×5×7.....(2n - 1)]
* Number of permutation of n dissimilar things taken all at a time is nPn
nPn = n!
* Number of permutation of n dissimilar things taken all at a time is nPn
nPn = n!
* Number of permutation of n different things , taken r at a time , when a particular thing is to be always included in each arrangement = r. n-1Pr-1
* Number of permutation of n different things taken all at a time , when m specified things always come together is m! × (n - m + 1) !
* The number of arrangement that can be formed using n things out of which p are identical and of one kind q are identical are of another kind , r of them are all and of third kind and rest are all different, is given by
* Number of permutation of n different things taken all at a time , when m specified things always come together is m! × (n - m + 1) !
* The number of arrangement that can be formed using n things out of which p are identical and of one kind q are identical are of another kind , r of them are all and of third kind and rest are all different, is given by
Some Important Results
1. Without repetition :- The number of permutation of n different things taken r at a time is denoted by nPr or P(n,r)
In other words , arranging the n things taking r at a time means that the arrangement is equivalent to filling 'r' place with n things
'r' places 1 2 3 4 5 ................ r
number of choice n (n - 1) (n - 2) (n - 3) (n - 4) (n - r + 1)
2. With repetition The number of permutation of n different taken r at a time when each things may occur once , twice etc., upto n times (i.e. repeated) in any arrangement is nr.
'r' places 1 2 3 4 5 ................ r
number of choice n (n - 1) (n - 2) (n - 3) (n - 4) (n - r + 1)
2. With repetition The number of permutation of n different taken r at a time when each things may occur once , twice etc., upto n times (i.e. repeated) in any arrangement is nr.
2. Circular permutation
If the things are called around a circle , then a permutation is called a circular permutation.
In circular permutation , there is no first or last place of an object . Hence , the principles of linear permutations are not applicable in circular permutations . In such type of permutations , the relative positions of the things alone need to be taken into consideration and not the actual position.
The number of circular permutations of n different things taken all at a time around a circle is
( n - 1 ) !
Circular permutation Around a Thread
Any arrangement of n different things around a thread or a string in the clockwise or anticlockwise direction are same or they cannot be significantly differentiated, thus total ways (permutation) of arrangement is given by (1/2)(n - 1) !
Combination
Each of the groups or selections that can be made by taking some or all of a number of things without considering the arrangement is called a combination.
e.g. The different combination formed of three letters A,B,C taken two at a time are AB,BC, and AC.
These three groups or selections are called the combination of three things taken two at a time
* Without repetition the number of combinations of n dissimilar things taken r at a time is nCr
*With repetition the number of combinations of n dissimilar things taken all at a time is nCn
Total number of combinations
1.The total number of combinations of (p+q) things taken any number at a time when p things are alike of one kind and q things are alike of a second kind is (p+1)(q+1) - 1..
e.g. There are 4 oranges, 5 pineapples and 7 watermelons , in a fruit basket . The number of ways in fruits is [(4+1)(5+1)(7+1)] - 1
= 5×6×7 - 1 = 239.
2. The total number of ways of selecting one or more objects from n given objects is (2n - 1).
3. Total number of selection of r consecutive things out of n things in a row = n - r + 1.
4. Number of selections of r consecutive things out of n things along a circle = n, when r < n
1,when r = n.
5. Total number of ways in which r things are selected out of n identical things is 1.
6. Total number of ways in which zero or more things are selected out of n identical things = n + 1.
3. Total number of selection of r consecutive things out of n things in a row = n - r + 1.
4. Number of selections of r consecutive things out of n things along a circle = n, when r < n
1,when r = n.
5. Total number of ways in which r things are selected out of n identical things is 1.
6. Total number of ways in which zero or more things are selected out of n identical things = n + 1.
Important formulae
Comments
Post a Comment