Honors Exam 2010 COMBINATORICS
1. Patrol officers are to be paired for the 3-11 pm shift. Each pair must have an experienced and an inexperienced officer who are compatible. Compatible pairs are indicated below.
(a) What is the largest possible number of pairs with each officer in at most one pair?
(b) Prove that your answer to (a) is correct. Your proof should, of course, be concise.
(c) If the compatibility table was replaced by a ratings matrix C with nonnegative real entries and the goal was to maximize the sum of the ratings of the formed pairs, why is there a best pairing among the optimal solutions to the following problem?
Maximize ∑i,j cijxij
subject to ∑jxij = 1, for i = 1, . . . , 10
∑ixij = 1, for j = 1, . . . , 10
xij ≥ 0, for all (i, j).
2. A non-increasing sequence λ = (λ1, λ2, . . .) of nonnegative integers whose sum |λ| is finite is called a partition of n if |λ| = n. We call λi a part of λ if λi > 0. Prove the following facts. At least one of your proofs should use a generating function and at least one should use a bijection.
(a) The number of partitions of n into distinct parts equals the number into odd parts.
(b) The number of partitions of n into odd parts of which exactly k are distinct equals the number into distinct parts in which exactly k sequences of consecutive positive integers occur. (For example, (11, 11, 9, 5, 5, 5, 0, . . .) has exactly 3 distinct odd parts and in (11, 10, 9, 8, 6, 2, 0, . . .) exactly 3 sequences of consecutive positive integers occur.)
(c) The number of partitions of n into distinct parts such that ∑i≥1(-1)i-1λi = k equals the number into k odd parts.
3. Let n ≥ 0 be an integer, and let [n] = {1, 2, . . . , n} (so that [0] = ∅). A set partition of [n] is a collection of nonempty disjoint subsets of [n], called blocks, whose union is [n]. The number of set partitions of [n] is called the nth Bell number bn. The number of blocks in a set partition π is denoted |π|. The nth Bell polynomial is the polynomial bn(q) = ∑πq|π|, where the sum is over set partitions π of [n] (so that bn(1) = bn). For example, b4 = 15 and b4(q) = q + 7q2 + 6q3 + q4.
(a) Find ∑n≥0bn(xn/n!).
(b) Prove that the sequence of Bell numbers is log-convex: bn2 ≤ bn-1bn+1 for n ≥ 1. Does the fact that bkbl ≤ bk-1bl+1 for k ≤ l follow?
(c) Prove that the sequence of Bell polynomials is q-log-convex: bn-1(q)bn+1(q) - bn(q)2 has nonnegative coefficients for n ≥ 1. Does the fact that bk-1(q)bl+1(q) - bk(q)bl(q) has nonnegative coefficients for k ≤ l follow?
4. Let τ, µ and ν be partitions such that |τ | = |µ| + |ν|. Let f(τ, µ, ν) be the number of functions T with domain {(i, j)| µi < j ≤ τi} such that the number of pairs (i, j) that T maps to k is νk, for k ≥ 1, and such that
- T(i, j) ≤ T(i, j') for j < j';
- T(i, j) < T(I', j) for i < I';
- nk(I, J) ≥ nk+1(I, J) for I ≥ 1, µI ≤ J < τI and k ≥ 1,
(a) What is the algebraic significance of the numbers f(τ, µ, ν)?
(b) Why does f(τ, ν, µ) equal f(τ, µ, ν)?
(c) What is f(τ, µ, ν) if µ = (0, 0, . . .) and ν = (1, . . . , 1, 0, . . .)?