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.    #(unordered) samples without replacement.
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).    #(unordered) samples with replacement.
nHk = n+k-1Ck = (n+k-1)! / (n-1)!k!

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 (i.e. is a subset) is
   N!/(N-n)!Nn = N·(N-1)·...·(N-n+1) / Nn = Product(k=1 to n-1)(1-k/N)

Probability that a sample with replacement is a subset (i.e no dups)
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

Partitions

Number of ways a set of size n can be partitioned/grouped into k subsets. (all the elements in one of the k subsets)
= Stirling numbers of the second kind: S(n,k)

Ex. set {a,b,c} n=3.
Partitions of k=1: {a,b,c}.    S(3,1)=1
Partitions of k=2: {a,b}{c}, {a,c}{b}, {b,c}{a}.    S(3,2)=3
Partitions of k=3: {a}{b}{c}.    S(3,3)=1

Ex. set {a,b,c,d} n=4.
Partitions of k=1: {a,b,c,d}.    S(4,1)=1
Partitions of k=2: {a,b}{c,d}, {a,c}{b,d}, {a,d}{b,c}, {a,b,c}{d}, {a,b,d}{c}, {a,c,d}{b}, {b,c,d}{a}.    S(4,2)=7
Partitions of k=3: {a,b}{c}{d}, {a,c}{b}{d}, {a,d}{b}{c}, {b,c}{a}{d}, {b,d}{a}{c}, {c,d}{a}{b}.    S(4,3)=6
Partitions of k=4: {a}{b}{c}{d}.    S(4,4)=1

S(n,1)=1 S(n,n)=1

S(n,k) = easy for software...No simple formula for us.

n:    k:     

Total number of partitions of a set of size n is sum from k=1 to n of S(n,k) = Bn (Nth Bell number).

Ex. set of size n=4: B4 = S(4,1)+S(4,2)+S(4,3)+S(4,4) = 1+7+6+1 = 15

n 1 2 3 4 5 6 7 8 9 10 ...
Bn 1 2 5 15 52 203 887 4140 21147 115975
n:     

Bell's triangle.
Copy end of row to start of next row.
Row entries are sum of entry to left plus entry left and above (Mij←Mij-1+Mi-1j-1.
Rightmost entry is Bn.

1