Permutation and combination
Permutation
and combination
Basics Concepts and Formulas in Permutations and Combinations
Basics Concepts and Formulas in Permutations and Combinations
Fundamental Principles of
Counting : Multiplication TheoremIf an operation can be performed in m different ways and
following which a second operation can be performed in n different ways, then
the two operations in succession can be performed in m × n different ways.
Fundamental Principles of Counting : Addition TheoremIf an operation can be performed in m different ways and a second independent operation can be performed in n different ways, either of the two operations can be performed in (m+n) ways.
Factorial:
Let n be a positive integer. Then n factorial (n!) can be defined as
n! = n(n-1)(n-2)...1
Examples:5! = 5 x 4 x 3 x 2 x 1 = 120
3! = 3 x 2 x 1 = 6
Special Cases:
a)0! = 1
b)1! = 1
Permutations:
Permutations are the different arrangements of a given number of things by taking some or all at a time
Examples:
a)All permutations (or arrangements) formed with the letters a, b, c by taking three at a time are (abc, acb, bac, bca, cab, cba)
b)All permutations (or arrangements) formed with the letters a, b, c by taking two at a time are (ab, ac, ba, bc, ca, cb)
Combinations:
Each of the different groups or selections formed by taking some or all of a number of objects is called a combination
Examples:Suppose we want to select two out of three girls P, Q, R. Then, possible combinations are PQ, QR and RP. (Note that PQ and QP represent the same selection)
Suppose we want to select three out of three girls P, Q, R. Then, only possible combination is PQR
Difference between Permutations and Combinations and How to Address a Problem
Sometimes, it will be clearly stated in the problem itself whether permutation or combination is to be used. However if it is not mentioned in the problem, we have to find out whether the question is related to permutation or combination.
Consider a situation where we need to find out the total number of possible samples of two objects which can be taken from three objects P,Q , R. To understand if the question is related to permutation or combination, we need to find out if the order is important or not.
If order is important, PQ will be different from QP , PR will be different from RP and QR will be different from RQ
If order is not important, PQ will be same as QP, PR will be same as RP and QR will be same as RQ
Hence,
If the order is important, problem will be related to permutations.
If the order is not important, problem will be related to combinations.
For permutations, the problems can be like "What is the number of permutations the can be made", "What is the number of arrangements that can be made", "What are the different number of ways in which something can be arranged", etc
For combinations, the problems can be like "What is the number of combinations the can be made", "What is the number of selections the can be made", "What are the different number of ways in which something can be selected", etc.
Mostly problems related to word formation, number formation etc will be related to permutations. Similarly most problems related to selection of persons, formation of geometrical figures , distribution of items (there are exceptions for this) etc will be related to combinations.
Repetition:
The term repetition is very important in permutations and combinations.
Consider the same situation described above where we need to find out the total number of possible samples of two objects which can be taken from three objects P,Q , R.
If repetition is allowed, the same object can be taken more than once to make a sample.
i.e., if repetition is allowed, PP, QQ, RR can also be considered as possible samples.
If repetition is not allowed, then PP, QQ, RR cannot be considered as possible samples
Normally repetition is not allowed unless mentioned specifically.
pq and qp are two different permutations ,but they represent the same combination.
Number of permutations of n distinct things taking r at a time:Number of permutations of n distinct things taking r at a time can be given by
nPr = n!(n−r)!=n(n−1)(n−2)...(n−r+1)where 0≤r≤n
If r > n, nPr = 0
Fundamental Principles of Counting : Addition TheoremIf an operation can be performed in m different ways and a second independent operation can be performed in n different ways, either of the two operations can be performed in (m+n) ways.
Factorial:
Let n be a positive integer. Then n factorial (n!) can be defined as
n! = n(n-1)(n-2)...1
Examples:5! = 5 x 4 x 3 x 2 x 1 = 120
3! = 3 x 2 x 1 = 6
Special Cases:
a)0! = 1
b)1! = 1
Permutations:
Permutations are the different arrangements of a given number of things by taking some or all at a time
Examples:
a)All permutations (or arrangements) formed with the letters a, b, c by taking three at a time are (abc, acb, bac, bca, cab, cba)
b)All permutations (or arrangements) formed with the letters a, b, c by taking two at a time are (ab, ac, ba, bc, ca, cb)
Combinations:
Each of the different groups or selections formed by taking some or all of a number of objects is called a combination
Examples:Suppose we want to select two out of three girls P, Q, R. Then, possible combinations are PQ, QR and RP. (Note that PQ and QP represent the same selection)
Suppose we want to select three out of three girls P, Q, R. Then, only possible combination is PQR
Difference between Permutations and Combinations and How to Address a Problem
Sometimes, it will be clearly stated in the problem itself whether permutation or combination is to be used. However if it is not mentioned in the problem, we have to find out whether the question is related to permutation or combination.
Consider a situation where we need to find out the total number of possible samples of two objects which can be taken from three objects P,Q , R. To understand if the question is related to permutation or combination, we need to find out if the order is important or not.
If order is important, PQ will be different from QP , PR will be different from RP and QR will be different from RQ
If order is not important, PQ will be same as QP, PR will be same as RP and QR will be same as RQ
Hence,
If the order is important, problem will be related to permutations.
If the order is not important, problem will be related to combinations.
For permutations, the problems can be like "What is the number of permutations the can be made", "What is the number of arrangements that can be made", "What are the different number of ways in which something can be arranged", etc
For combinations, the problems can be like "What is the number of combinations the can be made", "What is the number of selections the can be made", "What are the different number of ways in which something can be selected", etc.
Mostly problems related to word formation, number formation etc will be related to permutations. Similarly most problems related to selection of persons, formation of geometrical figures , distribution of items (there are exceptions for this) etc will be related to combinations.
Repetition:
The term repetition is very important in permutations and combinations.
Consider the same situation described above where we need to find out the total number of possible samples of two objects which can be taken from three objects P,Q , R.
If repetition is allowed, the same object can be taken more than once to make a sample.
i.e., if repetition is allowed, PP, QQ, RR can also be considered as possible samples.
If repetition is not allowed, then PP, QQ, RR cannot be considered as possible samples
Normally repetition is not allowed unless mentioned specifically.
pq and qp are two different permutations ,but they represent the same combination.
Number of permutations of n distinct things taking r at a time:Number of permutations of n distinct things taking r at a time can be given by
nPr = n!(n−r)!=n(n−1)(n−2)...(n−r+1)where 0≤r≤n
If r > n, nPr = 0
Special
Case: nP0 = 1
nPr is also denoted by P(n,r). nPr has importance outside combinatorics as well where it is known as the falling factorial and denoted by (n)r or nr
Examples
8P2 = 8 x 7 = 56
5P4= 5 x 4 x 3 x 2 = 120
Number of permutations of n distinct things taking all at a time:
Number of permutations of n distinct things taking them all at a time = nPn = n!
Number of Combinations of n distinct things taking r at a time
Number of combinations of n distinct things taking r at a time ( nCr) can be given by
nCr = n!(r!)(n−r)!=n(n−1)(n−2)⋯(n−r+1)r!where 0≤r≤n
If r > n, nCr = 0
Special Case: nC0 = 1
nCr is also denoted by C(n,r). nCr occurs in many other mathematical contexts as well where it is known as binomial coefficient and denoted by (nr)
Examples:
nPr is also denoted by P(n,r). nPr has importance outside combinatorics as well where it is known as the falling factorial and denoted by (n)r or nr
Examples
8P2 = 8 x 7 = 56
5P4= 5 x 4 x 3 x 2 = 120
Number of permutations of n distinct things taking all at a time:
Number of permutations of n distinct things taking them all at a time = nPn = n!
Number of Combinations of n distinct things taking r at a time
Number of combinations of n distinct things taking r at a time ( nCr) can be given by
nCr = n!(r!)(n−r)!=n(n−1)(n−2)⋯(n−r+1)r!where 0≤r≤n
If r > n, nCr = 0
Special Case: nC0 = 1
nCr is also denoted by C(n,r). nCr occurs in many other mathematical contexts as well where it is known as binomial coefficient and denoted by (nr)
Examples:
|
1. Out of 7 consonants and 4 vowels, how
many words of 3 consonants and 2 vowels can be formed?ans) Number of ways of selecting 3 consonants out of 7
= 7C3
Number of ways of selecting 2 vowels out of 4 = 4C2 Number of ways of selecting 3 consonants out of 7 and 2 vowels out of 4 = 7C3 x 4C2 It means that 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 x 4 x 3 x 2 x 1 = 120 Hence, Required number of ways = 210 x 120 = 25200 2. 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? ans) In a group of 6 boys and 4 girls, four children are to be selected such that at least one boy should be there. Hence we have 4 choices as given below We can select 4 boys ------(Option 1). Number of ways to this = 6C4 We can select 3 boys and 1 girl ------(Option 2) Number of ways to this = 6C3 x 4C1 We can select 2 boys and 2 girls ------(Option 3) Number of ways to this = 6C2 x 4C2 We can select 1 boy and 3 girls ------(Option 4) Number of ways to this = 6C1 x 4C3 Total number of ways = (6C4) + (6C3 x 4C1) + (6C2 x 4C2) + (6C1 x 4C3) = (6C2) + (6C3 x 4C1) + (6C2 x 4C2) + (6C1 x 4C1) [Applied the formula nCr = nC(n - r) ] = 15 + 80 + 90 + 24 = 209 3. From a group of 7 men and 6 women, five persons are to be selected to form a committee so that at least 3 men are there on the committee. In how many ways can it be done? ans) From a group of 7 men and 6 women, five persons are to be selected with at least 3 men. Hence we have the following 3 choices We can select 5 men ------(Option 1) Number of ways to do this = 7C5 We can select 4 men and 1 woman ------(Option 2) Number of ways to do this = 7C4 x 6C1 We can select 3 men and 2 women ------(Option 3) Number of ways to do this = 7C3 x 6C2 Total number of ways = 7C5 + [7C4 x 6C1] + [7C3 x 6C2] = 7C2 + [7C3 x 6C1] + [7C3 x 6C2] [Applied the formula nCr = nC(n - r) ] = 21 + 210 + 525 = 756 4. In how many different ways can the letters of the word 'OPTICAL' be arranged so that the vowels always come together?ans) The word 'OPTICAL' has 7 letters. It has the vowels 'O','I','A' in it and these 3 vowels should always come together. Hence these three vowels can be grouped and considered as a single letter. That is, PTCL(OIA). Hence we can assume total letters as 5. and all these letters are different. Number of ways to arrange these letters = 5! = [5 x 4 x 3 x 2 x 1] = 120 All The 3 vowels (OIA) are different Number of ways to arrange these vowels among themselves = 3! = [3 x 2 x 1] = 6 Hence, required number of ways = 120 x 6 = 720 5. In how many different ways can the letters of the word 'CORPORATION' be arranged so that the vowels always come together?ans)The word 'CORPORATION' has 11 letters. It has the vowels 'O','O','A','I','O' in it and these 5 vowels should always come together. Hence these 5 vowels can be grouped and considered as a single letter. that is, CRPRTN(OOAIO). Hence we can assume total letters as 7. But in these 7 letters, 'R' occurs 2 times and rest of the letters are different. Number of ways to arrange these letters = [Loading Maths... ]2520In the 5 vowels (OOAIO), 'O' occurs 3 and rest of the vowels are different. Hence, required number of ways = 2520 x 20 = 50400 6. In how many ways can a group of 5 men and 2 women be made out of a total of 7 men and 3 women?ans)We need to select 5 men from 7 men and 2 women from 3 women Number of ways to do this = 7C5 x 3C2 = 7C2 x 3C1 [Applied the formula nCr = nC(n - r) ] = 21 x 3 = 63 7. In how many different ways can the letters of the word 'MATHEMATICS' be arranged such that the vowels must always come together? ans) The word 'MATHEMATICS' has 11 letters. It has the vowels 'A','E','A','I' in it and these 4 vowels must always come together. Hence these 4 vowels can be grouped and considered as a single letter. That is, MTHMTCS(AEAI). Hence we can assume total letters as 8. But in these 8 letters, 'M' occurs 2 times, 'T' occurs 2 times but rest of the letters are different. Hence,number of ways to arrange these letters = [Loading Maths... ]In the 4 vowels (AEAI), 'A' occurs 2 times and rest of the vowels are different. Hence, required number of ways = 10080 x 12 = 120960 8. There are 8 men and 10 women and you need to form a committee of 5 men and 6 women. In how many ways can the committee be formed? ans)We need to select 5 men from 8 men and 6 women from 10 women Number of ways to do this = 8C5 x 10C6 = 8C3 x 10C4 [Applied the formula nCr = nC(n - r) ] = 56 x 210 = 11760 9. How many 3-letter words with or without meaning, can be formed out of the letters of the word, 'LOGARITHMS', if repetition of letters is not allowed?ans)The word 'LOGARITHMS' has 10 different letters. Hence, the number of 3-letter words(with or without meaning) formed by using these letters = 10P3 = 10 x 9 x 8 = 720 10. In how many different ways can the letters of the word 'LEADING' be arranged such that the vowels should always come together? ans) The word 'LEADING' has 7 letters. It has the vowels 'E','A','I' in it and these 3 vowels should always come together. Hence these 3 vowels can be grouped and considered as a single letter. that is, LDNG(EAI). Hence we can assume total letters as 5 and all these letters are different. Number of ways to arrange these letters = 5! = 5 x 4 x 3 x 2 x 1 = 120 In the 3 vowels (EAI), all the vowels are different. Number of ways to arrange these vowels among themselves = 3! = 3 x 2 x 1= 6 Hence, required number of ways = 120 x 6= 720 |
Domain and Range
Domain and Range of a Function
Domain:The domain of a function is the complete set of possible values of the independent variable.
ie;The domain is the set of all possible
x-values which will make the function "work", and will output real
y-values.
When finding the domain, remember:
The denominator (bottom) of a fraction cannot be zero.
The number under a square root sign must be positive in this work
When finding the domain, remember:
The denominator (bottom) of a fraction cannot be zero.
The number under a square root sign must be positive in this work
eg:
Here is the graph of y=√x+4:
The domain of this function is x≥−4, since x cannot be less than −4. To see why, try out some numbers less than −4 (like −5 or −10) and some more than −4 (like −2 or 8) in your calculator. The only ones that "work" and give us an answer are the ones greater than or equal to −4. This will make the number under the square root positive.
Notes:
The enclosed (colored-in) circle on the point (−4,0). This indicates that the domain "starts" at this point.
How to find the domainIn general, we determine the domainof each function by looking for those values of the independent variable (usually x) which we are allowed to use. (Usually we have to avoid 0 on the bottom of a fraction, or negative values under the square root sign).
Here is the graph of y=√x+4:
The domain of this function is x≥−4, since x cannot be less than −4. To see why, try out some numbers less than −4 (like −5 or −10) and some more than −4 (like −2 or 8) in your calculator. The only ones that "work" and give us an answer are the ones greater than or equal to −4. This will make the number under the square root positive.
Notes:
The enclosed (colored-in) circle on the point (−4,0). This indicates that the domain "starts" at this point.
How to find the domainIn general, we determine the domainof each function by looking for those values of the independent variable (usually x) which we are allowed to use. (Usually we have to avoid 0 on the bottom of a fraction, or negative values under the square root sign).
Range:The range of a function is the complete
set of all possible resulting values of the dependent variable (y,usually),
after we have substituted the domain.
ie;The range is the resulting y-values we
get after substituting all the possible x-values.
How to find the range:
The range of a function is the spread of possible y-values (minimum y-value to maximum y-value)
Substitute different x-values into the expression for y to see what is happening. (Ask yourself: Is yalways positive? Always negative? Or maybe not equal to certain values?)
Make sure you look for minimum and maximum values of y.
Draw a sketch! In math, it's very true that a picture is worth a thousand words.
The range of a function is the spread of possible y-values (minimum y-value to maximum y-value)
Substitute different x-values into the expression for y to see what is happening. (Ask yourself: Is yalways positive? Always negative? Or maybe not equal to certain values?)
Make sure you look for minimum and maximum values of y.
Draw a sketch! In math, it's very true that a picture is worth a thousand words.
Some
Questions:
a)
f(x)=x^2+2 Domain:
The function f(x) = x^2 + 2 is defined for all real values of x
(because there are no restrictions on the value of x).
Hence, the
domain of f(x) is"all real values of x".
Range: Since x^^2 is never negative, x^2 + 2 is never less than 2
Hence, the range of f(x) is"all real numbers f(x)≥2".
We can see that x can take any value in the graph, but the resulting y = f(x) values are greater than or equal to 2.
(b) f(t)=1/t+2
Domain: The function f(t)=1/t+2 is not defined for t = -2, as this value would result in division by zero. (There would be a 0 on the bottom of the fraction.)
Hence the domain of f(t) is"all real numbers except -2"
Range: No matter how large or small t becomes, f(t) will never be equal to zero.
Range: Since x^^2 is never negative, x^2 + 2 is never less than 2
Hence, the range of f(x) is"all real numbers f(x)≥2".
We can see that x can take any value in the graph, but the resulting y = f(x) values are greater than or equal to 2.
(b) f(t)=1/t+2
Domain: The function f(t)=1/t+2 is not defined for t = -2, as this value would result in division by zero. (There would be a 0 on the bottom of the fraction.)
Hence the domain of f(t) is"all real numbers except -2"
Range: No matter how large or small t becomes, f(t) will never be equal to zero.
If we try to solve the equation
for 0, this is what happens:
0=t+21
Multiply both sides by (t + 2) and we get
0=1
This is impossible.So the range of f(t) is"all real numbers except zero".
We can see in the graph that the function is not defined for t=−2 and that the function (the y-values) takes all values except 0.
C)State the domain and range of the following relation. Is the relation a function?
{(2, –3), (4, 6), (3, –1), (6, 6), (2, 3)}
The above list of points, being a relationship between certain x's and certain y's, is a relation. The domain is all the x-values, and the range is all the y-values. To give the domain and the range, I just list the values without duplication:
domain: {2, 3, 4, 6}
range: {–3, –1, 3, 6}
(It is customary to list these values in numerical order, but it is not required. Sets are called "unordered lists", so you can list the numbers in any order you feel like. Just don't duplicate: technically, repetitions are okay in sets, but most instructors would count off for this.)
While the given set does represent a relation (because x's and y's are being related to each other), they gave me two points with the same x-value: (2, –3) and (2, 3). Since x = 2 gives me two possible destinations, then this relation is not a function.
Note that all I had to do to check whether the relation was a function was to look for duplicate x-values. If you find a duplicate x-value, then the different y-values mean that you do not have a function.
D)State the domain and range of the following relation. Is the relation a function?
{(–3, 5), (–2, 5), (–1, 5), (0, 5), (1, 5), (2, 5)}
I'll just list the x-values for the domain and the y-values for the range:
domain: {–3, –2, –1, 0, 1, 2}
range: {5}
0=t+21
Multiply both sides by (t + 2) and we get
0=1
This is impossible.So the range of f(t) is"all real numbers except zero".
We can see in the graph that the function is not defined for t=−2 and that the function (the y-values) takes all values except 0.
C)State the domain and range of the following relation. Is the relation a function?
{(2, –3), (4, 6), (3, –1), (6, 6), (2, 3)}
The above list of points, being a relationship between certain x's and certain y's, is a relation. The domain is all the x-values, and the range is all the y-values. To give the domain and the range, I just list the values without duplication:
domain: {2, 3, 4, 6}
range: {–3, –1, 3, 6}
(It is customary to list these values in numerical order, but it is not required. Sets are called "unordered lists", so you can list the numbers in any order you feel like. Just don't duplicate: technically, repetitions are okay in sets, but most instructors would count off for this.)
While the given set does represent a relation (because x's and y's are being related to each other), they gave me two points with the same x-value: (2, –3) and (2, 3). Since x = 2 gives me two possible destinations, then this relation is not a function.
Note that all I had to do to check whether the relation was a function was to look for duplicate x-values. If you find a duplicate x-value, then the different y-values mean that you do not have a function.
D)State the domain and range of the following relation. Is the relation a function?
{(–3, 5), (–2, 5), (–1, 5), (0, 5), (1, 5), (2, 5)}
I'll just list the x-values for the domain and the y-values for the range:
domain: {–3, –2, –1, 0, 1, 2}
range: {5}
This is another
example of a "boring" function, just like the example on the
previous page: every last x-value goes to the exact same y-value. But each
x-value is different, so, while boring, this relation is indeed a function. In
point of fact, these points lie on the horizontal line y = 5.
There is one other case for finding the domain and range of functions. They will give you a function and ask you to find the domain (and maybe the range, too). I have only ever seen (or can even think of) two things at this stage in your mathematical career that you'll have to check in order to determine the domain of the function they'll give you, and those two things are denominators and square roots.
E)Determine the domain and range of the given function:
The domain is all the values that x is allowed to take on. The only problem I have with this function is that I need to be careful not to divide by zero. So the only values that x can not take on are those which would cause division by zero. So I'll set the denominator equal to zero and solve; my domain will be everything else.
x^2 – x – 2 = 0
(x – 2)(x + 1) = 0
x = 2 or x = –1
Then the domain is "all x not equal to –1 or 2".
The range is a bit trickier, which is why they may not ask for it. In general, though, they'll want you to graph the function and find the range from the picture.
There is one other case for finding the domain and range of functions. They will give you a function and ask you to find the domain (and maybe the range, too). I have only ever seen (or can even think of) two things at this stage in your mathematical career that you'll have to check in order to determine the domain of the function they'll give you, and those two things are denominators and square roots.
E)Determine the domain and range of the given function:
The domain is all the values that x is allowed to take on. The only problem I have with this function is that I need to be careful not to divide by zero. So the only values that x can not take on are those which would cause division by zero. So I'll set the denominator equal to zero and solve; my domain will be everything else.
x^2 – x – 2 = 0
(x – 2)(x + 1) = 0
x = 2 or x = –1
Then the domain is "all x not equal to –1 or 2".
The range is a bit trickier, which is why they may not ask for it. In general, though, they'll want you to graph the function and find the range from the picture.
In this
case:
As I can see from my picture, the graph "covers" all y-values (that is, the graph will go as low as I like, and will also go as high as I like). Since the graph will eventually cover all possible values of y, then the range is "all real numbers".
F)Determine the domain and range of the given function:
The domain is all values that x can take on. The only problem I have with this function is that I cannot have a negative inside the square root. So I'll set the insides greater-than-or-equal-to zero, and solve. The result will be my domain:
–2x + 3 > 0
–2x > –3
2x < 3
x < 3/2 = 1.5
Then the domain is "all x < 3/2".
The range requires a graph. I need to be careful when graphical radicals.
The graph starts at y = 0 and goes down from there. While the graph goes down very slowly, I know that, eventually, I can go as low as I like (by picking an x that is sufficiently big). Also, from my experience with graphing, I know that the graph will never start coming back up. Thenthe range is "y < 0".
G)Determine the domain and range of the given function:
y = –x^4 + 4
This is just a garden-variety polynomial. There are no denominators (so no division-by-zero problems) and no radicals (so no square-root-of-a-negative problems). There are no problems with a polynomial. There are no values that I can't plug in for x. When I have a polynomial, the answer is always that the domain is "all x".
The range will vary from polynomial to polynomial, and they probably won't even ask, but when they do, I look at the picture:
The graph goes only as high as y = 4, but it will go as low as I like. Then:
The range is "all y < 4".
