Math/Physic/Economic/Statistic Problems
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).
(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.)
(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) We 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:
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:
3. Optional problems
(1) Pick a random permutation of [n]. On average, how many fixed points does it have? (Recall that
i ∈[n] is a fixed point for a permutation σ : [n] →[n] if ball i goes in box i. That is, σ(i) = i.)
(2) How many coefficients of the polynomial (1 + x + x2)n are not divisible by 3?