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=


         
Letter (n≤26)    Number

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
Probability that a sample selected with replacement of size n from a population of size N has no duplicates is N!/(N-n)!Nn = N·(N-1)·...·(N-n+1) / Nn = Product(k=1 to n-1)(1-k/N)

N n: 10 30 100
1000 P(no dups) 0.955861 0.644461 0.005959
10000 P(no dups) 0.995509 0.957392 0.608566
100,000 P(no dups) 0.999550 0.995659 0.951690
1,000,000 P(no dups) 0.999955 0.999565 0.995062

Probability the sample has duplicates is 1-P(no dups).

#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) 

An element of an n-set is in half (2n-1) of all (2n) subsets.
So the probability that it is in a randomly chosen subset is ½.

So the probability that it is in two randomly chosen subsets is 1/4.
and the probability that it is in neither of the two subsets is 3/4.
Same for each of the n elements, thus the probability that two subsets
are disjoint is (3/4)n.


Probability that two k-sized subsets are disjoint is 
n-kCk / nCk