Permutations

sequences, orders, sorts, shuffles, arrangements, anagrams, rankings of n different things k at a time = #ways without replacement.
Learn: do the permuatations of 4 things 1, 2, 3, and 4 at a time.

  = n·(n-1)·...·(n-k+1)      When k=n, nPk = n!

n:      k:        nPk=


nPn, # permutations of all n of the things is n!
nPn-1 # permutations of n things taken n-1 at a time is also n!
nP1, # permutations of n things taken 1 at a time is n
nP2, # permutations of n things taken 2 at a time (ie. ordered pairs) is n(n-1) = #edges in fully-connected digraph

A multiset (elements can be repeated) # of permutations = n! / m1!m2!...mi!
MISSISSIPPI = 11! / 1! 4! 4! 2! = 34650

Derangements all things "move": !n = ⌊n!/e + 1/2⌋

Combinations

subsets.    committees, subgroups, samples
nCk = the number of subsets of size k from a set of size n.
Learn: do the subsets of 4 things 0, 1, 2, 3, and 4 at a time.
Do the subsets of 5 things 0, 1, 2, 3, 4, and 5 at a time.

=             n "choose" k     the binomial coefficients, Pascal's triangle

n:      k:        nCk=


nC0 =1, the empty set
nC1 =n, the singleton sets
nCn =1, the set itself
nCn-1 =n, each set minus one member
nC2 =(n(n-1))/2 =(n2-n)/2 = #unordered pairs = #edges in fully-connected graph Kn
nCk = nCn-k, symmetry

Pascal's triangle:

nCk = n-1Ck-1 + n-1Ck

Binomial theorem:

#(unordered) samples without replacement = #subsets = #combinations = C(N,n) = N! / (N-n)!n!
N=100, n=10     C(100,10)≈17.3T

#(unordered) samples with replacement = #combinations with replacement = C(N+n-1,n) = C(N+n-1,N-1)
N=100, n=10     C(109,10)=C(109,99)≈42.6T

#ordered samples without replacement = #permutations = P(N,n) = N! / (N-n)! = C(N,n)·n!
N=100, n=10     P(100,10)≈62E (quintillion)

#ordered samples (permutations with replacement) = Nn
N=100, n=10     P(100,10)=100E (quintillion)