Kernel: Python 3

Introduction

Review of the binomial coefficient

Suppose nn and kk are positive integers with n≥kn≥k. Then C(n,k)C(n,k) is the number of ways to select kk items from a group of nn items without caring about the order in which we select them. The number C(n,k)C(n,k) is an integer called the binomial coefficient and is computed using the formula:

C(n,k)= $\frac{n!}{n−k!k!}$

Example: Suppose four students are working in a group on a homework problem and we want to select two of them to go to the board to present it, and we don't care which two, or the order in which the two are selected. The number of ways this can be done is

C(4,2)= $\frac{4!}{(4−2)!2!}$ = $\frac{24}{2×2}$ =6

Let's check that this is right: If the students are Alice, Bob, Chuck, and Dave (which we will abbreviate A, B, C, D) then here are the groups of 2 we can select:

Since we don't care about the order in which they are selected, the choice "Alice, Bob" is the same as the choice "Bob, Alice". Therefore we can see that we have 6 possible selections.

Python code for the binomial coefficient

The binomial coefficient is not a built-in function in Python, so let's write a Python function that computes it. We will need the factorial function from the math module for this.

In [2]:

from math import factorial

def binom(n,k):
    return int(factorial(n)/(factorial(n-k) * factorial(k)))

We use int above to force the output to be an integer. Otherwise the division operation produces a decimal.

Now let's test it out using the example above:

In [3]:

# Number of ways to select 2 items from a group of 4 without respect to order
binom(4,2)

Out[3]:

6

Another example

A game show on TV has an audience of 100 people, and 5 people are selected at random to come down front to be contestants. How many possible ways are there to make this selection?

Solution: There's nothing here to suggest that ordering matters, so the answer is C(100,5):

binom(100,5)

In [4]:

binom(100,5)

Out[4]:

75287520