Permutation and Combination

Lets start with definitions.

Permutation is the number of subsets you can form from a set considering the order as a factor / order is important.

Eg.
set = A,B,C,D        
size of set = n = 4
size of subset = k = 2 (pick 2 at a time)

How many subsets of 2 elements can be form? 
Order is a factor / important. (this means AB not equal to BA)

Answer:
No. of Subsets = AB AC AD BA BC BD CA CB CD DA DB DC = 12 = nPk

*******************************************************

Combination is the number of subsets you can form from a set without considering the order as a factor / order is not important.

Eg.
set = A,B,C,D        
size of set = n = 4
size of subset = k = 2 (pick 2 at a time)

How many subsets of 2 elements can be form? 
Order is not a factor / not important. (this means AB is equal to BA)

Answer:
No. of Subsets = AB AC AD BA BC BD CA CB CD DA DB DC = 6 = nCk 

***********************i++**************************

Another form of permutation is the number of ways a set of numbers can be arranged. Just like a 4 digits lottery, when you want to buy all the posssible permutations of a set of 4 numbers.

Eg.
Number 1234 can be arrange in how many ways?
n = 4
Possible permutations for 1234 = 24
Formula:
Possible Permutations = n! = 4*3*2*1 = 24
Actually the formula is similar to the one on top. Just that in this case, k = 4.
Therefore:
(n – k)! = (4 – 4)! = 0! = 1
Why 0! = 1? I will explain that in another post.

What if one of the numbers are repeated.
Like 1231 instead of 1234.
Then the formula n! , will need to be divided by the factorial of the number of repeats.
Possible permutations for 1231 = 4! / 2! = 12
The 2 at the denominator comes from 1, which is repeated twice.

What if 2 numbers are repeated. Like 1221 instead of 1234 or 1231. Then the denominator will be the product of two factorials(2!*2!) , since there are 2 numbers which is repeated 2 times each.
The formula:
possible permutations = 4! / (2!*2!) = 6
Manually listing them:
1221 1122 2211 1212 2112 2121

A 9 digits example:
121337999
n = 9, 2 numbers repeated twice , 1 number repeated 3 times. What is the number of permutations?
possible permutations = 9! / (2!*2!*3!) = 15120
If none of the numbers are repeated:
possible permutations = 9! = 362880