8jJUrTR5xXP3Vw
MATH 239 – Assignment 1
MATH 239 – Assignment 1
Due Thursday September 23 at 11am Eastern time via Crowdmark.
(Question 1) For any integer n ≥ 1 let An be the set of all ordered pairs of subsets of {1, . . . , n}:
An = {(S1, S2) : S1, S2 ⊆ {1, . . . , n}}.
By counting |An| in two different ways, prove that
4n =
n∑
k=0
(
n
k
)
3n−k.
(Question 2) A permutation matrix of size n is an n×n matrix with entries in the set {0, 1} such that
every row contains exactly one 1 and every column contains exactly one 1. Prove that for any positive
integer n the set of permutations of {1, . . . , n} is in bijection with the set of permutation matrices of
size n.
(Question 3) For the following sets A and functions ω, either explain why ω is not a weight function
for that set or give the generating series ΦωA(x). Write the generating series in a closed form (that is,
without Σ or . . .) if possible.
1. Fix a positive integer n and let A be the set of proper subsets of {1, 2, . . . , n} and let ω be the size
of the subset.
2. DNA is a molecule composed of a chain of nucleotides. There are four different nucleotides in
DNA: adenine, cytosine, guanine, thymine. So, DNA sequences can be represented mathemati-
cally as words on the alphabet A,C,G, T . Let A be the set of DNA sequences and let ω be the
length of the sequence (that is, the total number of nucleotides).
3. Let A be again the set of DNA sequences and let ω be the number of adenine nucleotides.
4. Let A =
⋃
n≥0An where A0 = {∅} and An for n ≥ 1 consists of the set of permutations of
{1, 2, . . . , n}. For σ ∈ A let ω(σ) = n where σ ∈ An (consider why this is well defined).
FALL 2021 MATH 239: INTRODUCTION TO COMBINATORICS Page 1