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 .
