HUIJZER.XYZ

Combinations and permutations

2020-06-28

Counting is simple except when there is a lot to be counted. Combinations and permutations are such a case; they are about counting without replacement. Suppose we want to count the number of possible results we can obtain from picking kk numbers, without replacement, from an equal or larger set of numbers, that is, from nn where knk \leq n. When the same set of numbers in different orders should be counted separately, then the count is called the number of permutations. So, if we have some set of numbers and shuffle some numbers around, then we say that the numbers are permuted. When the same set of numbers in different orders should be counted only once, then the count is called the number of combinations. Which makes sense since it is only about the combination of numbers and not the order.

The equations for permutations and combinations can be derived as follows: We can depict this little universe UU containing nn numbers as

U={1,...,n} U = \{ 1, ..., n \}

and the set of kk drawn numbers as

Sa={s1,...,sk}. S_a = \{ s_1, ..., s_{k} \}.

We could split UU up into UaU_a and UbU_b since we know that knk \leq n,

Ua={1,...,k},Ub={k+1,...,n} U_a = \{ 1, ..., k \}, U_b = \{ k+1, ..., n \}

and define SS to be the union of SaS_a and SbS_b such that S=U=n|S| = |U| = n,

Sa={s1,...,sk},Sb={sk+1,...,sn}. S_a = \{ s_1, ..., s_k \}, S_b = \{ s_{k+1}, ..., s_n \}.

For the number of permutations, denoted by PknP^n_k, let us fill SS by drawing numbers from UU. Then, observe that to fill s1s_1 we can pick from nn numbers. To fill s2s_2 we can pick from n1n - 1 numbers. Continuing this, we can fill SS in n(n1)0=n!n \cdot (n - 1) \cdot \cdot \cdot 0 = n! different ways (where the order is important). However, this was not the original goal. Instead, we want to fill only SaS_a. To this end, remove all the possibilities from SbS_b. Note that Sa=k|S_a| = k and Sb=nk|S_b| = n - k. So, the number of permutations is given by,

Pkn=n!(nk)!. P^n_k = \frac{n!}{(n-k)!}.

For the number of combinations, denoted by CknC^n_k or (nk){n\choose k}, we expect a smaller number of total possibilities since we ignore different orderings. This smaller number is simply all the possible orderings for SaS_a, that is, k!k!. So, the number of combinations is given by

Ckn=(nk)=n!k!(nk)!. C^n_k = {n\choose k} = \frac{n!}{k!(n-k)!}.