Counting: Disposition, Permutations and Combinations

Combinatorics is "The FIne Art of Counting". Coutnign what? Counting elements from one or more sets.

Fundamental Principle of Counting (Combinatorics)

If something can be chosen, or can happen, or be done, in n different ways, and, after that has happened, something else can be chosen in p different ways, then the number of ways of choosing both of them is n*p.

There are 3 main definitions to worry about:

Disposition: counting the different ways of arranging item from a set of n elements
Permutation: counting the different ways of putting k elements from a set of n elements in k distinct positions
Combinations: counting the different ways of choosing k elements from a set of n elements

Disposition

Disposition. the choosing of n different things, one by one, and arranging in ordered positioning (first, second, third and so on). The amount is named D(n) = (n!)

In fact, we have D(n) = n * (n-1) * ... * (1) possible choices

n at first place
(n-1) at second place
(n-2) at third place
...
(1) at last place

A s a definition, D(n) = n!

Permutation

Permutation. the choosing of n different things taken m at time (having m<n), tracking order, the positioning (first, second, third and so on). The amount is named P(n,m) or nPm = (n!)/(n-k!)

We have n * (n-1) * ... * (n-k+1) possible choices:

n at first place
(n-1) at second place
(n-2) at third place
...
(n-k+1) at k-th place

The other (n-k) are left unchoosen

Factorial Representation

For short, since

n * (n-1) * ... * (n-k+1) = n * (n-1) * ... * (1)/k * (k-1) * ... * (1) = n!/(n-k)!

nPk = n/(n − k)

Combination

Combination. the choosing of n different things taken m at time (having m<n), without tracking order, positioning is unrelevant (building an heap). The amount is named C(n,m) or nCm = (n!)/k!(n-k!)

We have n * (n-1) * ... * (n-k+1)/k! possible choices but loosing information about order (grouped by k!)

Factorial Representation

nCk = n/(n − k) k