Notes on binomial coefficients
Commonly know first few and recurrence (& closed form);
a lot more can be said.
. generating function
(1+a)^n is a generating function for nCk
(can make a 2 var gen func: 1/(1-b(1+a)))
yields: same even as odd (1-1)^n, total num subsets (1+1)^n
. recurrence
. closed form (via perm and stabilize)
. total number of subsets: 2^n, binary strings
. converges to normal (CLT for Bernoulli)
. same number of even as odd subsets
(surprisingly interesting!)
easy if n is odd, b/c can just swap
(note: odd/even different)
for even subtle b/c no natural correspondence between even and odd!
can plug in a=-1, getting (1-1)^n = 0
can fix an element: then including/not
(subtle: issue of naturality: natural for pointed sets)
probability: even/odd is random
algebraic: group homo: (Z/2)^n -> Z/2