Combination & Permutation

This topic is sometimes confusing when we face them in programming. Here, I am giving some insight that you can remember later.

Permutations ( order does matter)

There are two types:

• Repetition is allowed: examples is like "333".
• Repetition is NOT allowed: examples is "123"

1. Permutation with Repetition
When there n different entities, we can have n choices every draw.
For example, choosing 5 of those items, it has n^5 times choices. ( n x n x n x n x n )

In general, it is represented as n^r, where n is the number of items, and choose r of them.

2. Permutation with NO Repetition
Since there is no repetition is allowed, every draw is reduced by 1.
For example, when there are five different balls with color, you have to choose three of them.
First, you draw blue ball, you cannot draw blue ball again.
In this case, the possible choices are 5 x 4 x 3, because you just choose three from five.
In general, when you draw r from n different items, it is represented by

n!/(n-r)!

Combinations ( order does not matter)

There are two types:

• Repetition is allowed: examples is like (3,3,3,10,10).
• Repetition is NOT allowed: examples is (3,4,5,6,10).

1. Combination with No Repetition

Let's take some example.

When we take 3 out of 5 different items that matters order, it is 5!/(5-3)!.

We have balls number from 1 to 5, and choose balls 1,2, and 3.

There are 6 cases that matter order, and just one case that does not matter order.

Permutation have 3! ( 3x2x1) more times than combination.

In general, when we select r from n items, permutation has r! times more than combination.

So, the formula would be n!/r!(n-r)!.

2. Combination with Repetition

This is little confusing category.

Let's look at the example above.

When we take 3 balls from 5 balls (numbered 1 to 5), we are allowed to draw like (3,3,3).

There are three spots, then we can choose three 3, and none of others (1,2,4,5).

XX333XX

In general, we have r + (n-1) balls and want to choose r of them.

(r+n-1)!/r!(n-1)!