Permutation and Combination
In this chapter, we shall learn about some basic counting techniques which will be useful in determining the number of different ways of arranging and selecting objects without actually listing them.
Fundamental principle of multiplication- Suppose student Mohan has 3 pants and 2 shirts. How many different pairs of a pant and shirt can he dress up with?
There are three ways in which a pant can be chosen.
For 1st pant-------------any of the two shirts can be chosen---------2 ways
For 2nd pant-------------any of the two shirts can be chosen---------2 ways
For 3rdpant--------------any of the two shirts can be chosen----------2 ways
For every pant, there are two shirts, therefore, he can dress up with 3x2 = 6.   
Let the three pants be P1, P2 and P3 and two shirts be S1, S2 and S3. Above can be easily understood by using this diagram:



For every pant, there are two shirts, therefore, he can dress up in 3x2 = 6 ways.   
Number of pair of pants and shirts he can choose = (No. of pants he can choose) x (No. of shirts he can choose)
Problems of above type are solved by using multiplication principle or fundamental principle of multiplication which states that:
If an event can occur in m different ways and another event can occur in n different ways, number of ways in which both events m & n can be performed is equal to m x n.
Fundamental principle of addition- If an event can occur in m different ways and another event can occur in n different ways, number of ways in which event m or n can be performed is equal to m + n.
Q) In a debate competition, there are 5 candidates from science side, 4 from commerce side and 3 from humanities side. In how many ways a winner of competition can be selected?
Ans) A winner out of science students can be selected in 5 ways.
A winner out of commerce students can be selected in 4 ways.
A winner out of humanities students can be selected in 3 ways.
An overall winner of competition can be selected in 5 + 4 + 3 = 12 ways.
Q) In a shop, there are 10 shirts and there are 10 pants
1)      In how many ways can a pair of pant and a pair of shirt can be selected.
2)      In how many ways can a pair of cloth can be selected.
Factorial notation- The notation n! (factorial n) represents the product of first n natural numbers. Factorial of only natural numbers is defined.
For example, 5! = 1 x 2 x 3 x 4 x 5
0! = 1
n! = n (n - 1)! = n (n-1) (n-2)! = n (n-1) (n-2) (n-3)! (provided n ≥ 3)
n! tool for arrangement- Number of ways in which, we can palace N things in N places = N!
or No. of ways in which we can arrange n things = N!
Q) Make 8 by using only zeros and by using any mathematical operation?
Q) How many 4-digits numbers can be formed from digits 1, 2, 3 and 4?
Q) How many 7 letter words with or without meaning can be formed from letters M, N, O, P, Q, R and S?
Q) Of the different words that can be formed from the letters of the word BEGINS how many words begins with B and end with S?
The number of arrangements (or permutations) of n objects, where p1 objects are of first kind, p2 objects are of second kind, ----- pk objects are of kth kind and the rest, if any, are of different kind is (n!)/(p1.p2…pk). 
Q) Find the number of permutations (or arrangements) of letters of word ALLAHABAD?
Question based on combination of fundamental principle of multiplication and n! principle
Q) In how many ways can the 7 letters M, N, O, P, Q, R and S be arranged so that P and Q occupy continuous position?
Combination (nCr) tool for arrangement- This tool is used for specific situation of counting, the number of ways of selecting r things out of n distinct things = [ nCr].
The number of ways of selecting r things out of n identical things = 1.
nCr = n! /r! x (n-r)!
important points regarding nCr
1)     nCr + nCr – 1 = n + 1Cr
2)     nCx = nCy
It implies that (x = y) or (x + y = n)
3)      When n is constant and r is variable, for nCr to be greatest
a)       If n is even, r = n/2
b)      If n is odd, r = (n + 1)/2 or (n-1)/2
Q) A committee of 5 members is to be formed from group of 8 members. In how many ways can this be done?
Q) How many chords can be drawn through 21 points on a circle?
Q) In how many ways can a student choose a programme of 5 courses if 9 courses are available and 2 specific courses are compulsory for every student?
Question based on combination of fundamental principle of multiplication and Combination
Q) A committee of 3 persons is to be constituted from a group of 2 men and 3 women. In how many ways can this be done? How many of these committees would consist of 1 man and 2 women?
Q) In how many ways can one select a cricket team of eleven from 17 players in which only 5 players can bowl if each cricket team of 11 must include exactly 4 bowlers?
Q) A bag contains 5 black and 6 red balls. Determine the number of ways in which 2 black and 3 red balls can be selected?
·         If balls of same color are distinct.
·         If balls of same color are identical.
 Q) A committee of 5 members is to be formed from group of 8 members. In how many ways can this be done?
Permutation (arrangement) nPr
Number of ways in which r things out of N distinct things can be selected and can be arranged at r different places = NCr x r! = NPr
Q) In how many ways 5 fruits out of group of 8 fruits can be selected and arranged at 5 different places?
Arrangement of objects not all distinct
Number of arrangements of N things out of which P1 are of one type, P2 are of second type, P3 are of third type and the rest are all different = (N! / (P1! P2! P3!))
Q) How many words with or without meaning can be formed with the letters of following words: -
1) ALLAHABAD
2) MISSISSIPPI
3) APPLE
Circular permutations
There are three objects A, B and C. We can linearly arrange these three objects in 3! = 6 possible ways. There are following linear arrangements of these three objects: - ABC, ACB, CAB, CBA, BAC, BCA.





If we talk about circular arrangements, we can observe from figure 1 that three arrangements ACB, CBA and BAC are same. We can observe from figure 2 that three arrangements ABC, BCA and CAB are same.
We conclude that there are two ways of circular arrangements of these three objects. This happens because there is no point of a starting point on a circular arrangement. Three objects can be arranged in ((3!)/3) ways = 2! Ways.
Generalizing the whole concept, on circular table, N objects can be arranged in (N - 1)! Ways or (N!)/N.
Q) In how many ways five guests can sit on a round table?
If we talk about necklace or garland, where we can turn necklace or garland and clockwise and anti-clockwise arrangements are not different. No. of circular arrangements of N different beads of necklace = (N - 1)! /2.
Q)  How many different garlands can be formed from eight different flowers?
Selection of any number of things out of N distinct things
If there are N distinct things, 1 thing out of N distinct thing can be chosen in NC1.  
m things out of N distinct things can be chosen in NCm ways.
Any number (0 or 1 or 2) of things out of N can be chosen in
  (NC0 + NC1 + NC2 + NC3 + NC4 + NC5 . . . . . . . . . . . .. NCN) ways. (By using combination and fundamental principle of addition)
NC0 + NC1 + NC2 + NC3 + NC4 + NC5 . . . . . . . . . . . .. NCN = 2N
The number of selections of 1 or more things out of N different things =
NC1 + NC2 + NC3 + NC4 + NC5 . . . . . . . . . . . .. NCN = 2N- 1
Q) A boy has gone to a library and there are 200 different books in library. In how many ways he can pick one or more books from library?
Number of diagonals of N sided polygon
Number of diagonals of N sided polygon = (Number of straight lines formed by joining N points) – (Number of sides) = NC2 – N
Number of straight lines formed by N points of which l are collinear
NC2 straight lines are formed by joining N points which are not collinear and only 1 straight line is formed by joining R collinear points. Therefore, number of straight lines formed by joining N points of which l are collinear =
NC2 -  lC2 + 1
Number of Triangles formed by N points of which l are collinear
NC3 triangles are formed by joining N points which are not collinear and no triangle is formed by joining R collinear points. Therefore, number of triangles formed by joining N points of which l are collinear =
NC3 -  lC3
Number of parallelograms formed by intersection of m parallel lines with n parallel lines
Two lines out of m parallel lines can be selected in mC2 ways and two lines out of n parallel lines can be selected in nC2 ways. Therefore, parallelogram is formed by selecting two lines out of m parallel lines and two lines out of n parallel lines. Number of parallelograms formed by intersection of m parallel lines with n parallel lines =
mC2 x nC2

Comments

Post a Comment

Popular posts from this blog

                                            Probability Probability means the chance of the occurrence of an event. In layman terms, we can say that it is the likelihood that something- that is defined as the event will or will not occur. In probability, our first approach is to define the event and then we approach to find out the probability of an event or we approach to find out the chance of the occurrence of an event. Sample space This is defined with respect to a random experiment and denotes the set representing all the possible outcomes of the random experiment. For example: - Sample space when a coin is tossed is S = (Head, Tail). Sample space when a dice is thrown is S = (1, 2, 3, 4, 5, 6). Sample space when two dices are thrown is S = (1, 1) (1, 2) (1, 3) (1, 4) (1, 5) (1, 6)     ...
Read more
Image
                        COORDINATE GEOMETRY Two real number lines that are perpendicular to each other and that intersect at their respective zero points define a rectangular coordinate system . Often called the x-y coordinate system or x-y plane . The horizontal number line is called the x-axis and the vertical number line is called the y-axis . The point where the two axes intersect is called the origin , denoted by O. The positive half of the x-axis is to the right of the origin, and the positive half of the y-axis is above the origin. The two axes divide the plane into four regions called quadrants I , II , III , and IV , as shown in the figure below. Each point P in the x-y plane can be identified with an ordered pair (x, y) of real numbers and is denoted by P (x, y). The first number is called the x-coordinate, and the second number is called the y-coordinat...
Read more