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.
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?
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$.
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.
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?
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.
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?