Android app on Google Play

Combinatorics

Combinatorics is the branch of mathematics dealing with the study of countable discrete structures. This is where you count the number of combinations or permutations of something is counted, when selecting objects from different groups.

The addition principle of counting

Another word for the addition principle could be the “either-or”-principle, because you can choose only one object out of several sets of objects.

For example:

You are allowed to take EITHER a vegetable OR a fruit.

Vegetables:
cucumber, carrot, radish

Fruits:
orange, apple

There are three vegetable and two fruits. Since we are allowed to choose EITHER a vegetable OR a fruit, the total number of different choices you can make is determined by adding the number of objects in the one group by the numbers of objects in the other group:

3 + 2 = 5

The total number of different choices is 5.

The multiplication principle

The multiplication principle, also known as the “both-and”-principle, says that you’ll have to choose one object from each group of objects.


For example:

We have to choose BOTH a vegetable AND a fruit.
Combinatorics tree diagram

Vegetables:
cucumber, carrot, radish

Fruits:
orange, apple

Since we have to take both a vegetable and a fruit, we can calculate the number of choices on the basis of the multiplications principle.

3*2=6

You can make six different choices.

Another way to illustrate the number of possible choices is by making a tree diagram. See the figure to the right.

The factorial function

In combinatorics you often need to make calculations where you multiply a series of descending natural numbers, like for eksample:

7*6*5*4*3*2*1

This can be simplified with the factorial function denoted by the first number followed by an exclamation point “!”.

For example:
Seven factorial
7!=7*6*5*4*3*2*1

Four factorial
4!=4*3*2*1

Combinations and permutations

When objects are selected randomly from several groups of objects, you can either calculate the number of possible combinations or the number of possible permutations, and the objects can either be selected with repetition or not.

Combinations: The order of the objects doesn’t matter.
Permutations: The order of the objects does matter.
Repetition is allowed: Each object can be selected more than one time.
No repetition: Each object can be selected only once.

Permutation without repetition:

When counting the number of ways in which you can select r objects in a specific order out of n objects, and each object cannot be selected more than one time, it is called permutation without repetition:

$^nP$_r=\binom{n}{r}=frac{n!}{(n-r)!}


For example:
An association with 8 members wants to choose a management board with one chairman, one vice-chairman, and one treasurer. Each member of the board can only hold one seat.

n = 8, because the association has 8 members.
r = 3, because 3 of them must be elected to the management board.

Since the situation is “permutation without repetition”, the number of ways, in which the management board can be composed, is given by:

$^8P$_3=\binom{8}{3}=frac{8!}{(8-3)!}=frac{8!}{5!}=frac{8*7*6*5*4*3*2*1}{5*4*3*2*1}=frac{40320}{120}=336

The management board can be composed in 336 different ways.

Permutation with repetition:

When counting the number of ways in which you can select r objects in a specific order out of n objects, and it doesn’t matter if an object is selected more than one time, it is called permutation with repetition:

Number of permutations=n^r

For example:
The pin code of a credit card has 4 digits, each of which can be the numbers from 0 to 9. How many different pin codes can be made for such a credit card?

n = 10, because there are 10 different digits to choose from.
r = 4 because, we need to find 4 digits for the pin code.

Since it’s doesn’t matter if the same digit appears more than one time in the pin code, it’s a “permutation with repetition”-situation, and the number of possible pin codes is given by:

Number of codes=10^4=10*10*10*10=10000

You can make 10,000 different pin codes.

Combination without repetition:

When counting the number of ways in which you can select r objects out of n objects without caring about the order, and each object cannot be selected more than one time, it is called combination without repetition:

$^nC$_r=\binom{n}{r}=frac{$^nP$_r}{r!}=frac{n!}{(n-r)!*r!}

For example:
A family of 5 people have to choose 2 people to do the dishes. In how many ways can the two people be chosen?

n = 5, because there are 5 people in the family.
r = 2, because two need to be chosen.

Since it doesn’t matter who is working together, and since one person can’t be chosen twice to do the dishes it’s a “combination with repetition”-situation:

$^5C$_2=\binom{5}{2}=frac{5!}{(5-2)!*2!}=frac{5*4*3*2*1}{3*2*1*2*1}=10

The dish washing team can be composed in 10 different ways.

Combination with repetition:

When counting the number of ways in which you can select r objects out of n objects without caring about the order, and it doesn’t matter if an object is selected more than one time, it is called combination with repetition:

Number of combinations=frac{(n-1+r)!}{(n-1)!*r!}

For example:
You come to an ice cream stand having 7 different types of ice cream to choose from. How many different ice creams can you get, if you are allowed to have 3 ice cream cones, and if it doesn’t matter that two or all three of the cones are of the same type?

n = 7, because there are 7 different types of ice cream to choose from.
r = 3, because you are allowed to have 3 ice cream cones.

Since it doesn’t matter in which order the ice cream cones are selected and if some of them are the same, it’s a “combination with repetition”-situation:

Number of ice creams=frac{(n-1+r)!}{(n-1)!*r!}=frac{(7-1+3)!}{(7-1)!*3!}=frac{9!}{6!*3!}=frac{362880}{4320}=84

You can get 84 different ice creams.

Calculate numbers of permutations or combinations

The total number of obcjects to choose from (n): 
The number of objects you want to choose (r): 
Permutation or combination: 
Repetition: