Binomial and multinomial coefficients

The binomial coefficient \(\binom n k\) represents the number of different ways to choose a subset of size \(k\) out of a set of size \(n\), and is in general given by the formula

\(\displaystyle \binom n k = \frac{n!}{k!(n-k)!}\)

However, binomial coefficients can be computed more efficiently than literally using the above formula with factorial, so Disco has special built-in support for computing them. Since \(\binom n k\) is usually pronounced “\(n\) choose \(k\)”, the Disco syntax is n choose k. For example:

Disco> 5 choose 2
10
Disco> 7 choose 0
1
Disco> 0 choose 0
1
Disco> 7 choose 8
0
Disco> 100 choose 23
24865270306254660391200

Multinomial coefficients

Disco also has support for multinomial coefficients:

\(\displaystyle \binom{n}{k_1 \quad k_2 \quad \dots \quad k_r} = \frac{n!}{k_1! k_2! \dots k_r! (n - k_1 - k_2 - \dots - k_r)!}\)

is the number of ways to simultaneously choose subsets of size \(k_1, k_2, \dots, k_r\) out of a set of size \(n\). In Disco, a multinomial coefficient results when the second argument to choose is a list instead of a natural number. For example:

Disco> 10 choose 2
45
Disco> 10 choose [2]
45
Disco> 10 choose [2,3]
2520
Disco> 10 choose [2,3,5]
2520
Disco> 10 choose [2,3,5] == (10 choose 2) * (8 choose 3) * (5 choose 5)
true