Permutations, Combinations, and Combinatorial Proof

Videos

Readings

Warmup

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

Give a combinatorial proof of the following identity: for all \(n \in \mathbb{Z}\), \(0 \leq k \leq n\), 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 proof algebraically as well, but if you do it that way then you’re missing the point!

Problem 3

Suppose that we want to form a committee of \(k\geq 2\) people from a set of \(n \geq k\) people.

Part A

Aisha and Hinal are fast friends. Each of them will only join the committee if the other is also on it. How many ways are there to form the committee that either includes both Aisha and Hinal, or neither of them?