Factorial notation: Let [latex]n[/latex] be the positive integers. Then factorial [latex]n[/latex] is denoted by [latex]n[/latex]! is defined as [latex]n[/latex]! = [latex]n(n - 1)(n - 2)......3.2.1.[/latex]

Example: 6! = 6 x 5 x 4 x 3 x 2 x 1 = 720

Fundamental Principle of Counting:

• Let us now solve the problem mentioned in the introduction. We will write [latex]t_{1}[/latex], [latex]t_{2}[/latex] to denote trains from Bangalore to Itarsi and [latex]T_{1}[/latex], [latex]T_{2}[/latex], [latex]T_{3}[/latex], for the trains from Itarsi to Allahabad. Suppose I take [latex]t_{1}[/latex] to travel from Bangalore to Itarsi. Then from Itarsi I can take [latex]T_{1}[/latex] or [latex]T_{2}[/latex] or [latex]T_{3}[/latex].


• So the possibilities are [latex]t_{1}T_{1}[/latex], [latex]t_{2}T_{2}[/latex] and [latex]t_{3}T_{3}[/latex] where [latex]t_{1}T_{1}[/latex] denotes travel from Bangalore to Itarsi by [latex]t_{1}[/latex] and travel from Itarsi to Allahabad by [latex]T_{1}[/latex]. Similarly, if I take [latex]t_{2}[/latex] to travel from Bangalore to Itarsi, then the possibilities are [latex]t_{2}T_{1}[/latex], [latex]t_{2}T_{2}[/latex] and [latex]t_{2}T_{3}[/latex]. Thus, in all there are 6(2×3) possible ways of travelling from Bangalore to Allahabad.


• Here we had a small number of trains and thus could list all possibilities. Had there been 10 trains from Bangalore to Itarsi and 15 trains from Itarsi to Allahabad, the task would have been very tedious. Here the Fundamental Principle of Counting or simply the Counting Principle comes in use:
  If any event can occur in m ways and after it happens in any one of these ways, a second event can occur in n ways, then both the events together can occur in m \times n ways.

Example 1: How many multiples of 5 are there from 10 to 95?
Solution:

As you know, multiples of 5 are integers having 0 or 5 in the digit to the extreme right (i.e. the unit's place).
The first digit from the right can be chosen in 2 ways.
The second digit can be any one of 1, 2, 3, 4, 5, 6, 7, 8, 91, 2, 3, 4, 5, 6, 7, 8, 9 i.e. There are 9 choices for the second digit.
Thus, there are 2 × 9 = 2 × 9 = 18 multiples of 5 from 10 to 95.

Example 2: In a city, the bus route numbers consist of a natural number less than 100, followed by one of the letters A,B,C,D,E and F. How many different bus routes are possible?
Solution:

The number can be any one of the natural numbers from 1 to 99.
There are 99 choices for the number.
The letter can be chosen in 6 ways.
Number of possible bus routes are 99 × 6 = 99 × 6 = 594

Example 3: There are 3 questions in a question paper. If the questions have 4,3 and 2 solutions respectively, find the total number of solutions.
Solution:

Here question 1 has 4 solutions, question 2 has 3 solutions and question 3 has 2 solutions.
=> By the multiplication (counting) rule,
Total number of solutions=4×3×2==4×3×2= 24

Permutations: Each of the different arrangement of a given set by taking some or all elements at a time are called permutations.
Example: All permutations(or arrangements) made with letters u, v, w taking two at a time are uv, vu, uz, zu, vz, zv.

• Number of permutations of 'n' dissimilar things taken 'n' at a time is [latex]n_{{p}_{n}}[/latex].


• If, out of 'n' things 'p' are exactly a like of kind, 'q' are exactly a like of second kind and 'r' are exactly a like of third kind and the rest of all different, then the number of permutations of 'n' things taken all at a time is [latex]\frac{n!}{p!q!r!}[/latex]


• Number of circular permutations of 'n' different things taken all at a time is (n 1)!.

Example: Suppose you want to arrange your English, Hindi, Mathematics, History, Geography and Science books on a shelf. In how many ways can you do it?
Solution:

We have to arrange 6 books.
The number of permutations of n objects is [latex]n![/latex] = [latex]n.(n−1).(n−2)...2.1[/latex]
Here [latex]n[/latex] = 6 and therefore, number of permutations is 6.5.4.3.2.1 = 720.

The number of permutations of [latex]r[/latex] objects out of [latex]n[/latex] objects is

[latex]n[/latex]([latex]n[/latex]−1)..([latex]n[/latex]−[latex]r[/latex]+1)

The number of permutations of [latex]r[/latex] objects out of [latex]n[/latex] objects is usually denoted by [latex]^{n}P_{r}[/latex].

Thus, [latex]^{n}P_{r}[/latex] = [latex]n[/latex]([latex]n[/latex]−1)([latex]n[/latex]−2)...([latex]n[/latex]−[latex]r[/latex]+1)

Example: If you have 6 New Year greeting cards and you want to send them to 4 of your friends, in how many ways can this be done?
Solution:

We have to find number of permutations of 4 objects out of 6 objects.
This number is [latex]^{6}P_{4}[/latex] = 6(6−1)(6−2)(6−3) = 6 x 5 x 4 x 3 = 360
Therefore, cards can be sent in 360 ways.
So, using the factorial notation, this formula can be written as follows:
[latex]^{n}P_{r}[/latex] = [latex]\frac{n!}{(n−r)!}[/latex]

Permutations under Some Conditions:

• Number of permutations of [latex]n[/latex] different things, taken [latex]r[/latex] at a time, when a particular thing is to be always included in each arrangement is: [latex]r^{n - 1}P_{r - 1}[/latex]


• Number of permutations of [latex]n[/latex] different things, taken [latex]r[/latex] at a time, when a particular thing is to be always included in each arrangement is: [latex]^{n - 1}P_{r}[/latex]


• Number of permutations of [latex]n[/latex] different things, taken all at a time, when m specified things always come together is: [latex]m! \times (n - m + 1)![/latex]


• Number of permutations of [latex]n[/latex] different things, taken all at a time, when m specified never come together is: [latex]n! − [m! \times (n − m + 1)!][/latex]


• The number of permutations of [latex]n[/latex] dissimilar things taken [latex]r[/latex] at a time when [latex]k(< r)[/latex] particular things always occur is: [latex][^{n − k}P_{r−k}][/latex] x [latex][^{r}P_{k}][/latex]


• The number of permutations of [latex]n[/latex] dissimilar things taken [latex]r[/latex] at a time when [latex]k[/latex] particular things never occur is: [latex]^{n−k}P_{r}[/latex]


• The number of permutations of [latex]n[/latex] dissimilar things taken [latex]r[/latex] at a time when repetition of things is allowed any number of times is: [latex]n^{r}[/latex]


• The number of permutations of [latex]n[/latex] different things, taken not more than [latex]r[/latex] at a time, when each thing may occur any number of times is: [latex]n[/latex] + [latex]n^{2}[/latex] + [latex]n^{3}[/latex] + . . . + [latex]n^{r}[/latex] = [latex]\frac{n(n^{r} - 1)}{n - 1}[/latex]


• The number of permutations of [latex]n[/latex] different things taken not more than [latex]r[/latex] at a time: [latex]^{n}P_{1}[/latex] + [latex]^{n}P_{2}[/latex] + [latex]^{n}P_{3}[/latex] + . . . + [latex]^{n}P_{r}[/latex]

Example 1: Suppose 7 students are staying in a hall in a hostel and they are allotted 7 beds. Among them, Parvin does not want a bed next to Anju because Anju snores. Then, in how many ways can you allot the beds?
Solution:

Let the beds be numbered 1 to 7.
Case 1:
Suppose Anju is allotted bed number 1.
Then, Parvin cannot be allotted bed number 2.
So Parvin can be allotted a bed in 5 ways.
After allotting a bed to Parvin, the remaining 5 students can be allotted beds in 5! ways.
So, in this case the beds can be allotted in 5 × 5! = 600 ways.
Case 2:
Anju is allotted bed number 7.
Then, Parvin cannot be allotted bed number 6
As in Case 1, the beds can be allotted in 600 ways.
Case 3:
Anju is allotted one of the beds numbered 2, 3, 4, 5 or 6
Parvin cannot be allotted the beds on the right hand side and left hand side of Anju's bed.
For example, if Anju is allotted bed number 2, beds numbered 1 or 3 cannot be allotted to Parvin.
Therefore, Parvin can be allotted a bed in 4 ways in all these cases.
After allotting a bed to Parvin, the other 5 can be allotted a bed in 5! ways.
Therefore, in each of these cases, the beds can be allotted 4 × 5! = 480 ways.
=> The beds can be allotted in:
2 × 600 + 5 × 480 = 1200 + 2400 = 3600 ways

Example 2: In how many ways can an animal trainer arrange 5 lions and 4 tigers in a row so that no two lions are together?
Solution:

They have to be arranged in the following way:
| L | T | L | T | L | T | L | T | L |
The 5 lions should be arranged in the 5 places marked 'L'.
This can be done in 5! ways.
The 4 tigers should be in the 4 places marked 'T'.
This can be done in 4! ways.
Therefore, the lions and the tigers can be arranged in 5! × 4! = 2880 ways

Example 3: How many arrangements of the letters of the word ‘BENGALI’ can be made

(i) If the vowels are never together.
(ii) If the vowels are to occupy only odd places.

Solution:

There are 7 letters in the word ‘Bengali; of these 3 are vowels and 4 consonants.
(i) Considering vowels a, e, i as one letter, we can arrange 4 + 1 letters in 5! ways in each of which vowels are together. These 3 vowels can be arranged among themselves in 3! ways.
=> Total number of words = 5! × 3!
= 120 × 6 = 720
So there are total of 720 ways in which vowels are ALWAYS TOGEGHER.
Now,
Since there are no repeated letters, the total number of ways in which the letters of the word ‘BENGALI’ cab be arranged:
= 7! = 5040
So,
Total no. of arrangements in which vowels are never together:
= ALL the arrangements possible - arrangements in which vowels are ALWAYS TOGETHER
= 5040 − 720 = 4320
(ii) There are 4 odd places and 3 even places. 3 vowels can occupy 4 odd places in [latex]^{4}P_{3}[/latex] ways and 4 constants can be arranged in [latex]^{4}P_{4}[/latex] ways.
=> Number of words = [latex]^{4}P_{3}[/latex] x [latex]^{4}P_{4}[/latex] = 576.

Combination: Each of the different groups or selections which are formed by taking some or all of a number of things irrespective of order is called a combination.
Example: All the combinations formed by a, b, c taking two at a time are ab, bc, ca.
Note that ab and ba are two different permutations but represent the same combination.

• Number of combinations of 'n' dissimilar things taken 'r' at a time is [latex]n_{{c}_{r}}[/latex].


• The total number of combinations of (p + q) things taken one or more at a time. When p things are a like of one kind and 'q' things are alike of second kind is (p + 1)(q + 1) - 1.


• If some or all of n things be taken at a time then the number of combinations will be [latex]2^n - 1[/latex].Fundamental theorem: If there are 'm' ways of doing a thing and 'n' ways of doing another thing then the total number of ways of doing both the things one after the another is 'mn' ways.

Example 1: Find the number of subsets of the set {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11} having 4 elements.
Solution:

Here the order of choosing the elements doesn't matter and this is a problem in combinations.
We have to find the number of ways of choosing 4 elements of this set which has 11 elements.
This can be done in:
[latex]^{11}C_{4}[/latex] = [latex]\frac{11 \times 10 \times 9 \times 8}{1 \times 2 \times 3 \times 4}[/latex] = 330 ways.

Example 2: 12 points lie on a circle. How many cyclic quadrilaterals can be drawn by using these points?
Solution:

For any set of 4 points we get a cyclic quadrilateral. Number of ways of choosing 4 points out of 12 points is [latex]^{12}C_{4}[/latex] = 495
Therefore, we can draw 495 quadrilaterals.

Example 3: The Indian Cricket team consists of 16 players. It includes 2 wicket keepers and 5 bowlers. In how many ways can a cricket eleven be selected if we have to select 1 wicket keeper and at least 4 bowlers?
Solution:

We are to choose 11 players including 1 wicket keeper and 4 bowlers
or, 1 wicket keeper and 5 bowlers.
Number of ways of selecting 1 wicket keeper, 4 bowlers and 6 other players
= [latex]^{2}C_{1}[/latex] X [latex]^{5}C_{4}[/latex] X [latex]^{9}C_{6}[/latex] = 840
Number of ways of selecting 1 wicket keeper, 5 bowlers and 5 other players
= [latex]^{2}C_{1}[/latex] X [latex]^{5}C_{5}[/latex] X [latex]^{9}C_{5}[/latex] = 252
=> Total number of ways of selecting the team:
= 840 + 252 = 1092

Definition of rank: If the words, that can be formed from the letters of a given word, are listed as in a dictionary and if given word appears at the nth place in this list, then n is called the rank of the given word(in the list).

1. Number of all permutations of n things, taken r at a time, is given by: [latex]n_{{p}_{r}}[/latex] = [latex]n(n -1)(n - 2).....(n - r + 1)[/latex] = [latex]\frac{n!}{(n - r)!}[/latex]
Example: [latex]8_{{p}_{2}}[/latex] = 8 x 2 = 16
2. If there are n objects of which [latex]p_{1}[/latex] are alike of one kind; [latex]p_{2}[/latex] are alike of another kind; [latex]p_{3}[/latex] are alike of third kind and so on and [latex]p_{r}[/latex] are alike of rth kind, such that ([latex]p_{1} + p_{2} + p_{3 + ...... + p_{r}}[/latex]) = n. Then, number of permutations of these n objects = [latex]\frac{n!}{(p_{1}!)(p_{2}!)......p_{r}!}[/latex]
3. The number of all combinations of n things, taken r at a time is given by: [latex]n_{{c}_{r}}[/latex] = [latex]\frac{n!}{(r!)(n - r)!}[/latex] = [latex]\frac{n(n - 1)(n - 2)....(n - r + 1)}{1.2.3....(r - 1).r}[/latex]
4. [latex]n_{{c}_{r}}[/latex] =[latex]n_{{c}_{n - r}}[/latex]
5. If [latex]n_{{c}_{r}}[/latex] = [latex]n_{{c}_{s}}[/latex] then either r = s or r + s = n
6. [latex]n_{{p}_{r}}[/latex] = n - [latex]1_{{p}_{r}} + r * n - 1_{{p}_{r - 1}}[/latex]
7. [latex]n_{{c}_{r}}[/latex] = n - [latex]1_{{c}_{r - 1}} + n - 1_{{c}_{r}}[/latex]
8. [latex]\frac{n_{{p}_{r}}}{n - 1_{{p}_{r - 1}}}[/latex] = n and [latex]\frac{n_{{c}_{r}}}{n - 1_{{c}_{r - 1}}}[/latex] = [latex]\frac{n}{r}[/latex]
9. [latex]\frac{n_{{p}_{r}}}{n_{{p}_{r - 1}}}[/latex] = n - r + 1 and [latex]\frac{n_{{c}_{r}}}{n_{{c}_{r - 1}}}[/latex] = [latex]\frac{n - r + 1}{r}[/latex]

1. How many words can be formed by using all letters of the word 'PATNA'?
Solution:

Given
Word is 'PATNA'.
Word PATNA contains 5 different letters.
Therefore, required number of words = [latex]5_{{p}_{5}}[/latex] = 5! = 5 x 4 x 3 x 2 x 1 = 120.

2. In how many ways can a cricket eleven be chosen out of a batch of 15 players?
Solution:

Given that
Cricket batch contains 11 members as a team.
Therefore, Required number of ways = [latex]15_{{c}_{11}}[/latex] = [latex]15_{{c}_{11}}[/latex] = [latex]15_{{c}_{4}}[/latex] = [latex]\frac{15 * 14 * 13 * 12}{4 * 3 * 2 * 1}[/latex] = 1365.

3. How many words can be formed by using all the letters of the word 'SUCCESS', so that the vowels are never together?
Solution:

Given,
Word SUCCESS contains 7 letters.
Taking the vowels UE together, treat them as a letter.
Then, the letters to be arranged are SCCSS(UE).
This group has 6 letters of which c and s occurs 2 times, and others are different.
Number of ways of arranging these letters = [latex]\frac{6!}{2! * 2!}[/latex] = 180.
Now 2 vowels can be arranged among themselves in 2! = 2 ways
Therefore, required number of ways = 180 * 2 = 360.

4. Compute: [latex]\frac{35!}{30!}[/latex]?
Solution:

Given,
[latex]\frac{35!}{30!}[/latex] = [latex]\frac{35 * 34 * 33 * 32 * 31 * (30!)}{(30!)}[/latex] = 38955840. Therefore,
[latex]\frac{35!}{30!}[/latex] = 38955840.

5. Find the value of:

(i) [latex]20_{{c}_{18}}[/latex] ? (ii) [latex]5_{{p}_{4}}[/latex] ?

Solution:

(i) Given, [latex]20_{{c}_{3}}[/latex] = [latex]\frac{20 * 19 * 18}{3!}[/latex] = [latex]\frac{20 * 19 * 18}{3 * 2 * 1}[/latex] = 1140
(ii) Given, [latex]5_{{p}_{4}}[/latex] = [latex]\frac{5!}{4!}[/latex] = [latex]\frac{5 * 4 * 3 * 2 * 1}{4 * 3 * 2 * 1}[/latex] = 5