Definition

Combinatorics is the branch of mathematics studying the enumeration, combination, and permutation of sets of elements and the mathematical relations that characterize their properties.


Enumeration

Enumeration is a method of counting all possible ways to arrange elements. Although it is the simplest method, it is often the fastest method to solve hard GRE problems and is a pivotal principle for any other combinatorial method. In fact, combination and permutation is shortcuts for enumeration. The main idea of enumeration is writing down all possible ways and then count them. Let's consider a few examples:

Example #1
Q:. There are three marbles: 1 blue, 1 gray and 1 green. In how many ways is it possible to arrange marbles in a row?
Solution: Let's write out all possible ways:

Answer is 6.

In general, the number of ways to arrange n different objects in a row

Example #2
Q:. There are three marbles: 1 blue, 1 gray and 1 green. In how many ways is it possible to arrange marbles in a row if blue and green marbles have to be next to each other?
Solution: Let's write out all possible ways to arrange marbles in a row and then find only arrangements that satisfy question's condition:

Answer is 4.

Example #3
Q:. There are three marbles: 1 blue, 1 gray and 1 green. In how many ways is it possible to arrange marbles in a row if gray marble have to be left to blue marble?
Solution: Let's write out all possible ways to arrange marbles in a row and then find only arrangements that satisfy question's condition:

Answer is 3.


Arrangements of n different objects

Enumeration is a great way to count a small number of arrangements. But when the total number of arrangements is large, enumeration can't be very useful, especially taking into account GRE time restriction. Fortunately, there are some methods that can speed up counting of all arrangements.

The number of arrangements of n different objects in a row is a typical problem that can be solve this way:

1. How many objects we can put at 1st place? n.
2. How many objects we can put at 2nd place? n - 1. We can't put the object that already placed at 1st place.
.....
n. How nany objects we can put at n-th place? 1. Only one object remains.

Therefore, the total number of arrangements of n different objects in a row is

\(N = n*(n-1)*(n-2)....2*1 = n!\)


Combination

A combination is an unordered collection of k objects taken from a set of n distinct objects. The number of ways how we can choose k objects out of n distinct objects is denoted as:

\(C^n_k\)

knowing how to find the number of arrangements of n distinct objects we can easily find formula for combination:

1. The total number of arrangements of n distinct objects is n!
2. Now we have to exclude all arrangements of k objects (k!) and remaining (n-k) objects ((n-k)!) as the order of chosen k objects and remained (n-k) objects doesn't matter.

\(C^n_k = \frac{n!}{k!(n-k)!}\)



Permutation

A permutation is an ordered collection of k objects taken from a set of n distinct objects. The number of ways how we can choose k objects out of n distinct objects is denoted as:

\(P^n_k\)

knowing how to find the number of arrangements of n distinct objects we can easily find formula for combination:

1. The total number of arrangements of n distinct objects is n!
2. Now we have to exclude all arrangements of remaining (n-k) objects ((n-k)!) as the order of remained (n-k) objects doesn't matter.

\(P^n_k = \frac{n!}{(n-k)!}\)

If we exclude order of chosen objects from permutation formula, we will get combination formula:

\(\frac{P^n_k}{k!} = C^n_k\)


Circular arrangements

Let's say we have 6 distinct objects, how many relatively different arrangements do we have if those objects should be placed in a circle.



The difference between placement in a row and that in a circle is following: if we shift all object by one position, we will get different arrangement in a row but the same relative arrangement in a circle. So, for the number of circular arrangements of n objects we have:

\(R = \frac{n!}{n} = (n-1)!\)


Tips and Tricks

Any problem in Combinatorics is a counting problem. Therefore, a key to solution is a way how to count the number of arrangements. It sounds obvious but a lot of people begin approaching to a problem with thoughts like "Should I apply C- or P- formula here?". Don't fall in this trap: define how you are going to count arrangements first, realize that your way is right and you don't miss something important, and only then use C- or P- formula if you need them.