Problem 372
Find the EGF (exponential generating function) for the sequence \(a_n=2^n\text{.}\) What does this say about the EGF for the number of subsets of an \(n\)-element set?
Section C.2 Exponential Generating Functions
¶We say that the expression \(\sum_{i=0}^\infty a_i\frac{x^i}{i!}\) is the exponential generating function for the sequence \(a_i\text{.}\) It is standard to use EGF as a shorthand for exponential generating function. In this context we call the generating function \(\sum_{i=0}^n a_ix^i\) that we originally studied the ordinary generating function for the sequence \(a_i\text{.}\) You can see why we use the term exponential generating function by thinking about the exponential generating function (EGF) for the all ones sequence,
\begin{equation*}
\sum_{i=0}^\infty 1\frac{x^i}{i!} = \sum_{i=0}^\infty \frac{x^i}{i!}
=e^x,
\end{equation*}
which we also denote by \(\exp (x)\text{.}\) Recall from calculus that the usual definition of \(e^x\) or \(\exp(x)\) involves limits at least implicitly. We work our way around that by defining \(e^x\) to be the power series \(\sum_{i=0}^\infty \frac{x^i}{i!}\text{.}\)
Problem 373
Find the EGF (exponential generating function) for the number of ways to paint the \(n\) streetlight poles that run along the north side of Main Street in Anytown, USA using four colors.
Problem 374
For what sequence is \(\frac{e^x-e^{-x}}{2} =\cosh x\) the EGF (exponential generating function)?
Problem 375
For what sequence is \(\ln(\frac{1}{1-x})\) the EGF? (\(\ln (y)\) stands for the natural logarithm of \(y\text{.}\) People often write \(\log(y)\) instead.) Hint: Think of the definition of the logarithm as an integral, and don't worry at this stage whether or not the usual laws of calculus apply, just use them as if they do! We will then define \(\ln({ 1-x})\) to be the power series you get. 1 It is possible to define the derivatives and integrals of power series by the formulas
\begin{equation*}
\frac{d}{dx}
\sum_{i=0}^\infty b_ix^i = \sum_{i=1}^\infty ib_ix^{i-1}
\end{equation*}
and
\begin{equation*}
\int_0^x
\sum_{i=0}^\infty b_ix^i = \sum_{i=0}^\infty \frac{b_i}{i+1}x^{i+1}
\end{equation*}
rather than by using the limit definitions from calculus. It is then possible to prove that the sum rule, product rule, etc. apply. (There is a little technicality involving the meaning of composition for power series that turns into a technicality involving the chain rule, but it needn't concern us at this time.)
Problem 376
What is the EGF for the number of permutations of an \(n\)-element set?
Problem 377
What is the EGF for the number of ways to arrange \(n\) people around a round table? Try to find a recognizable function represented by the EGF. Notice that we may think of this as the EGF for the number of permutations on \(n\) elements that are cycles.
Hint
An earlier problem may help you put your answer into a simpler form.
Problem 378
What is the EGF \(\sum_{n=0}^\infty p_{2n}\frac{x^{2n}}{(2n)!}\) for the number of ways \(p_{2n}\) to pair up \(2n\) people to play a total of \(n\) tennis matches (as in Problems 12 and 44)?
Hint
What is the power series representation of \(e^{x^2}\text{?}\)
Problem 379
What is the EGF for the sequence \(0,1,2,3,\ldots\text{?}\) You may think of this as the EFG for the number of ways to select one element from an \(n\) element set. What is the EGF for the number of ways to select two elements from an \(n\)-element set?
Problem 380
What is the EGF for the sequence \(1,1,\ldots,1,\ldots\text{?}\) Notice that we may think of this as the EGF for the number of identity permutations on an \(n\)-element set, which is the same as the number of permutations of \(n\) elements that are products of 1-cycles, or as the EGF for the number of ways to select an \(n\)-element set (or, if you prefer, an empty set) from an \(n\)-element set. As you may have guessed, there are many other combinatorial interpretations we could give to this EGF.
Problem 381
What is the EGF for the number of ways to select \(n\) distinct elements from a one-element set? What is the EGF for the number of ways to select a positive number \(n\) of elements from a one element set? Hint: When you get the answer you will either say “of course,” or “this is a silly problem.”
Hint
There is only one element that you may choose. In the first case you either choose it or you don't.
Problem 382
What is the EGF for the number of partitions of a \(k\)-element set into exactly one block? (Hint: is there a partition of the empty set into exactly one block?)
Problem 383
What is the EGF for the number of ways to arrange \(k\) books on one shelf (assuming they all fit)? What is the EGF for the number of ways to arrange \(k\) books on a fixed number \(n\) of shelves, assuming that all the books can fit on any one shelf? (Remember Problem 122.)