L2 C4 S3

S3: The N choose K formula

FIRST question: How many sequences of 0's and 1's have exactly K 1's and N-K 0's?

To answer this question, we look at the problem in a slightly different way. We put NUMBERS on the positions of the binary sequence like this:

We can think of a sequence as a collection of CHOICES from the position numbers 1,2,...,N A 0 means that the corresponding position is NOT chosen, and a 1 means that the position number has been chosen. In the example above, the sequence shown chooses 2,N and does not choose 1,3. This way, a sequence of 0's and 1's with K 1's and N-K 0's corresponds to a choice of K numbers from among the total of N numbers. How many ways can we choose K elements from a set with N elements? This is a famous question with a well known answer, given by the N choose K formula:

This formula provides us with the answer to the FIRST question -- this is the NUMBER of sequences of 0's and 1's which has exactly K 1's and N-K 0's. This allows us to answer the second question

SECOND Question: Given a Bernoulli sequence of length N, what is the chance that it has exactly K 1's and exactly N-K 0's?

By using the multiplication rule, each sequence with K 1's and N-K 0's has probability p^K (1-p)^N-K This means that the desired probability, which is the answer to the second question, is:

These formulae are very important in the development of probability theory. We will show many real world applications of them later.

Khan Academy Lesson on N choose K — 4+ minutes You Tube video

N Choose K formula explained — You Tube Video in 5 minutes