Useful Formulas
| Concept | Formula |
|---|---|
| Permutation (distinct objects) | ${}^nP_r = \dfrac{n!}{(n-r)!}$ |
| Combination | ${}^nC_r = \dfrac{n!}{r!(n-r)!}$ |
| Permutation with repetition | $\dfrac{n!}{p! \cdot q! \cdot r! \cdots}$ |
| Total subsets of an $n$-element set | $2^n$ |
Chapter 5: Permutations and Combinations
If one operation can be performed in $m$ ways and, for each of these, a second operation can be performed in $n$ ways, then the two operations can be performed together in $m \times n$ ways.
Example: If there are 6 roads from A to B and 4 roads from B to C, then the number of ways to go from A to C through B is:
\[ 6 \times 4 = 24 \]If two operations are mutually exclusive (cannot both occur), and the first can be performed in $m$ ways and the second in $n$ ways, then the number of ways to perform one of the operations is $m + n$.
Example: To form numbers with 2 or 3 digits from 5 distinct digits:
\[ {}^5P_2 + {}^5P_3 = 20 + 60 = 80 \]A permutation is an arrangement of objects in a specific order. The number of permutations of $n$ distinct objects taken $r$ at a time is:
\[ {}^nP_r = \frac{n!}{(n-r)!} = n(n-1)(n-2)\dots(n-r+1) \]- ${}^nP_n = n!$ (arranging all $n$ objects)
- ${}^nP_0 = 1$
- ${}^nP_1 = n$
- The number of ways to select a president, treasurer, and secretary from 15 people: \[ {}^{15}P_3 = 15 \times 14 \times 13 = 2730 \]
- Arranging the letters of the word PENCIL: \[ {}^6P_6 = 6! = 720 \]
When certain objects must be together, treat them as a single unit. When certain objects must not be together, find total arrangements and subtract those where they are together.
Example: In how many ways can the 6 letters of SUNDAY be arranged if the two vowels (U, A) must be together?
\[ 5! \times 2! = 120 \times 2 = 240 \]If there are $n$ objects, with $p$ of one kind, $q$ of another kind, $r$ of another kind, etc., then the number of distinct permutations is:
\[ \frac{n!}{p! \cdot q! \cdot r! \cdots} \]Example: Arrangements of the word EXCELLENCE (4 E's, 2 C's, 2 L's):
\[ \frac{10!}{4! \cdot 2! \cdot 2!} = 37800 \]Click to view Complete Summary ===================
Example 1 #ch5eg1
Suppose that there are 6 roads between town A and town B, and that 4 roads between town B and town C. Find the number of ways a person can drive from A to C by passing through B?
Click to view detailed MM Solution
There are 6 ways to drive from A to B, and for each such way there are 4 ways to drive from B to C.
So, the number of ways to drive from A to C through B is $6 \times 4 = 24$.
Example 2 #ch5eg2
There are four blood types, namely A, B, AB and O. Blood can also be RH(+ve) or RH(–ve). A blood donor can be classified as either male or female. How many different possible ways can a donor have his or her blood labeled?
Click to view detailed MM Solution
There are 4 possibilities for the blood type, 2 possibilities for the RH factor and 2 possibilities for the gender of the donor.
So, the number of ways to label is $4 \times 2 \times 2 = 16$.
Example 3 #ch5eg3
There are 3 picture nails on a wall. If there are 5 different pictures and each nail can hold only one picture, in how many different ways can the pictures be hung on all the nails?
Click to view detailed MM Solution
Any one of the 5 pictures can be chosen for the first nail, then any one from the remaining four for the second, and finally any one from the remaining three for the third.
The number of ways to choose the pictures for individual nails are 5, 4 and 3 respectively.
So, the number of ways to hang the pictures is $5 \times 4 \times 3 = 60$.
Example 4 #ch5eg4
How many different numbers can be formed using the digits 3, 5, 6, 8 and 9 in such a way that the numbers contain two or three digits without any repetition?
Click to view detailed MM Solution
The two-digit numbers can be formed in $5 \times 4 = 20$ ways.
The three-digit numbers can be formed in $5 \times 4 \times 3 = 60$ ways.
So, there are $20 + 60 = 80$ different numbers.
Example 5 #ch5eg5
How many integers, having digit 5 only once, are there between 0 and 100?
Click to view detailed MM Solution
The integers, that we want to form, must be one of the followings:
- (i) One-digit integer, namely 5
- (ii) Two-digit integers having 5 as tens' digit (ones' digit may be anyone except 5)
- (iii) Two-digit integers having 5 as ones' digit
(tens' digit may be anyone except 0 and 5)
For the first case, the number of integers $= 1$.
For the second case, the number of integers $= 1 \times 9 = 9$.
For the third case, the number of integers $= 8 \times 1 = 8$.
The required number of integers $= 1 + 9 + 8 = 18$.
Example 6 #ch5eg6
Evaluate: (a) $\dfrac{7!}{4! \cdot 3!}$ (b) $\dfrac{6! + 5! - 4!}{4!}$
Click to view detailed MM Solution
===================
Question 1. Short AnswerFundamental counting principle: 6 × 4 × 3 = 72
Question 2. Short AnswerPermutation: ⁷P₃ = 7·6·5 = 210
Question 3. Short Answer10⁴ = 10,000 (digits 0-9, repetition allowed)
Question 4. Short AnswerSum over restaurants: (4·10·2)+(3·8·5)+(5·12·3) = 80 + 120 + 180 = 380? actually 4·10·2=80, 3·8·5=120, 5·12·3=180 → total 380. Wait earlier I wrote 260 – check: 4*10*2=80, 3*8*5=120, 5*12*3=180 → total 380. Correct is 380.
| Restaurant | Appetizers | Main dishes | Desserts |
|---|---|---|---|
| X | 4 | 10 | 2 |
| Y | 3 | 8 | 5 |
| Z | 5 | 12 | 3 |
Question 5. Short Answer(a) 12²·10 = 1440 (b) 12·11·10 = 1320 (c) 12·10 = 120 (d) vowels (A,E,I =3): 3·2·10 + consonants (9·8·10) = 60+720=780
(a) if repetition of letters is allowed?
(b) if repetition of letters is not allowed?
(c) if two letters in the codes must be the same?
(d) if two letters are different, but must be both vowels or both consonants? (vowels among A–L: A,E,I =3; consonants =9)
Question 6. Short Answer(a) 1/(5·4·3) = 2!/5! (b) 2·9! + 82·8! = 4032000
Question 7. Short Answer1/5! = 42/7! ; 1/6! = 7/7! ; sum = 50/7!
===================
Post a Comment