permutations and combinations

permutations

a set of arrangements constructed from a set of elements where the order of the elements is relevant e.x. inputs for a numeric lock

combinations

a set of selections constructed from a set of elements where the order of the elements is irrelevant

r-permutations

an ordered arrangement of r elements from a set of n objects is called an r-permutation when repetitions are not allowed: 0 <= r <= n

r-combinations

an unordered selection of r elements from a set of n objects is called an r-combination when repetitions are not allowed: 0 <= r <= n

coin flip example for permutations and combinations

the set of outcomes for a single coin flip is {H, T}, suppose we flip it twice: the set of outcome permutations is {HH, HT, TH, TT} the set of outcome combinations is {HH, HT, TT} (the ordering of H and T is arbitrary, HT and TH are interchangeable)

number of r-permutations without repetition

P(n, r) = n!/(n-r)!

number of r-combinations without repetition

C(n, r) = nCr = n!/r!(n-r)!, n >= r

symmetry of r-combinations

choosing r from n has the same number of combinations as choosing (n-r) from n e.x. choosing 7 distinct digits from 10 has the same number of combinations as choosing 3 distinct digits from 10, you can think of it as choosing the 3 digits not to include

number of r-permutations with repetition

n^r

number of r-combinations with repetition methodology

imagine arranging the set of n numbers to choose from in any order, and arranging a pointer to point to the first number then imagine creating a binary string where 1 means to select the current pointed-to number, and 0 means to move the pointer to the next number, there will be r 1s and (n-r) 0s the binary string will have (n-1) 0s and r 1s the number of combinations is equal to the number of unique binary strings, which is the combinations of choosing n from r with repetitions is equal to the combinations of choosing r from r + n - 1 with no repetitions

number of r-combinations with repetition

(r+n-1)Cr = (r+n-1)!/r!(n-1)!