Factorials and binomial coefficients

Algorithm 13.A: Permutations

Input: the number $n$ of unique objects that could be chosen, and the number $k$ of objects that will be chosen.
Output: a non-negative integer.

Describe an algorithm for calculating the number of ways in which $k$ objects can be lined up (permuted) from $n$ unique objects.

Note that this algorithm does not ask for a list of all permutations, but rather, it simply asks for how many of such permutations exist.

Your computer (the person performing this algorithm) cannot follow general instructions. Instead, your computer can only write numbers on a piece of paper and change numbers on that piece of paper based on numbers that are already written on that piece of paper. You cannot just say "Multiply together all integers from $n$ down to $n - k$." You can, however, have to boxes labelled n and k and a box called result and then initialize these boxes with specific values.

Algorithm 13.B: Factorial

Input: the number $n$ of unique objects to be permuted.
Output: a non-negative integer.

Describe an algorithm that calculates $n!$ for any non-negative integer value of $n$. This is also the number of ways in which either $n$ or $n - 1$ objects can be lined up (permuted) from $n$ unique objects.

For this algorithm, you can instruct the user to use Algorithm 13.A with specific values of $n$ and $k$.

Note that in any circumstance where $n!$ appears, there is invariably a process somewhere there $n$ objects had to be rearranged in $n!$ ways.

Demonstrate your understanding:
Why are there just as many ways of lining up (permuting) $n$ unique objects as there are lining up (permuting) $n - 1$ objects taken from $n$ unique objects?

Algorithm 13.C: n choose k

Input: the number $n$ of unique objects that could be chosen, and the number $k$ of objects that will be chosen.
Output: a non-negative integer.

Describe an algorithm for calculating the number of ways of choosing $k$ objects from $n$ unique objects. Your algorithm should use the factorial. These are also the binomial coefficients ${n \choose k}$. Your algorithm should involve the least number of integer multiplications or divisions possible.

For this algorithm, an expensive means of calculating this would be to calculate three different versions of Algorithm 13.B and then calculate a ratio of these results. Instead, an efficient algorithm will instruct the user to perform calculations of Algorithm 13.A and one of Algorithm 13.B and then calculate a ratio of these.

Test your algorithm by ensuring that it should be relatively easy for your computer to calculate both $1000 \choose 2$ and $1000 \choose 998$.

Algorithm 13.D: Approximating e

Input: a non-negative integer $n$.
Output: a rational number.

Describe an algorithm that efficiently calculates the sum

$\sum_{k = 0}^\infty \frac{1}{k!} = \frac{1}{0!} + \frac{1}{1!} + \frac{1}{2!} + \cdots + \frac{1}{n!}$

Your algorithm should require no more than $n$ inversions, $n - 1$ multiplications and $n - 1$ additions.

Algorithm 13.E(a): Binomial coefficients

Input: a non-negative integer $n$ and two non-negative integers $k_1$ and $k_2$ such that $k_1 + k_2 = n$.
Output: a non-negative integer.

Describe an algorithm for calculating the number of ways of dividing $n$ unique objects into two separate groups of $k_1$ and $k_2$ objects where $k_1 + k_2 = n$.

Demonstrate your understanding:
Why are the formulas for choosing $k$ objects out of $n$ the same as the formula for dividing $n$ unique objects into two groups of $k$ and $n - k$ objects?

Algorithm 13.E(b): Trinomial coefficients

Input: a non-negative integer $n$ and three non-negative integers $k_1$, $k_2$ and $k_3$ such that $k_1 + k_2 + k_3 = n$.
Output: a non-negative integer.

Describe an algorithm for calculating the number of ways of dividing $n$ unique objects into three separate groups of $k_1$, $k_2$ and $k_3$ objects where $k_1 + k_2 + k_3 = n$.

Again, your algorithm should require only three calls to Algorithm 13.A or Algorithm 13.B.

Algorithm 13.E(c): Multinomial coefficients

Input: a non-negative integer $n$ and $m$ non-negative integers $k_1, k_2, \ldots, k_m$ such that $k_1 + k_2 + \cdots k_m = n$.
Output: a non-negative integer.

Describe an algorithm for calculating the number of ways of dividing $n$ unique objects into $m$ separate groups of $k_1$, $k_2$, ..., $k_m$ objects where $k_1 + k_2 \cdots k_m = n$.

Again, your algorithm should require only $m$ calls to Algorithm 13.A or Algorithm 13.B.

Demonstrate your understanding:
The game of Bridge is played with fifty-two cards with four players. Each player is dealt one-quarter of the deck or thirteen cards. How many different ways are there of distributing those fifty-two cards between the four players?
The game of Euchre is played with twenty-four cards with four players. Each player is dealt five cards, with the remaining four cards forming the kitty. How many different ways are there of distributing those twenty-four cards between the four players?