MA 4133/6133 - Homework















Starred* problems should be completed if you are enrolled in the course at the 6000 level.
I recommend (but do not require) that all students read and attempt these problems. If you make some significant progress, you should turn it in.

Homework 10 11, due Dec 2

Bóna p339: 23, 27, 28
Bóna p476: 25, 27

Homework 10, due Nov 17 at 1pm

Bóna p176: 27, 28, 32, 33, 40

A. Recall that the moment generating function of a random variable X is the exponential generating function for the sequence E(Xn). Show that if X has the moment generating function et2/2, then X2 has the moment generating function (1 - 2t)-1/2.

Note: et2/2 is the mgf for the standard normal distribution. (1 - 2t)-1/2 is the mgf for the chi-squared (1) distribution. Modulo the fact that an mgf determines the distribution of its random variable, Problem A proves that the square of a standard normal random variable is chi-squared.

Homework 9, due Nov 3 at 1pm

A. If Δ is a simplicial complex, then the f-vector of Δ is the sequence

fiΔ = #{faces of Δ having i vertices}

Find the generating function for fiΔ in the case where Δ is a single d-simplex.

B. If Δ and Γ are simplicial complexes, then the join of Δ and Γ is the simplicial complex Δ * Γ with vertex set V(Δ) ∪ V(Γ), and all faces of the form δ ∪ γ for a face δ of Δ and a face γ of Γ. Using the Product Lemma and/or Meta-Theorem, relate the generating functions for the f-vectors of Δ, Γ, and Δ * Γ.

C. Find a power series representation for sqrt(1 - 16x2), and relate it to the Catalan numbers.

D. If cn is the nth Catalan number, prove the identity

(Sum from i = 0 to n of   c2ic2n - 2i) = 4n cn

Hint: Use generating functions. The preceding problem and the Product Lemma are both related.

E. Show that the number of ways to divide an n-gon into triangles by adding (noncrossing) edges between existing vertices is counted by a Catalan nuber.

Homework 8, due Oct 27 at 1pm

Bóna p176: 25, 26, 48, 49a, 49b

A. Show that the Catalan numbers count the number of NE lattice paths that do not pass above the diagonal line y = x.

Homework 7, due Oct 20 at 1pm

Bóna p143: 20, 22, 23, 26, 29* (see also problem 9), 32
Bóna p176: 24, 47

Homework 6, due Oct 13 at 1pm

Bóna p126: 34, 36, 40, 43, 52, 55

A. Find an arrangement of "hyperplanes" (lines) in R2 such that the lines are in 1-1 correspondence with elements of order 2, and the regions are in 1-1 correspondence with elements of the dihedral group D2n.

B*. Describe all subspaces of R4 that are preserved by the action of S4 by permutation matrices. (We described at least one such subspace in class!)

Homework 5, due Oct 6 at 1pm

Bóna p126: 31, 32, 33, 38, 39, 41, 42

Homework 4, due Sep 19 at 1pm

Bóna p107: 21, 28, 30*, 31, 32, 33, 34, 36

Hint on 31: n2 + 2n = (n + 1)n + n.
Hint on 30: It might be helpful to show that there are a lot of partitions having all parts small.

Homework 3, due Sep 12 at 1pm

Bóna p79: 33, 38
Bóna p107: 17, 24, 26, 27, 35

Homework 2, due Sep 8 at 1pm

Bóna p53: 49, 53
Bóna p79: 28, 36, 40, 43, 45

Homework 1, due Aug 29 at 1pm

Bóna p53: 26, 28, 34, 35, 39, 48

A. Write a detailed proof of Theorem 3.5 from Bóna.