Videos (~25 mins)

Reading (~40 mins)

Warmup (~40 mins)

Problem 1

Consider the four letters \(a,b,c,d\).

Part A

Write down 6 permutations of these letters. How many total permutations are there?

Part B

Write down 4 \(3\)-permutations of these letters. How many total \(3\)-permutations are there?

Part C

Pick one combination of 3 letters from \(abcd\), and write down all permutations of this combination.

How many combinations of 3 letters are there from \(abcd\)?

Problem 2

In the video “How many ways are there to reorder the word MISSISSIPPI?” by Dr. Trefor Bazett, Dr. Bazett computes the number of reorderings as follows. First he considers the number of places to put all the “S”s, then all the “I”s, then the two “Ps”, and finally the “M”. The resulting expression is

\[ \begin{aligned} \binom{11}{4} \binom{7}{4} \binom{4}{2} \binom{1}{1}\;. \end{aligned} \tag{1}\]

Part A

Find the mistake in Dr. Bazett’s solution. Describe what the error is and write down the correct solution!

Yes, math profs make mistakes too…

Part B

Perform the same analysis as Dr. Bazett, but start by placing the “M”, then the two “P”s, then the four “I”s, and then the four “S”s. You should get an expression that is similar to your corrected answer in Part A, including some of the same numbers, but in different places.

Part C

Using the formula for \(\binom{n}{k}\), write a calculation to show that your answer in Part B agrees with (is the same number as) Dr. Bazett’s solution in Equation 1 (after your correction from Part A).

Part D

The method of combinatorial proof is used to show that two expressions are equal by demonstrating that they are different ways of counting the same thing. Use a combinatorial proof to show that, for any integers \(n\), \(k\), and \(j\) such that \(k + j \leq n\),

\[ \begin{aligned} \binom{n}{k}\binom{n-k}{j} = \binom{n}{j}\binom{n-j}{k}\;. \end{aligned} \]

Note: it is possible to do this with algebra, but please don’t! The combinatorial proof is simpler and nicer.

Hint: consider the number of ways to reorder a word of length \(n\) containing only three kinds of distinct letters.