91Ó°ÊÓ

Prove that the number of 2 -by-n arrays $$\left[\begin{array}{llll}x_{11} & x_{12} & \cdots & x_{1 n} \\ x_{21} & x_{22} & \cdots & x_{2 n}\end{array}\right]$$ that can be made from the numbers \(1,2 \ldots, 2 n\) such that $$\begin{array}{c} x_{11}

. (a) Calculate the partition number \(p_{6}\) and construct the diagram of the set \(\mathcal{P}_{6}\), partially ordered by majorization. (b) Calculate the partition number \(p_{7}\) and construct the diagram of the set \(\mathcal{P}_{7}\), partially ordered by majorization.

Let \(t_{1}, t_{2}, \ldots, t_{m}\) be distinct positive integers, and let $$q_{n}=q_{n}\left(t_{1}, t_{2}, \ldots, t_{m}\right)$$ equal the number of partitions of \(n\) in which all parts are taken from \(t_{1}, t_{2}, \ldots, t_{m}\). Define \(q_{0}=1\). Show that the generating function for \(q_{0}, q_{1}, \ldots, q_{n}, \ldots\) is$$\prod_{k=1}^{m}\left(1-x^{t_{k}}\right)^{-1} .$$

Prove that conjugation reverses the order of majorization; that is, if \(\lambda\) and \(\mu\) are partitions of \(n\) and \(\lambda\) is majorized by \(\mu\), then \(\mu^{*}\) is majorized by \(\lambda^{*}\)

Use the generating function for the large Schröder numbers to compute the first few large Schröder numbers.

. Prove that the Catalan number \(C_{n}\) equals the number of lattice paths from \((0,0)\) to \((2 n, 0)\) using only upsteps \((1,1)\) and downsteps \((1,-1)\) that never go above the horizontal axis (so there are as many upsteps as there are downsteps). (These are sometimes called Dyck paths.)

The large Schröder number \(C_{n}\) counts the number of subdiagonal HVD-lattice paths from \((0,0)\) to \((n, n) .\) The small Schröder number counts the number of dissections of a convex polygonal region of \(n+1 .\) Since \(R_{n}=2 s_{n+1}\) for \(n \geq 1\), there are as many subdiagonal HVD-lattice paths from \((0,0)\) to \((n, n)\) as there are dissections of a convex polygonal region of \(n+1\) sides. Find a one-to-one correspondence between these lattice paths and these dissections.