91Ó°ÊÓ

Let \(h_{n}\) denote the number of regions into which a convex polygonal region with \(n+2\) sides is divided by its diagonals, assuming no three diagonals have a common point. Define \(h_{0}=0 .\) Show that $$h_{n}=h_{n-1}+\left(\begin{array}{c}n+1 \\ 3\end{array}\right)+n, \quad(n \geq 1)$$ Then determine the generating function and obtain a formula for \(h_{n}\).

Let \(\alpha\) be a real number. Let the sequence \(h_{0}, h_{1}, h_{2}, \ldots, h_{n}, \ldots\) be defined by \(h_{0}=1\), and \(h_{n}=\alpha(\alpha-1) \cdots(\alpha-n+1),(n \geq 1)\). Determine the exponential generating function for the sequence.

Let \(S\) denote the multiset \(\left\\{\infty \cdot e_{1}, \infty \cdot e_{2}, \ldots, \infty \cdot e_{k}\right\\} .\) Determine the exponential generating function for the sequence \(h_{0}, h_{1}, h_{2}, \ldots, h_{n}, \ldots\), where \(h_{0}=1\) and, for \(n \geq 1\), (a) \(h_{n}\) equals the number of \(n\) -permutations of \(S\) in which each object occurs an odd number of times. (b) \(h_{n}\) equals the number of \(n\) -permutations of \(S\) in which each object occurs at least four times. (c) \(h_{n}\) equals the number of \(n\) -permutations of \(S\) in which \(e_{1}\) occurs at least once, \(e_{2}\) occurs at least twice, \(\ldots, e_{k}\) occurs at least \(k\) times. (d) \(h_{n}\) equals the number of \(n\) -permutations of \(S\) in which \(e_{1}\) occurs at most once, \(e_{2}\) occurs at most twice, \(\ldots, e_{k}\) occurs at most \(k\) times.

Solve the recurrence relation \(h_{n}=(n+2) h_{n-1},(n \geq 1)\) with initial value \(h_{0}=2\).

Solve the recurrence relation \(h_{n}=5 h_{n-1}-6 h_{n-2}-4 h_{n-3}+8 h_{n-4},(n \geq 4)\) with initial values \(h_{0}=0, h_{1}=1, h_{2}=1\), and \(h_{3}=2\).

Solve the nonhomogeneous recurrence relation $$\begin{array}{l}h_{n}=2 h_{n-1}+n, \quad(n \geq 1) \\\h_{0}=1 \end{array}$$

Solve the following recurrence relations by using the method of generating functions as described in Section \(7.4\) : (a) \(h_{n}=4 h_{n-2},(n \geq 2) ; h_{0}=0, h_{1}=1\) (b) \(h_{n}=h_{n-1}+h_{n-2},(n \geq 2) ; h_{0}=1, h_{1}=3\) (c) \(h_{n}=h_{n-1}+9 h_{n-2}-9 h_{n-3},(n \geq 3) ; h_{0}=0, h_{1}=1, h_{2}=2\) (d) \(h_{n}=8 h_{n-1}-16 h_{n-2},(n \geq 2) ; h_{0}=-1, h_{1}=0\) (e) \(h_{n}=3 h_{n-2}-2 h_{n-3},(n \geq 3) ; h_{0}=1, h_{1}=0, h_{2}=0\) (f) \(h_{n}=5 h_{n-1}-6 h_{n-2}-4 h_{n-3}+8 h_{n-4},(n \geq 4) ; h_{0}=0, h_{1}=1, h_{2}=1, h_{3}=2\)

Solve the recurrence relation $$\begin{array}{l}h_{n}=3 h_{n-1}-4 n, \quad(n \geq 1) \\\h_{0}=2\end{array}$$ from Section \(7.6\) using generating functions.