Counting Techniques

Fundamental Principle of Counting

If event E1 can have n1 different outcomes, event E2 can have n2 different outcomes, ..., and event Em can have nm different outcomes, then it follows that the number of possible outcomes in which composite events E1, E2, ..., Em can have is

n1 × n2 × ... × nm

We call this The Multiplication Principle.
 

Permutation

Permutation is the ordered arrangement of n different objects in k slots in a line.

The permutation of n objects taken k at a time is:

$P(n, \, k) = {^n}P_k = \dfrac{n!}{(n - k)!}$

 

The permutation of n objects taken all at a time is

$^nP_n = n!$

Note: $0! = 1$
 

The number of permutations of n objects taken all at a time in which k1 of the objects are alike, k2 are alike, k3 are alike, and so on...

$N = \dfrac{n!}{k_1! \times k_2! \times k_3! \, \times \, ...}$

 

Cyclic Permutation
The permutation of n objects in a circle is

$N = (n - 1)!$

 

Combination

Combination is the number of unordered selections. The combination of n objects taken k at a time is:

$$C(n, \, k) = {^n}C_k = \binom{n}{k} = \dfrac{n!}{k! \, (n - k)!}$$

 

Note: ${^n}C_n = {^n}C_0 = 1$
 

The number of combinations of n objects taken 1 at a time, 2 at a time, 3 at a time, and so on until n at a time is

$N = 2^n - 1$

 

Partitioning

The number of ways of partitioning n objects into m groups with k1 objects in the first group, k2 objects in the second group, and so on.

If k1 + k2 + k3 + ... + km = n:

$N = \dfrac{n!}{k_1! \times k_2! \times k_3! \, \times \, ... \, \times \, k_m}$

 

If k1 + k2 + k3 + ... + km < n:

$N = {^n}C_{k_1} \times {^{n - k_1}}C_{k_2} \times {^{n - k_1 - k_2}}C_{k_3} \times \, ... \, \times \, {^{n - k_1 - k_2 - \, ... \, - k_{m - 1}}}C_{k_m}$

 

Tags: 
The Multiplication Principle
Permutation
Cyclic Permutation
Combination
Partitioning