The binomial coefficient computes the number of ways to pick $k$ elements from a set of $n$ elements, not to be
confused with the Stirling Number of the Second Kind. So for example, if we have a set $\{a,b,c,d\}$ we can pick
two elements in the following ways.
$\{a,b\},\{a,c\},\{a,d\},\{b,c\},\{b,d\},\{c,d\},$ which is 6 ways. So the binomial coefficient, shown as
$$\binom{4}{2}=6.$$
The usual formula presentation is easy to remember, but suffers from numerical overflow if we try to compute with
it, since factorials get big quick.
$$\binom{n}{k}=\frac{n!}{k!(n-k)!}$$
We do observe that the same number of factors exist in both the numerator and denominator.
$$\begin{array}{ccccc}
\binom{7}{-1}= & \frac{7!}{-1!(7+1)!}= & err\\
\binom{7}{0}= & \frac{7!}{0!(7-0)!}= &
\frac{7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1}{1(7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1)}= & \frac{1}{1}= & 1\\
\binom{7}{1}= & \frac{7!}{1!(7-1)!}= &
\frac{7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1}{1\cdot(6\cdot5\cdot4\cdot3\cdot2\cdot1)}= & \frac{7}{1}= & 7\\
\binom{7}{2}= & \frac{7!}{2!(7-2)!}= &
\frac{7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1}{2\cdot1\cdot(5\cdot4\cdot3\cdot2\cdot1)}= & \frac{6\cdot7}{1\cdot2}=
& 21\\
\binom{7}{3}= & \frac{7!}{3!(7-3)!}= &
\frac{7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1}{3\cdot2\cdot1\cdot(4\cdot3\cdot2\cdot1)}= &
\frac{5\cdot6\cdot7}{1\cdot2\cdot3}= & 35\\
\binom{7}{4}= & \frac{7!}{4!(7-4)!}= &
\frac{7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1}{4\cdot3\cdot2\cdot1\cdot(3\cdot2\cdot1)}= &
\frac{5\cdot6\cdot7}{1\cdot2\cdot3}= & 35\\
\binom{7}{5}= & \frac{7!}{5!(7-5)!}= &
\frac{7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1}{5\cdot4\cdot3\cdot2\cdot1\cdot(2\cdot1)}= & \frac{6\cdot7}{1\cdot2}=
& 21\\
\binom{7}{6}= & \frac{7!}{6!(7-6)!}= &
\frac{7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1}{6\cdot5\cdot4\cdot3\cdot2\cdot1\cdot(1)}= & \frac{7}{1}= & 7\\
\binom{7}{7}= & \frac{7!}{7!(7-7)!}= &
\frac{7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1}{7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1\cdot(1)}= & \frac{1}{1}= & 1\\
\binom{7}{8}= & \frac{7!}{8!(7-8)!}= & err
\end{array}$$
We can also observe that the calculation is symmetric. If $k>n-k$ then $k=n-k$ will give the same answer. We
might
want to check the symmetry observation with a case where $n$ is an even number, but we can do a much smaller
example.
So again, if $k>n-k$ then $k=n-k$ gives the same answer.
Instead of computing factorials, we can accumulate a multiple. The code below is a program for the next to last
column in [eq:nCr]. By having the division included in each step, large numbers can be avoided for a long time.
let result = 1
for(let i=1; i<=k; ++i){result = result*(n-k+i)/i;}
Stirling Numbers of the 2nd Kind
Number of ways to pick $k$ pairwise distinct subsets from an $n$ element set. This wording can be confusing, so read
carefully. If we have exactly four elements, $\{a,b,c,d\},$ how many ways exist to make one subset and use all four
elements? Pretty clear, there is only one way. $$\{a,b,c,d\}$$
With the four elements, $\{a,b,c,d\},$ how many ways exist to make two subsets? Here are all of the ways to make two
pairwise distinct subsets. The first four are called 1+3 splits and the last three are called 2+2 splits. We have
shown seven, because there are seven ways to arrange four elements into two subsets.
$$\begin{array}{c}
\{a\}\{b,c,d\}\\
\{b\}\{a,c,d\}\\
\{c\}\{a,b,d\}\\
\{d\}\{a,b,c\}\\
\{a,b\}\{c,d\}\\
\{a,c\}\{b,d\}\\
\{a,d\}\{b,c\}
\end{array}$$
We can also make 1+1+2 splits. Here we are considering the split of our four elements into three subsets.
$$\begin{array}{c}
\{a\}\{b\}\{c,d\}\\
\{a\}\{c\}\{b,d\}\\
\{a\}\{d\}\{b,c\}\\
\{b\}\{c\}\{a,d\}\\
\{b\}\{d\}\{a,c\}\\
\{c\}\{d\}\{a,b\}
\end{array}$$
Finally, we could consider 1+1+1+1 splits and with only 4 elements, we will get exactly 1 way to split them into
four
subsets. $$\{a\}\{b\}\{c\}\{d\}$$
The numbers that we have generated as "number of ways to make $k-element$ subsets” are $[1,7,6,1]$ and they are
known
as Stirling numbers of the second kind.
Triangle computation of Stirling numbers type 2.
There is a recurrence relation to generate the Stirling numbers. Mathematically it is
$$\left\{ \begin{array}{c}
n\\
k
\end{array}\right\} =k\left\{ \begin{array}{c}
n-1\\
k
\end{array}\right\} +\left\{ \begin{array}{c}
n-1\\
k-1
\end{array}\right\} \text{initial conditions}\left\{ \begin{array}{c}
0\\ 0 \end{array} \right\} =1 $$
The following triangle is generated.
$$ \begin{array}{c|ccccccc}
n/k & 0 & 1 & 2 & 3 & 4 & 5 & 6\\
\hline 0 & 1\\
1 & & 1\\
2 & & 1 & 1\\
3 & & 1 & 3 & 1\\
4 & & 1 & 7 & 6 & 1\\
5 & & 1 & 15 & 25 & 10 & 1\\
6 & & 1 & 31 & 90 & 65 & 15 & 1
\end{array}$$
The value $1$ located at $n=0$ $k=0$ is given as an initial condition. Every number thereafter can be found by
multiplying $k$ (the column header) times the number directly above the desired value plus the number above and to the
left of the desired value. So for instance to generate the value
$$\left\{ \begin{array}{c}
5\\
3
\end{array}\right\} =25,$$
just compute $3\times(6)+7.$ With a little practice, one can generate the triangle fairly quickly.
Bell Number Computation
A partition of a set is the placement of all elements into non-empty subsets. Each element must be in one and only one
subset. The Bell numbers represent a count of all possible partitions of a set of distinguishable elements, into
non-empty subsets and the intersection of any pair of subsets must be null.
$\textbf{Definition:}$ Bell Number. A count of all pairwise distinct subsets that can be made from a set of
distinguishalbe elements.
For example, consider a set of 4 elements, {a,b,c,d}. Here are the possible ways to make subsets. As usual, order
within a set does not matter. The empty set is not counted and no sets that might be empty are allowed.
$$\begin{array}{c}
\{a,b,c,d\}\\
\{a\}\{b,c,d\}\\
\{b\}\{a,c,d\}\\
\{c\}\{a,b,d\}\\
\{d\}\{a,b,c\}\\
\{a,b\}\{c,d\}\\
\{a,c\}\{b,d\}\\
\{a,d\}\{b,c\}\\
\{a\}\{b\}\{c,d\}\\
\{a\}\{c\}\{b,d\}\\
\{a\}\{d\}\{b,c\}\\
\{b\}\{c\}\{a,d\}\\
\{b\}\{d\}\{a,c\}\\
\{c\}\{d\}\{a,b\}\\
\{a\}\{b\}\{c\}\{d\}
\end{array}$$
Bell number by Stirling sum
Notice how these are very similar to the Stirling numbers of the second kind. Indeed, the Bell number for a set of $n$
items is the sum of all possible Stirling number sets fashioned from those items.$$B_{n}=\sum_{i=1}^{k}\left\{
\begin{array}{c}
n\\
k
\end{array}\right\} $$
Bell number by Triangle Recurrsion
There is a nice triangle expansion for generating these numbers.
$A_{1,1}=1\ (A_{0}=1,$ but is omitted from the triangle scheme.)
The first entry in each row is the last entry in the previous row.
Other entries are $A_{n,k}=A_{n,k-1}+A_{n-1,k-1}$ In the triangle, the cell to the left and the cell above that.
There is yet a third way to generate these numbers.$$B_{n+1}=\sum_{k=0}^{n}\binom{n}{k}B_{k}$$
This uses the binomial coefficient multiplied times the $k^{th}$ Bell number with all summed. Given all three methods,
I am inclined to think that the triangle method might be the fastest since it involves little more than repeated
addition.