Skip to main content
\(\newcommand{\cycle}[1]{\arraycolsep 5 pt \left(\begin{array}#1\end{array}\right)} \newcommand{\importantarrow}{\Rightarrow} \newcommand{\qchoose}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}_q} \def\neg1choose#1#2{\genfrac{[}{]}{0pt}{}{#1}{#2}_{-1}} \newcommand{\bp}{ \begin{enumerate}{\setcounter{enumi}{\value{problemnumber}}}} \newcommand{\ep}{\setcounter{problemnumber}{\value{enumi}} \end{enumerate}} \newcommand{\ignore}[1]{} \renewcommand{\bottomfraction}{.8} \renewcommand{\topfraction}{.8} \newcommand{\apple}{\text{🍎}} \newcommand{\ap}{\apple} \newcommand{\banana}{\text{🍌}} \newcommand{\ba}{\banana} \newcommand{\pear}{\text{🍐}} \newcommand{\pe}{\pear} \DeclareMathOperator{\Fix}{Fix} \DeclareMathOperator{\Orb}{Orb} \newcommand{\F}{\mathcal{F}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Section C.3 Applications to recurrences.

We saw that ordinary generating functions often play a role in solving recurrence relations. We found them most useful in the constant coefficient case. Exponential generating functions are useful in solving recurrence relations where the coefficients involve simple functions of \(n\text{,}\) because the \(n!\) in the denominator can cancel out factors of \(n\) in the numerator.

Problem 384

Consider the recurrence \(a_n=na_{n-1} +n(n-1)\text{.}\) Multiply both sides by \(\frac{x^n}{n!}\text{,}\) and sum from \(n=2\) to \(\infty\text{.}\) (Why do we sum from \(n=2\) to infinity instead of \(n=1\) or \(n=0\text{?}\)) Letting \(y = \sum_{i=0}^\infty a_ix^i\text{,}\) show that the left-hand side of the equation is \(y-a_0 -a_1x\text{.}\) Express the right hand side in terms of \(y\text{,}\) \(x\text{,}\) and \(e^x\text{.}\) Solve the resulting equation for \(y\) and use the result to get an equation for \(a_n\text{.}\) (A finite summation is acceptable in your answer for \(a_n\text{.}\))

Problem 385

The telephone company in a city has \(n\) subscribers. Assume a telephone call involves exactly two subscribers (that is, there are no calls to outside the network and no conference calls), and that the configuration of the telephone network is determined by which pairs of subscribers are talking. Notice that we may think of a configuration of the telephone network as a permutation whose cycle decomposition consists entirely of one-cycles and two-cycles, that is, we may think of a configuration as an involution in the symmetric group \(S_n\text{.}\)

(a)

Give a recurrence for the number \(c_n\) of configurations of the network. (Hint: Person \(n\) is either on the phone or not.)

(b)

What are \(c_0\) and \(c_1\text{?}\)

(c)

What are \(c_2\) through \(c_6\text{?}\)

Problem 386

Recall that a derangement of \([n]\) is a permutation of \([n]\) that has no fixed points, or equivalently is a way to pass out \(n\) hats to their \(n\) different owners so that nobody gets the correct hat. Use \(d_n\) to stand for the number of derangements of \([n]\text{.}\) We can think of derangement of \([n]\) as a list of \(1\) through \(n\) so that \(i\) is not in the \(i\)th place for any \(n\text{.}\) Thus in a derangement, some number \(k\) different from \(n\) is in position \(n\text{.}\) Consider two cases: either \(n\) is in position \(k\) or it is not. Notice that in the second case, if we erase position \(n\) and replace \(n\) by \(k\text{,}\) we get a derangement of \([n-1]\text{.}\) Based on these two cases, find a recurrence for \(d_n\text{.}\) What is \(d_1\text{?}\) What is \(d_2\text{?}\) What is \(d_0\text{?}\) What are \(d_3\) through \(d_6\text{?}\)

Subsection C.3.1 Using calculus with exponential generating functions

Problem 387

Your recurrence in Problem 385 should be a second order recurrence.

(a)

Assuming that the left hand side is \(c_n\) and the right hand side involves \(c_{n-1}\) and \(c_{n-2}\text{,}\) decide on an appropriate power of \(x\) divided by an appropriate factorial by which to multiply both sides of the recurrence. Using the fact that the derivative of \(\frac{x^n}{n!}\) is \(\frac{x^{n-1}}{(n-1)!}\text{,}\) write down a differential equation for the EGF \(T(x) = \sum_{i=0}^\infty c_i\frac{x^i}{i!}\text{.}\) Note that it makes sense to substitute 0 for \(x\) in \(T(x)\text{.}\) What is \(T(0)\text{?}\) Solve your differential equation to find an equation for \(T(x)\text{.}\)

(b)

Use your EGF to compute a formula for \(c_n\text{.}\)

Hint

At some point, you may find the binomial theorem to be useful.

Problem 388

Your recurrence in Problem 386 should be a second order recurrence.

(a)

Assuming that the left-hand side is \(d_n\) and the right hand side involves \(d_{n-1}\) and \(d_{n-2}\text{,}\) decide on an appropriate power of \(x\) divided by an appropriate factorial by which to multiply both sides of the recurrence. Using the fact that the derivative of \(\frac{x^n}{n!}\) is \(\frac{x^{n-1}}{(n-1)!}\text{,}\) write down a differential equation for the EGF \(D(x) = \sum_{i=0}^\infty d_i\frac{x^i}{i!}\text{.}\) What is \(D(0)\text{?}\) Solve your differential equation to find an equation for \(D(x)\text{.}\)

(b)

Use the equation you found for \(D(x)\) to find an equation for \(d_n\text{.}\) Compare this result with the one you computed by inclusion and exclusion.