MAT344
▶ Permutations/Combinations
▶ Intro to Combinatorial Proofs (time permitted)
Permutations
Definition
Let X be a collection of n distinct objects. A permutation of X is
an X -string s where no element is repeated (equivalently, s is
injective when viewed as a function).
▶ For example, a,b,c,ab,ba, and abc are all permutations of
{a, b, c}, but aba is not.
Definition
Given integers n and k with n ≥ k , we let P(n, k) denote the
number of permutations of [n] of length k .
Counting Permutations
Definition
Given an integer n, we let n! denote the integer
n × (n − 1)× ...× 2× 1. We call this value n factorial.
Theorem
Given integers n and k with n ≥ k , P(n, k) = n!(n−k)!
Proof.
▶ For a permutation of [n] of length k , we have n many choices
for s(0), n − 1 remaining choices for s(1),..., n − (k − 1)
remaining choices for s(k − 1). Hence,
P(n, k) = n × ...× (n − (k − 1)) = n!(n−k)!
▶ This isn’t a strong proof, we can strengthen our argument
when we discuss combinatorial proofs.
Some Counting Questions
▶ How many odd numbers are there with 2n many digits in its
decimal expansion?
▶ How many binary strings of length n ≥ 3 end in 01?
▶ How many binary strings of length n ≥ 3 don’t end in 01?
▶ An alien species comes to the UN with intentions of brokering
a peace deal with earth. The aliens use a lexicon of 64 distinct
symbols. No word in the alien language uses more than 6
symbols. What is the maximum number of words in the alien
dictionary?
▶ Suppose ϕ and ψ are two symbols in the alien lexicon. An
analyst at the UN noticed that ϕ is always followed by a ψ,
and a ϕ never appears more than once in a word. What is the
maximum number of possible words given this rule?
Combinations (subsets)
Definition
Given a set of objects X , a combination of size k is a subset A ⊆ X
of size k .
Definition
We let
(n
k
)
denote the number of combinations of size k of [n]. We
read
(n
k
)
as "n choose k".
▶ For a practical example on how combinations may be used, if I
have 10 friends and need to invite 5 to a party I’m throwing,
there is exactly
(10
5
)
many ways to do this.
Some Combination Question
Note: In the next slide, we compute
(n
k
)
explicitly. However, we do
not need to know how to compute this number in order to use it in
practice. This is a common theme in combinatorics.
▶ A lottery consists of choosing 5 red numbers from 1 to 59, and
then choosing a string of 3 white numbers from 1 to 12. How
many tickets are there? What if the white numbers need to be
distinct?
▶ How many flags can we make with 7 stripes, if we have 2
white, 2 red and 3 green stripes?
Counting Combinations
Theorem
For positive integers n and k with n ≥ k , (nk) = P(n,k)k! .
Proof.
▶ In order to create a permutation of [n] of size k , it suffices to
choose a combination A ⊆ [n] of size k to be the range, and
permute it.
▶ Thus, there are
(n
k
)× k! many ways to construct a
[n]-permutation of size k .
▶ However, we’ve defined P(n, k) as the number of
[n]-permutations of size k .
▶ Hence, P(n, k) =
(n
k
)
k!. Equivalently,
(n
k
)
= P(n,k)k! .
Precursor to Combinatorial Proofs
Given a set X of size n, determine how many subsets X has?
Count this two different ways. Do not forget that ∅ ⊆ X .