Permutations

sequences, orders, sorts, shuffles, arrangements, anagrams, rankings of n different things k at a time = #ways without replacement.
Learn: by hand, do the permutations of 3 things 1, 2, and 3 at a time. Then do the permutations 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
MASSACHUSETTS =

Derangements all things "move", a complete rearrangement: !n = ⌊n!/e + 1/2⌋
Probability of a permutation being a derangement is 1/e (in the limit as n→∞) ≈ 0.367879441
≈ 36.78% of permutations are derangements

Show a permutation. Type or paste the elements/symbols/"things":


n=

Combinations

subsets.    committees, subgroups, samples
nCk = the number of subsets of size k from a set of size n.
Learn: by hand, do the subsets of 4 things 0, 1, 2, 3, and 4 at a time. Then 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

#combinations is the #permutations divided by k!: nCk = nPk/k!
#permutations is the #combinations multiplied by k!: nPk = nCk·k!

Combinations with replacement (i.e. repetition allowed).
nHk = n+k-1Ck

Pascal's triangle:

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

Binomial theorem:

Statistics
Population size N, sample size n

#(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 (62 quintillion)

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