Preview Activity

Skip to main content

\(\usepackage{cancel} \def\d{\displaystyle} \def\N{\mathbb N} \def\B{\mathbf B} \def\Z{\mathbb Z} \def\Q{\mathbb Q} \def\R{\mathbb R} \def\C{\mathbb C} \def\U{\mathcal U} \def\x{\mathbf{x}} \def\y{\mathbf{y}} \def\X{\mathcal{X}} \def\Y{\mathcal{Y}} \def\pow{\mathcal P} \def\inv{^{-1}} \def\st{:} \def\iff{\leftrightarrow} \def\Iff{\Leftrightarrow} \def\imp{\rightarrow} \def\Imp{\Rightarrow} \def\isom{\cong} \def\bar{\overline} \def\card#1{\left| #1 \right|} \def\twoline#1#2{\begin{pmatrix}#1 \\ #2 \end{pmatrix}} \def\mchoose#1#2{ \left.\mathchoice {\left(\kern-0.48em\binom{#1}{#2}\kern-0.48em\right)} {\big(\kern-0.30em\binom{\smash{#1}}{\smash{#2}}\kern-0.30em\big)} {\left(\kern-0.30em\binom{\smash{#1}}{\smash{#2}}\kern-0.30em\right)} {\left(\kern-0.30em\binom{\smash{#1}}{\smash{#2}}\kern-0.30em\right)} \right.} \def\o{\circ} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \definecolor{fillinmathshade}{gray}{0.9} \newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}} \)

Print preview

Highlight workspace

Worksheet Preview Activity

It is often possible to find the answer to a counting question in two different ways. Doing so results in two formulas that give the answer, which might look different, but must be equal (since they are both the correct answer to the same question). This provides a proof of the equality of the two formulas, called a combinatorial proof.

Let’s explore a couple of examples.

1.

Consider the set of 7-bit strings of weight 3. That is, strings of 0s and 1s that are seven characters long and have exactly three 1s. How many such strings are there?

(a)

Give the answer as a single binomial coefficient.

(b)

Now count just those 7-bit strings of weight 3 that start with a 1. How many are there?

(c)

Now count just those 7-bit strings of weight 3 that start with 01. How many are there?

(d)

Now count just those 7-bit strings of weight 3 that start with 001. How many are there?

(e)

Continue this process until you have counted all 7-bit strings of weight 3, as a sum of binomial coefficients. What is this sum?

2.

Consider the counting question “How many ways can you permute the letters of the word STATISTICS?” Note that this is not just a permutation, since there are repeated letters.

(a)

How many ways can you select three of the ten positions in the anagram to be occupied by the letter S?

(b)

How many ways can you select three of the remaining seven positions in the anagram to be occupied by the letter T?

(c)

Continue with this approach until you have found an expression for the number of ways to permute the letters of STATISTICS as a product of binomial coefficients. Write out this product.

(d)

Now answer the counting question again, this time starting by asking how many ways you can select positions for the letter A first. Continue in any way you like until you have found a different expression for the number of ways to permute the letters of STATISTICS as a product of binomial coefficients. Write out this product.

(e)

Try yet another approach. What is wrong with saying the answer is \(10!\text{?}\) This is too large, but we can correct it by dividing to account for outcomes that are equivalent. What should you divide by?

Write your answer as a quotient of factorials. Do you get the same answer as before?