Skip to main content
Contents Embed Prev Up Next \(\newcommand{\set}[1]{\{#1\}}
\newcommand{\ints}{\mathbb{Z}}
\newcommand{\posints}{\mathbb{N}}
\newcommand{\rats}{\mathbb{Q}}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\complexes}{\mathbb{C}}
\newcommand{\twospace}{\mathbb{R}^2}
\newcommand{\threepace}{\mathbb{R}^3}
\newcommand{\dspace}{\mathbb{R}^d}
\newcommand{\nni}{\mathbb{N}_0}
\newcommand{\nonnegints}{\mathbb{N}_0}
\newcommand{\dom}{\operatorname{dom}}
\newcommand{\ran}{\operatorname{ran}}
\newcommand{\prob}{\operatorname{prob}}
\newcommand{\Prob}{\operatorname{Prob}}
\newcommand{\height}{\operatorname{height}}
\newcommand{\width}{\operatorname{width}}
\newcommand{\length}{\operatorname{length}}
\newcommand{\crit}{\operatorname{crit}}
\newcommand{\inc}{\operatorname{inc}}
\newcommand{\HP}{\mathbf{H_P}}
\newcommand{\HCP}{\mathbf{H^c_P}}
\newcommand{\GP}{\mathbf{G_P}}
\newcommand{\GQ}{\mathbf{G_Q}}
\newcommand{\AG}{\mathbf{A_G}}
\newcommand{\GCP}{\mathbf{G^c_P}}
\newcommand{\PXP}{\mathbf{P}=(X,P)}
\newcommand{\QYQ}{\mathbf{Q}=(Y,Q)}
\newcommand{\GVE}{\mathbf{G}=(V,E)}
\newcommand{\HWF}{\mathbf{H}=(W,F)}
\newcommand{\bfC}{\mathbf{C}}
\newcommand{\bfG}{\mathbf{G}}
\newcommand{\bfH}{\mathbf{H}}
\newcommand{\bfF}{\mathbf{F}}
\newcommand{\bfI}{\mathbf{I}}
\newcommand{\bfK}{\mathbf{K}}
\newcommand{\bfP}{\mathbf{P}}
\newcommand{\bfQ}{\mathbf{Q}}
\newcommand{\bfR}{\mathbf{R}}
\newcommand{\bfS}{\mathbf{S}}
\newcommand{\bfT}{\mathbf{T}}
\newcommand{\bfNP}{\mathbf{NP}}
\newcommand{\bftwo}{\mathbf{2}}
\newcommand{\cgA}{\mathcal{A}}
\newcommand{\cgB}{\mathcal{B}}
\newcommand{\cgC}{\mathcal{C}}
\newcommand{\cgD}{\mathcal{D}}
\newcommand{\cgE}{\mathcal{E}}
\newcommand{\cgF}{\mathcal{F}}
\newcommand{\cgG}{\mathcal{G}}
\newcommand{\cgM}{\mathcal{M}}
\newcommand{\cgN}{\mathcal{N}}
\newcommand{\cgP}{\mathcal{P}}
\newcommand{\cgR}{\mathcal{R}}
\newcommand{\cgS}{\mathcal{S}}
\newcommand{\bfn}{\mathbf{n}}
\newcommand{\bfm}{\mathbf{m}}
\newcommand{\bfk}{\mathbf{k}}
\newcommand{\bfs}{\mathbf{s}}
\newcommand{\bijection}{\xrightarrow[\text{onto}]{\text{$1$--$1$}}}
\newcommand{\injection}{\xrightarrow[]{\text{$1$--$1$}}}
\newcommand{\surjection}{\xrightarrow[\text{onto}]{}}
\newcommand{\nin}{\not\in}
\newcommand{\prufer}{\text{prüfer}}
\DeclareMathOperator{\fix}{fix}
\DeclareMathOperator{\stab}{stab}
\DeclareMathOperator{\var}{var}
\newcommand{\inv}{^{-1}}
\newcommand{\ds}{\displaystyle}
\newcommand{\mbf}[1]{\mathbf{#1}}
\newcommand{\mc}[1]{\mathcal{#1}}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Handout 8.1 Introduction to Ordinary Generating Functions
Formal Power Series.
Sequence
\(\sigma = \{a_{n}\colon n\geq 0\}\)
Formal power series
\(F(x) = \displaystyle\sum_{n=0}^{\infty} a_{n} x^{n}\)
Interval and radius of convergence?
Representing as functions?
In combinatorics, we call formal power series
generating functions .
Proposition 8.1 .
Let \(A(x)=\sum_{n=0}^{\infty} a_{n}x^{n}\) and \(B(x)=\sum_{n=0}^{\infty} b_{n}x^{n}\) be generating functions. Then \(A(x)B(x)\) is the generating function of the sequence whose coefficient on \(x^{n}\) is given by
\begin{equation*}
a_{0}b_{n}+a_{1}b_{n-1}+a_{2}b_{n-2}+\dots+a_{n}b_{0}=\sum_{k=0}^{n} a_{k}b_{n-k}.
\end{equation*}
Handing stuff out again. Suppose you wanted to make a really boring “fruit” basket that contains only apples. Let’s also say that you have only
\(6\) (identical) apples available. For aesthetic reasons, you insist that the basket contain exactly
\(1\text{,}\) \(3\text{,}\) or
\(4\) apples.
Peer instruction questions 1–2.
The generating function for the number of fruit baskets with
\(n\) apples subject to these rules is
Now we’ve got oranges, too! We have six (identical) oranges to use in fruit baskets, and we don’t care about aesthetics for oranges. (Still only allow 1, 3, or 4 apples.)
How many ways to make a fruit basket with
\begin{align*}
(x+x^{3}+x^{4})\amp(1+x+x^{2}+x^{3}+x^{4}+x^{5}+x^{6})\\\\
\amp= x + x^2 + 2 x^3 + 3 x^4 + 3 x^5 + 3 x^6 + 3 x^7 + 2 x^8 + 2 x^9 + x^{10}
\end{align*}
Suppose we now have bananas to add and that we must place at least one banana in a fruit basket. This introduces which factor?
Peer instruction question 3
Activity 8.1.1 .
Find the generating function in which the coefficient on \(x^{n}\) is the number of fruit baskets containing \(n\) pieces of fruit subject to the following restrictions:
Kiwi: at least
\(2\) and no more than
\(5\)
Grapefruit: either none or at least
\(7\)
Peer instruction question 4.
Activity 8.1.2 .
Find the generating function in which the coefficient on \(x^{n}\) is the number of fruit baskets containing \(n\) pieces of fruit subject to the following restrictions:
Apples:
\(1\text{,}\) \(3\text{,}\) or
\(4\)
Activity 8.1.3 .
Suppose in the country Combinatoria, they use coins with values 1, 2, 5, 10, 50, and 100. If you would like to write a generating function in which the coefficient on
\(x^{n}\) is the number of ways to form a collection of coins worth
\(n\) subject to the restriction that the number of coins of value
\(5\) is one, three, four, or five, what factor would you introduce into your generating function?
My Own Journey with Generating Functions.
Theorem 8.2 . Keller and Young 2020.
The ordinary generating function for the number of hereditary unit interval orders with \(n\) points, \(h_{n}\text{,}\) is
\begin{align*}
H(x)\amp= \frac{x^{5} - 9x^{4} + 12x^{3} - 6x^{2} + x}{1-x^{5} + 14x^{4} - 29x^{3} + 23x^{2} - 8x}\\
\amp= x + 2x^{2}+5x^{3}+14x^{4}+42x^{5}+132x^{6}+428x^{7}+1415x^{8}+\cdots
\end{align*}
and \(h_{n}\) is asymptotically \(0.08346\cdot 3.373133^{n}\text{.}\)
\begin{equation*}
C_{n} \sim \frac{4^{n}}{n^{3/2}\sqrt{\pi}}
\end{equation*}
Theorem 8.3 . Keller and Young 2020.
The generating function for the number of unit interval orders of dimension at most \(2\) with \(n\) points, \(d_{n}\text{,}\) is
\begin{align*}
D(x) \amp= \frac{-(5x^{8} - 41x^{7} + 101x^{6} - 129x^{5} + 96x^{4} - 42x^{3} + 10x^{2} - x)}{7x^{8} - 66x^{7} + 197x^{6} - 311x^{5} + 294x^{4} - 172x^{3} + 61x^{2} - 12x + 1}\\
\amp= x + 2x^{2}+5x^{3}+14x^{4}+42x^{5}+132x^{6}+426x^{7}+1390x^{8}+\cdots
\end{align*}
and \(d_{n}\) is asymptotically \(0.12958\cdot 3.2148^{n}\text{.}\)
