Combinatorics

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.

Applied Combinatorics

Suppose the Identity cards provided to the organizers of a club event consists a letter from {A,B,C} and two digits each from {1,2}. How many such number cards are printed?

Let us illustrate this problem with a tree diagram.

Applied Combinatorics

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
LetterLetter
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 = 1,757,600.

Permutations

Key word:  Factorial
The notation used to represent a factorial is '!'. For any positive integer n, n factorial is n! = n(n-1)(n-2)(n-3).......3.2.1.
For example 4! = 4.3.2.1 = 24.
0! is defined to be equal to 1.
Permutation is an arrangement of objects in a particular order.

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
    3   x    2      x   1       = 3! = 6 ways.

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

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.
The number of permutations of n things taken 'r' at a time = $_{n}P_{r}$ = $\frac{n!}{(n-r)!}$.

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

Example:
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:

Method 1: Using fundamental counting principle

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

Method 2: Using Permutation formula
      

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

Permutations with repetitions:

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$


Combinations

A combination is a selection in which the order does not matter.

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!}$
Example:
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.

Multiple events:

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)


Combinatorics Problems

The counting techniques like fundamental counting principle, permutations and combinations are frequently used in finding the outcomes of an experiment. For finding the probabilities of events these formulas are often used to determine the number of outcomes in the events and sample space.