Top

# Combinatorics

Combinatorics is defined as the mathematics of counting. It is a field of mathematics, which is concerned with solving problems in both, pure mathematics (algebra, probability theory, geometry etc.) as well as applied mathematics (optimization, statistical physics, computer science etc.).

 Related Calculators Combinatorics Calculator

## Applications of Combinatorics

Given below are some of the applications of combinatorics.

Combinatorics used in Pure Mathematics:

Permutation: The number of ways to arrange n objects is n!. We define P(n, r) = $\frac{n!}{(n - r)!}$ to be the number of ways that r objects can be chosen from n objects. A different ordering of the choice of object is considered to be a different way.

Combination: Combination differs from permutation in that, we are not concerned with the order by which objects are taken. We define nCr = $\frac{n!}{(n-r)! r! }$ where, 1 $\leq$ r $\leq$ n, to be the number of ways that r objects can be chosen from n objects. Choices which only differ in the ordering of objects are considered to be the same.

The pigeonhole principle: If (n + 1) objects are divided into n groups, there is at least one group which contains at least 2 objects. If m objects are divided into n groups, where m > kn, there is at least one group which contains at least (k + 1) objects.

Set theory: A set A is a collection of objects. We define |A| or n(A) to be the number of elements in A.

Combinatorics used in Applied Mathematics:
• For optimization of discrete and combinatorial objects.
• For problems in physics, particularly, statistical physics.
• For problems related to operations research, algorithm theory and computational complexity theory.
Examples:
1. Given 5 people and 5 seats, there are 5! = 120 ways for these people to be sitting.
2. 8 people compete in an athletic race. The number of possibilities that they won the gold, silver and bronze medals is P(8, 3) = 336.
3. Among a class of 40 students, 3 of them are chosen as monitors. The number of different possibilities is 40C3 = 9880.

### Solved Examples

Question 1: Prove that among any 52 positive integers, there must be two of them whose sum of difference is divisible by 100.
Solution:
Consider the last two digits of the 52 integers only.
Now, define the 51 sets: {00}, {01, 99}, â€¦,{49, 51} and {50}.
If any two of the 52 integers lie in the same set, then their sum or difference is divisible by 100.
Since there are 52 integers but only 51 sets, there must be two of them lying in the same set and the proposition is proved.

Question 2: Solve the following integer programming problem:
Maximize: F = 3x + 7y
Subject to:
$x\leq 3.5$
5x - 4y $\leq$ 10
4/7x + 2y $\leq$ 9
x, y $\geq$ 0 and integer.
Solution:
The integer optimal solution will be x = 1 and y = 4, as shown in the following graphical representation.

And, the optimal, non integer, the solution will be x = 3.5 and y = 3.5, F = 35, as shown in the following graphical representation.

*AP and SAT are registered trademarks of the College Board.