Combinatorics

Permutations

Keywords: Permutation without Repetition with Repetition

Permutation without Repetition

A permutation is an arrangement, or listing, of n distinct objects in which the order is important.

Total number of permutations in case of n elements:

P n = n · ( n 1 ) · ( n 2 ) · . . . · 2 · 1 = n !

Example:

In case of 4 elemts: {a,b,c,d}: n = 4 , P 4 = 4 ! = 4 · 3 · 2 · 1 = 24

abcd bacd cabd dabc
abdc badc cadb dacb
acbd bcad cbad dbac
acdb bcda cbda dbca
adbc bdac cdab dcab
adcb bdca cdba dcba

Permutation with Repetition

A permutation is an arrangement, or listing, of n objects in which the order is important. The elements are repeated. Number of repetations:

k 1 , k 2 , k 3 , . . . , k r ; ( k 1 + k 2 + k 3 + . . . + k r n )

Total number of permutations:

P n k 1 , k 2 , k 3 , . . . , k r = n ! k 1 ! · k 2 ! · k 3 ! · . . . · k r !

Example:

In case of 7 elemet: {a,a,a,a,b,b,c} first element repeats 4 times, second element repeats 2 times: n=7, k1=4,k2=2, k1=1

Total number of permutations:

P74,2,1=7!4!·2!·1!=105