Massive Math Stuff: Combinations and Permutations

Thursday, June 26, 2014

Combinations and Permutations

If the order doesn't matter, it is a Combination.
If the order does matter it is a Permutation.

A Permutation is an ordered Combination.
Permutations

Repetition is Allowed: such as the lock above. It could be "333". n × n × ... (r times) = n^r
No Repetition: for example the first three people in a running race. You can't be first andsecond.

Permutations without Repetition
if we wanted to select all: then it's n!.
The factorial function (symbol: !) just means to multiply a series of descending natural numbers.
if we wanted to select just r, then it's

where n is the number of things to choose from, and we choose r of them
(No repetition, order matters)

$^n\operatorname P_k = n\cdot(n-1)\cdot(n-2)\cdots(n-k+1)$

Combinations

Combinations without Repetition

The easiest way to explain it is to:

assume that the order does matter (ie permutations),
then alter it so the order does not matter

where n is the number of things to choose from, and we choose r of them
(No repetition, order doesn't matter)

$\binom nk = ^n\operatorname C_k = \frac{n(n-1)\ldots(n-k+1)}{k(k-1)\dots1}$
So remember, do the permutation, then reduce by a further "r!"

This formula is symmetrical:

In other words choosing 3 balls out of 16, or choosing 13 balls out of 16 have the same number of combinations.

Combinations with Repetition

From http://kruel.co/2012/05/06/number-of-combinations-with-repetition/#sthash.8TnqDEyX.dpbs
There are n = 4 sorts of candy to choose from and you want to buy k = 10 candies. How many ways can you do it?

Note that there are 10 symbols ‘C’ and 3 partition walls, represented by a ‘+’ sign. That is, there are n-1+k = 13, equivalently n+k-1, symbols. Further note that each of the 3 partition walls could be in 1 of 13 positions. In other words, to represent various choices of 10 candies from 4 categories, the positions of the partition walls could be rearranged by choosing n-1 = 3 of n+k-1 = 13 positions

C++CCC+CCCCCC

CCCCCCCCCC+++

We have now translated the original problem into choosing 3 of 13 available positions.

(n+k-1)!/k!(n-1)!

where n is the number of things to choose from, and we choose r of them
(Repetition allowed, order doesn't matter)

Interestingly, we could have looked at the arrows instead of the circles, and we would have then been saying "we have r + (n-1) positions and want to choose (n-1) of them to have arrows", and the answer would be the same ...