powered by Tutorvista.com

Sales Toll Free No: 1-855-666-7440

Combinatorics is the branch of mathematics that studies the different possible arrangements of elements of finite sets and the enumeration techniques for these arrangements. Primitively it deals with counting of permutations and combinations and progressively study advanced counting patterns in algebra, calculus and discrete mathematics.

Let us illustrate this problem with a tree diagram.

For making an identity card, a letter is first chosen from the three letters A, B, C. Then each of two digits is chosen from 1 and 2. So totally there are 3 x 2 x 2 = 12 identity cards as seen in the last column.

The counting done for this tree diagram is based on Fundamental counting principle.

Fundamental Counting Principle: If an event can occur in m ways and another event can occur followed by the first event in n ways, then the two events can together occur in m x n ways.

The fundamental counting principle can be extended to any number of events. If there are n events which can occur independently in $n_{1}$, $n_{2}$......

$n_{n}$ ways then the n events can together occur in $n_{1}n_{2}........n_{n}$ ways.

Example:

If a motor vehicle license plate consists of one letter followed by two digits and again followed by three letters, where the letters and digits can repeat, find the number of license plates which can be made this way.

Letter |
Digit |
Digit | Letter | Letter | Letter |

26 | 10 | 10 | 26 | 26 | 26 |

Using fundamental counting principle, the number of plates that can be made = 26 x 10 x 10 x 26 x 26 =

The notation used to represent a factorial is

For example 4! = 4.3.2.1 = 24.

Suppose you want seat three persons in a row. The first seat can be occupied by any one of the three. Having the first seat occupied, the second seat can be occupied in two ways and finally the last seat is taken by the remaining person.

Seat 1 |
Seat 2 |
Seat 3 |

3 ways | 2 ways | 1 way |

Same way n objects can be arranged in n(n-1)(n-2)........3.2.1 = n! ways.

8 books can arranged on a shelf in a row in 8! = 40320 ways.

Suppose we are to pick 'r' things from n objects and arrange them. We use the notation $_{n}P_{r}$ or P(n,r) to denote this.

Using fundamental counting principle this would be equal to n(n -1)(n - 2)(n -3)..........(n- r +1).

8 students participate in a running race. In how many ways the first,second and third positions can be determined if no tie is allowed?

This problem can be solved using two methods:

The first three positions can be decided in = 10 x 9 x 8 =

$_{n}P_{r}=\frac{n!}{(n-r)!}=\frac{10!}{7!}=\frac{10.9.8.7!}{7!}= 10.9.8$ =

The number of permutations of n objects with one item repeated $x_{1}$ times, the other repeated $x_{2}$times and so on is equal to

$\frac{n!}{x_{1}!x_{2}!.......x_{k}!}$

where $x_{1}+x_{2}+......x_{k}=n$

Suppose you want to select three candidates for a job out of 10 shortlisted. This is a case of pure selection where the order does not matter. We need to find the number of combinations of selecting 3 people from 10.

The notation used to denote the number of combinations of n objects selecting r at a time is $_{n}C_{r}$ or C(n,r).

The number of permutations of n things taken r at a time consists of two events. That is selecting r items first, and then arranging these r items. As the r items can be arranged in r! ways, the permutation can be equated to

$_{n}P_{r}=_{n}C_{r}.r!$. From this equation we can deduce the formula for combination as

$_{n}C_{r}=\frac{_{n}P_{r}}{r!}=\frac{n!}{(n-r)!r!}$

There are 12 English lessons in a text book. The teacher wants each of the student to summarize any two these lessons. In how many ways two lessons can be chosen from 12?

We need to find $_{12}C_{2}$

$_{12}C_{2}=\frac{12!}{10!2!}= \frac{12.11}{2}$ = 66 ways.

In a given problem if order is important for counting, use the permutation formula. If the situation is purely of selection then use the combination formula.

Number of ways of both events A and B occur =( Number of ways of event A can occur) X (Number of ways of event B can occur)

Number of ways either event A or event B occurs = (Number of ways of event A can occur) + (Number of ways of event B can occur)