MA241 ASSIGNMENT 2
DUE 28/10/2021
Final version, updated 21/10 (hints added 25/10)
“W3” means you are particularly equipped (and encouraged) to solve these problems before week 4.
1. Warm-up questions (Do these, but do not turn them in.)
(1) W3 Let n ≥k ≥1 be Integers.
(a) A function from {1,…,k} to {1,…,n} is called strictly increasing if
f(1) < f(2) < ···< f(k −1) < f(k).
How many strictly increasing functions are there from {1,…,k} to {1,…,n}?
(b) A function from {1,…,k} to {1,…,n} is called non-decreasing if
f(1) ≤f(2) ≤···≤f(k −1) ≤f(k).
How many non-decreasing functions are there from {1,…,k} to {1,…,n}? (Hint: Consider
the numbers f(1) −1,f(2) −f(1),f(3) −f(2),…,f(k) −f(k −1),n −f(k).)
(2) W3 Show that S(n,n−1) = (n
2
) and S(n,2) = 2n−1 −1. Find a closed formula for S(n,n−2). (Recall
that S(n,k) is the number of set partitions of [n] into k nonempty subsets.) A previous version had
S(n,n −3) – the new version is less complicated.
(3) W3 Show that the number of partitions of n into at most k parts is equal to the number pk(n) of
partitions of n + k into exactly k parts. (This is the number ways of distributing n unlabeled balls in
k unlabeled boxes.)
(4) W3 Suppose n is a positive integer satisfying the condition that the number of self-conjugate partitions
of n is even. What can you say about the parity of p(n)?
2. Problems to be turned in
(1) W3 Let n be a nonnegative integer. Let An be the set of subsets of {1,…,n} that do not contain
any consecutive pair of numbers. For example, A3 = {∅,{1},{2},{3},{1,3}}.
(a) Compute A0,A1,A2,A3,A4,A5.
(b) Make a conjecture about |An| for all n ≥1.
(c) Prove your conjecture.
(2) W3 Find a bijective proof for the identity 6S(n,3) + 6S(n,2) + 3S(n,1) = 3n.
(3) W3 Find a bijective proof for the identity Bn = ∑n−1
k=0
(n−1
k
)Bk. (Recall Bn is the number of set
partitions of [n] into nonempty subsets.)
(4) W3
(a) Let n ≥2. Prove that the number of partitions of n in which the two largest parts are equal
(e.g. 5 + 5 + 3 + 1) is equal to p(n) −p(n −1).
(b) Find/prove a formula, along the same lines, for the number of partitions of n ≥3 in which the
three largest parts are equal.
(c) Prove that the sequence p(n) −p(n −1) (for n ≥ 2) is nondecreasing. (That is, show that
(p(n) −p(n −1)) −(p(n −1) −p(n −2) ≥0 holds.)
(5) The following three problems are glimpses of extremal combinatorics. Solve at least one of them.
(These are all slightly tricky — if you do not come up with a complete solution, record your best
attempt.)
Date: October 25, 2021.
1
(a) Find the minimum number of lines required to hit every vertex of a 10 ×10 square grid of dots,
if no line is allowed to be horizontal or vertical. (Prove it is the minimum.)
(b) Prove that if 8 2 ×2 blocks of squares are removed from an 8 ×8 chessboard, then there is at
least one 2 ×2 block in the remaining squares. Is the same true if 9 2 ×2 blocks are removed?
(c) Suppose squares of an 8 ×8 chessboard are covered in grass, which spreads as follows: Grass
spreads to a square when two adjacent squares (i.e. squares that share an edge) are covered.
Find the minimum number of squares which must initially be covered in grass to ensure that
the whole chessboard is eventually covered in grass. (Prove it is the minimum.)
Hints:
(a) How many points are on the edge of the square grid?
(b) Represent the 49 2 ×2 blocks of the chessboard as a 7 ×7 grid.
(c) Consider the perimeter of the grassy area.
(6)Define below sets Xn,Yn,Zn,Wn. Write down the sets for n = 1,2,3,4, and confirm the following:
|X1|= |Y1|= |Z1|= |W1|= 1
|X2|= |Y2|= |Z2|= |W2|= 2
|X3|= |Y3|= |Z3|= |W3|= 5
|X4|= |Y4|= |Z4|= |W4|= 14.
Prove that for all n, |Xn| = |Yn| = |Zn| = |Wn|. Preferably, prove this by finding explicit bi-
jections. (The bijections are not very obvious — this problem will require some experimenta-
tion/guesswork/creativity. Again, if you do not come up with a complete solution, record your best
attempt.)
• The set Xn of north-east lattice paths from (0,0) to (n,n) that do not cross (strictly) above the
diagonal line from (0,0) to (n,n). E.g. with n = 4 here is one of the 14:
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•(4,4)
• The set Yn of ways of filling a 2 ×n grid of boxes with the numbers 1,…,2n (using each number
once), such that rows increase from left to right, and columns increase from top to bottom, e.g.
with n = 3 here is one of the 5:
1 3 4
2 5 6
• The set Zn of triangulations of a (convex) (n + 2)-gon. This means a collection of noncrossing
diagonals that divide the polygon into triangles, e.g. with n = 4 here are two of the 14:
1 2
3
45
6
1 2
3
45
6
• The set Wn of tilings of an n ×n staircase shape with n rectangles, e.g. for n = 3 here are two
of the 5:
2
Hints:
• Xn to Yn: Find a bijection. There are 2n steps (each rightward or upward) in a Dyck path, and
2n numbers in the grid…
• Finding a bijection from Zn to any of the others is quite tricky. If you don’t find one, try instead
proving that Zn satisfies the Catalan recursion from Friday’s lecture: |Zn+1|= ∑n
i=0 |Zi||Zn−i|.
(Each triangulation contains exactly one triangle whose vertices are 1,2,i for some i.)
• For Wn: Again, if you do not find a bijection to one of the other sets, try proving the same
recursion as is in the last hint. The n squares along the staircase must all be in different
rectangular tiles — and one of these tiles must contain the square in the northwest corner.
