Mach 9.1 Basic Combinatorics

199 days ago by mpaul

Multiplication Counting Principle

If event_1 can occur in x_1 ways, event_2 in x_2 ways, event_3 in x_3 ways, ... , and event_n in x_n ways, then all the events can occur together in x_1\cdot x_2\cdot x_3\cdot ... \cdot x_n ways.
def count(*ways): return prod(ways) 
       
count(1,2,3,4) 
       
count(6,7,2) 
       
count(5,4,3,2) 
       

n!

There are n! permutations (arrangements) of n distinct objects. 

Why?  Because there are n ways to arrange the first object, n-1 ways to arrange the second, etc.
def fact(n): return prod([1..n]) 
       
fact(10) 
       

factorial is in Sage:
for n in range(10): (n,factorial(n)) 
       
n = 4 permutations(n) 
       
len(permutations(n)) 
       
factorial(n) 
       

Distinguishable Permutations

There are \frac{n!}{n_1!n_2!n_3!...n_k!} distinguishable permutations of n objects with frequencies n_1+n_2+n_3+...+n_k = n.
def distinguishable(n, *freq): return factorial(n)/prod([factorial(d) for d in freq]) 
       
distinguishable(3,3) 
       
list(permutations(var('a b b'))) 
       
len(_) 
       
factorial(7) 
       
list(permutations(var('a a a a a a'))) 
       
len(_) 
       

_{n}P_{r}

There are \frac{n!}{(n-r)!} distinguishable permutations of r objects taken from a set of n objects.

We represent this as _{n}P_{r}.
def P(n,r): return distinguishable(n,n-r) 
       
P(10,2) 
       
def P(n,r): return prod([n,n-1..1][:r]) 
       
P(10,4) 
       

_nC_r

There are _nC_r combinations of r objects taken from a set of n objects.

The number of permutations of these groups is _nC_r \cdot r!  This is equivalent to _nP_r.

Therefore, _nC_r  = \frac{_nP_r}{r!} = \frac{n!}{(n-r)! \cdot r!}.

_nC_r is also known as a binomial coefficient and is often expressed as \binom {n} {r}.
def C(n,r): return P(n,r)/factorial(r) 
       
C(10,3) 
       

The function binomial() is in Sage:
binomial(10,3) 
       
var('a b') show(binomial(a,b)) 
       
list(Combinations(var('b a n a n a'),3)) 
       
len(_) 
       
list(Permutations(var('b a n a n a'),3)) 
       
len(_) 
       

There are 2^n possible subsets of a set containing n objects.
n = 5 list(Combinations(n)) 
       
len(_) 
       
2^n 
       

\sum_{r=0}^{n}  _{n} C _{r} = 2^{n}
C = binomial n = 7 [C(n,r) for r in [0..n]] 
       
sum(_) 
       
n = 100 for r in range(n+1): factorial(n)/factorial(r)/factorial(n-r) 
       
Permutations(var('L O G A R I T H M')).cardinality() 
       
Permutations(var('C H A T T A N O O G A')).cardinality() 
       
Permutations(12,6).cardinality()