Section2Basic Combinatorial Numbers
Subsection2.1Binomial Coefficients
The number of \(3\)-sets chosen from a \(10\)-set, \({10 \choose 3}\text{.}\)
The coefficients of an expansion of \((a+b)^n\text{.}\)
All of the coefficients.
A Python dictionary, indexed by powers of the two variables in the expansion.
Tote up all of these binomial coefficients, to get \(2^{10}\text{.}\) (Size of the power set, or the result of setting \(a=1\) and \(b=1\)).
Actual subsets of size 3 from a \(10\)-set; one way to understand a binomial coefficient.
sub is a “generator”. We can list the possibilities.
We can iterate over sub.
Subsection2.2Catalan Numbers
\(C_n = \frac{1}{n+1}{2n \choose n} = \frac{(2n)!}{(n+1)!\,n!}\)
Subsection2.3Bell Numbers
In honor of Eric Temple Bell.
Number of partitions of a set into disjoint non-empty sets.
That's hard to read.
A double-check.
Subsection2.4Stirling Numbers
Stirling numbers come in two flavors, “first” and “second”, or “cycle” and “subset”. We'll demonstrate the first.
The number of permutations on \(n\) symbols (in cycle notation) having exactly \(k\) cycles, \(\left\{n\atop k\right\}\text{.}\)
In cycle notation.
Now we get the trivial cycles. List length is what we want.
Collect all permutations with 3 cycles.
How many?