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 9.3 Solving a Nonlinear Recurrence
RUBOTS.
Rooted
Unlabeled
Binary
Ordered
Trees
By convention, we want the
\(1\) -vertex graph to be a RUBOT with one leaf.
Let \(c_{n}\) denote the number of RUBOTs with \(n\) leaves . (NOT vertices!) Take \(c_{0}=0\) by convention. The generating function for the number of RUBOTs is then
\begin{equation*}
C(x)\displaystyle = \sum_{n=0}^{\infty} c_{n}x^{n} = \phantom{0+1x+2x^3+5x^4 + \cdots}
\end{equation*}
Activity 9.3.1 .
Find
\(c_{1}\text{,}\) \(c_{2}\text{,}\) \(c_{3}\text{,}\) and
\(c_{4}\) by drawing the RUBOTs with
\(1\text{,}\) \(2\text{,}\) \(3\text{,}\) and
\(4\) leaves and then start writing out
\(C(x)\text{.}\)
Activity 9.3.2 . Decomposing RUBOTs.
(a) Let
\(l\) and
\(r\) be the left and right children, respectively, of the root of a RUBOT. How many RUBOTs with
\(17\) leaves have
\(12\) of those leaves descendants of
\(l\) and
\(5\) descendants of
\(r\text{?}\)
(b) Generalize to a formula for the number of RUBOTs with
\(n\) leaves in which the left child has
\(k\) leaves.
(c) Give a nonlinear recurrence for
\(c_{n}\text{.}\)
\begin{align*}
C(x) \amp = 0 + x + c_1c_1 x^2 + (c_1c_2+c_2c_1)x^3 + \cdots +
\sum_{k=1}^{n-1}c_k c_{n-k} x^n+ \cdots \\
C(x)\amp= 0 + x + (c_0c_2 + c_1c_1 +c_2c_0)x^2 + \cdots + \sum_{k=0}^{n}c_k c_{n-k} x^n+ \cdots \\
C^2(x) \amp = c_0^2 + (c_0c_1 + c_1c_0)x + (c_0c_2 +c_1c_1 + c_2c_0)x^2 + \cdots + \sum_{k=0}^{n}c_k c_{n-k} x^n+ \cdots\\
C(x) \amp= x+C^2(x)
\end{align*}
Activity 9.3.3 .
Use the quadratic formula to solve
\begin{equation*}
C^{2}(x) -C(x) + x = 0
\end{equation*}
for \(C(x)\text{.}\)
Recall that
\(\displaystyle (1-4x)^{-1/2}= \sum_{n=0}^{\infty} \binom{2n}{n}x^{n}\text{.}\)
Theorem 9.6 .
The generating function for the number \(c_{n}\) of rooted, unlabeled, binary, ordered trees with \(n\) leaves is
\begin{equation*}
C(x) = \frac{1-\sqrt{1-4x}}{2}= \sum_{n=1}^{\infty} \frac{1}{n}\binom{2n-2}{n-1}x^{n}.
\end{equation*}
Ramsey Numbers.
Definition 9.7 .
The
Ramsey number \(R(m,n)\) is the least number
\(t\) such that every graph on at least
\(t\) vertices contains a clique of size
\(m\) or an independent set of size
\(n\text{.}\)
Activity 9.3.4 .
(a) What is a clique? What is an independent set?
(b) Explain why
\(R(2,2) = 2\text{.}\)
(c) Can you draw a
\(4\) -vertex graph that has neither a
\(3\) -clique nor an independent set of size
\(3\text{?}\) What about
\(5\) vertices?
\(6\) vertices?
Proposition 9.8 .
The Ramsey number
\(R(3,3) =6\text{.}\)
