\documentclass[12pt]{article}

\usepackage[margin=1in,dvips]{geometry}
\usepackage{fancyhdr,lastpage}
\usepackage{amsmath}
\usepackage{tikz}
\usetikzlibrary{calc}
\usepackage{cjhebrew}
\usepackage{substr}

\IfSubStringInString{\detokenize{solution}}{\jobname}{%
  % Solutions
  \newcommand\qfill{}
  \newcommand\qpage{}
  \newcommand\qonly[1]{}
  \newcommand\answer[1]{#1}
  \newcommand\question[1]{{\em #1}}
  \newcommand\rubric[1]{}
}
{%
  \newcommand\qfill{\vfill}
  \newcommand\qpage{\newpage}
  \newcommand\qonly[1]{#1}
  \newcommand\answer[1]{}
  \newcommand\question[1]{#1}
  \newcommand\rubric[1]{}
}

\pagestyle{fancy}
\lhead{MATH 387-01}
\chead{Problem Set \#2\answer{ solutions}}
\rhead{\qonly{Name: \framebox{\phantom{Your name goes here}}}}
\lfoot{}
\cfoot{Page \thepage\ of \pageref{LastPage}}
\rfoot{{\bf due September 21, 2015}}

\begin{document}
\begin{enumerate}
\item {\bf (10 points)} \question{Prove that for every positive
    integer $n$, \[\sum_{k=0}^n\binom
    nk^2=\sum_{\ell=0}^n\sum_{r=0}^{\lfloor\frac{n-\ell}2\rfloor}\binom
    n\ell\binom{n-\ell}r\binom{n-\ell-r}r.\]
    For example: 
    \begin{multline*}
      \binom30^2+\binom31^2+\binom32^2+\binom33^2=20=\\
      \binom 30\binom 30\binom 30+\binom 30\binom31\binom 21+\binom 31\binom20\binom20+\binom31\binom 21\binom11+\binom32\binom10\binom10+\binom33\binom00\binom00
    \end{multline*}
    (Hint: you probably want to prove this combinatorially: the left
    side can be thought of as enumerating pairs of subsets of
    $\{1,2,\ldots,n\}$ with a particular property. Can you
    characterize each pair in other ways, and count those
    characterizations?)}

  \answer{For each value $k$, $\binom nk^2$ counts the pairs $(A,B)$
    of subsets of $\{1,2,3,\ldots,n\}$ such that $|A|=|B|=k$. Since we
    allow $k$ to range over all possible values, the left side will
    thus enumerate the pairs of subsets of $\{1,2,3,\ldots,n\}$ where
    $|A|=|B|$.

    On the other hand, the expression on the right side is $\binom
    n\ell\binom{n-\ell}r\binom{n-\ell-r}r$, which we might
    alternatively write as the multinomial $\binom
    n{\ell,r,r,n-\ell-2r}$; it can be thought of as the selection of a
    triple of three \emph{disjoint} subsets $(R,S,T)$ of
    $\{1,\ldots,n\}$ with $|R|=\ell$, $|S|=r$, and $|T|=r$; the
    summation simply guarantees that $R$, $S$, and $T$ take on all
    possible values such that $|R|+|S|+|T|\leq n$, so all we are
    really selecting on the right is three disjoint sets $R$, $S$, and
    $T$ such that $|S|=|T|$.  We now wish to show that this structure
    is fundamentally the same as that on the left side. We may do this
    via a bijection: let $A=R\cup S$ and $B=R\cup T$, or, conversely,
    let $R=A\cap B$, $S=A-B$, and $T=B-A$.

    In summary, we show these two values are identical by showing that
    they enumerate two distinct processes for building equal-size
    subsets of $\{1,2,3,\ldots,n\}$: we could select a size for $A$
    and $B$ and build two subsets of that size, or we could select a
    size for the overlapping and non-overlapping portions, and select
    the overlap, then $A$'s uniquely-held elements, and then $B$'s
    uniquely-held elements.}

\item {\bf (10 points)} \question{Prove combinatorially that for
    positive integers $m$, $w$, and $k$, $\sum_{j=0}^k\binom mj\binom
    w{k-j}=\binom{m+w}k$. (Hint: determine what the right side counts,
    and then divide those objects into $k+1$ classes whose sizes are
    on the left, based on their properties.}

  \answer{The right side of this expression clearly counts the
    possible $k$-element subsets of $\{1,2,3,\ldots,m+w\}$. To acquire
    the left side, let us consider how such a $k$-element subset $S$
    might have its elements divided between the smaller numbers
    $\{1,2,3,\ldots,m\}$ and the larger numbers
    $\{m+1,m+2,\ldots,m+w\}$. Plausibly anywhere between $0$ and $k$
    of the elements might belong to the former set; let's call the
    number of such elements $j$. Then for any specific $j$, we could
    build $S$ by selecting $j$ elements from $\{1,2,3,\ldots,m\}$ in
    any of $\binom mj$ ways, and selecting the remaining $k-j$
    elements from $\{m+1,m+2,\ldots,m+w\}$ in any of $\binom w{k-j}$
    ways. Thus for a fixed $j$ we might build the set $S$ in any of
    $\binom mj\binom w{k-j}$ ways. However, since any value of $j$ is
    possible, we must add up this calculation for each $j$ from $0$ to
    $k$, to get the desired count of $\sum_{j=0}^k\binom mj\binom
    w{k-j}$.}

\item {\bf (10 points)} \question{Suppose that a teacher wishes to
    distribute 25 identical pencils to Ahmed, Barbara, Casper, and
    Dieter such that Ahmed and Dieter receive at least one pencil
    each, Casper receives no more than five pencils, and Barbara
    receives at least four pencils. In how many ways can such a
    distribution be made?}

  \answer{We might pre-emptively assign one pencil to each of Ahmed
    and Dieter and four to Barbara; we now have simply the task of
    freely assigning the remaining 19 pencils to the four students
    giving no more than five to Caspar. Ignoring this last restriction
    for the time being, the balls-and-walls paradigm allows us to
    consider this as the placement of three partitions among 22
    positions which can be achieved in $\binom{22}3$ ways. However, we
    now want to \emph{exclude} from consideration any distribution
    which gives 6 or more pencils to Casper; to count these, we can
    pre-emptively give 6 pencils to Casper and count the ways to
    assign the remaining 13 pencils, and again our balls-and-walls
    paradigm provides a count of $\binom{16}3$. Since this most recent
    calculation is the number of placements to exclude, our final
    count will be $\binom{22}3-\binom{16}3=980$.}

\item {\bf (10 points)} \question{The Catalan number $C_n$ enumerates,
    among other things, the number of ways to nest $n$ pairs of
    parentheses, the number of ways to build a binary tree with $n$
    nodes, the number of Dyck paths from $(0,0)$ to $(0,2n)$, and the
    number of ways to build a binary tree where each node with
    children has 2 children, and which has $n+1$ leaves.

    Show with an \emph{explicit bijection} to one of the structures
    described above, that the triangulations by noncrossing diagonals
    of a convex $(n+2)$-gon are also enumerated by $C_n$. For
    instance, $C_4=14$, and below are the 14 triangulations of a
    hexagon:}
  \begin{center}
    \begin{tikzpicture}[scale=0.6]
      \draw (0:1)--(60:1)--(120:1)--(180:1)--(240:1)--(300:1)--cycle;
      \draw (0:1)--(120:1)--(240:1)--cycle;
    \end{tikzpicture}
    \begin{tikzpicture}[scale=0.6]
      \draw (0:1)--(60:1)--(120:1)--(180:1)--(240:1)--(300:1)--cycle;
      \draw (60:1)--(180:1)--(300:1)--cycle;
    \end{tikzpicture}
    \begin{tikzpicture}[scale=0.6]
      \draw (0:1)--(60:1)--(120:1)--(180:1)--(240:1)--(300:1)--cycle;
      \draw (0:1)--(120:1)--(300:1)--(180:1);
    \end{tikzpicture}
    \begin{tikzpicture}[scale=0.6]
      \draw (0:1)--(60:1)--(120:1)--(180:1)--(240:1)--(300:1)--cycle;
      \draw (60:1)--(180:1)--(0:1)--(240:1);
    \end{tikzpicture}
    \begin{tikzpicture}[scale=0.6]
      \draw (0:1)--(60:1)--(120:1)--(180:1)--(240:1)--(300:1)--cycle;
      \draw (120:1)--(240:1)--(60:1)--(300:1);
    \end{tikzpicture}
    \begin{tikzpicture}[scale=0.6]
      \draw (0:1)--(60:1)--(120:1)--(180:1)--(240:1)--(300:1)--cycle;
      \draw (0:1)--(240:1)--(60:1)--(180:1);
    \end{tikzpicture}
    \begin{tikzpicture}[scale=0.6]
      \draw (0:1)--(60:1)--(120:1)--(180:1)--(240:1)--(300:1)--cycle;
      \draw (60:1)--(300:1)--(120:1)--(240:1);
    \end{tikzpicture}\\
    \begin{tikzpicture}[scale=0.6]
      \draw (0:1)--(60:1)--(120:1)--(180:1)--(240:1)--(300:1)--cycle;
      \draw (120:1)--(0:1)--(180:1)--(300:1);
    \end{tikzpicture}
    \begin{tikzpicture}[scale=0.6]
      \draw (0:1)--(60:1)--(120:1)--(180:1)--(240:1)--(300:1)--cycle;
      \draw (0:1)--(60:1);
      \draw (0:1)--(120:1);
      \draw (0:1)--(180:1);
      \draw (0:1)--(240:1);
      \draw (0:1)--(300:1);
    \end{tikzpicture}
    \begin{tikzpicture}[scale=0.6]
      \draw (0:1)--(60:1)--(120:1)--(180:1)--(240:1)--(300:1)--cycle;
      \draw (60:1)--(0:1);
      \draw (60:1)--(120:1);
      \draw (60:1)--(180:1);
      \draw (60:1)--(240:1);
      \draw (60:1)--(300:1);
    \end{tikzpicture}
    \begin{tikzpicture}[scale=0.6]
      \draw (0:1)--(60:1)--(120:1)--(180:1)--(240:1)--(300:1)--cycle;
      \draw (120:1)--(0:1);
      \draw (120:1)--(60:1);
      \draw (120:1)--(180:1);
      \draw (120:1)--(240:1);
      \draw (120:1)--(300:1);
    \end{tikzpicture}
    \begin{tikzpicture}[scale=0.6]
      \draw (0:1)--(60:1)--(120:1)--(180:1)--(240:1)--(300:1)--cycle;
      \draw (180:1)--(0:1);
      \draw (180:1)--(60:1);
      \draw (180:1)--(120:1);
      \draw (180:1)--(240:1);
      \draw (180:1)--(300:1);
    \end{tikzpicture}
    \begin{tikzpicture}[scale=0.6]
      \draw (0:1)--(60:1)--(120:1)--(180:1)--(240:1)--(300:1)--cycle;
      \draw (240:1)--(0:1);
      \draw (240:1)--(60:1);
      \draw (240:1)--(120:1);
      \draw (240:1)--(180:1);
      \draw (240:1)--(300:1);
    \end{tikzpicture}
    \begin{tikzpicture}[scale=0.6]
      \draw (0:1)--(60:1)--(120:1)--(180:1)--(240:1)--(300:1)--cycle;
      \draw (300:1)--(0:1);
      \draw (300:1)--(60:1);
      \draw (300:1)--(120:1);
      \draw (300:1)--(180:1);
      \draw (300:1)--(240:1);
    \end{tikzpicture}
  \end{center}

  \answer{Several explicit bijections are possible; here I show one of
    the more straightforward ones. For purposes of illustration the
    techniques below will be illustrated with a nonagon and a 7-node
    binary tree.

    Let us choose a nonagon to triangulate in which one edge lies at
    the top; we will call this the ``root edge'' and the triangle
    containing it as the ``root triangle'', which will eventually
    resolve into our root node. The root triangle has two other edges,
    one clockwise from the root edge, and one counterclockwise from
    the root edge; we shall call these the ``right'' and ``left''
    edges respectively. If either edge is on the outside of the
    nonagon we consider it to represent a non-child; either which is
    interior to the nonagon will become the ``parent edge'' of
    whatever other triangle it borders. Now each ``child triangle''
    has a ``parent edge'' and two other edges. Just as with the root
    triangle, we label these two edges with the clockwise one being
    called ``right'' and the counterclockwise one ``left''. Repeating
    this until all triangles are labeled, we see that each triangle
    (except the root) has a parent, and that the triangle is the left
    or right child of that parent. This means we can associate each
    triangle in the triangulation with a single node of a binary
    tree. Below I show how this might work for a specific
    triangulation, labeling the currently-being-processed triangle in
    bold red, and labeling the parent edge, left edge and right edge
    thereof with ``P'', ``L'', and ``R'' respectively. For consistency
    of notation we will call the root edge the ``parent edge'' of the
    root triangle.

    \begin{center}
      \begin{tikzpicture}[scale=0.75]
        \begin{scope}
          \coordinate (v0) at (-10:1.5);
          \coordinate (v1) at (30:1.5);
          \coordinate (v2) at (70:1.5);
          \coordinate (v3) at (110:1.5);
          \coordinate (v4) at (150:1.5);
          \coordinate (v5) at (190:1.5);
          \coordinate (v6) at (230:1.5);
          \coordinate (v7) at (270:1.5);
          \coordinate (v8) at (310:1.5);
          
          \draw (v0)--(v1)--(v2)--(v3)--(v4)--
          (v5)--(v6)--(v7)--(v8)--cycle;
          \draw (v7)--(v4);
          \draw (v2)--(v4);
          \draw (v5)--(v7);
          \draw (v2)--(v8);
          \draw (v1)--(v8);
          \draw (v4)--(v8);
          
          \draw[red,thick] (v2)--(v3)--(v4)--cycle;
          \draw ($(v2)!.5!(v3)$) node[rectangle,draw=red,inner sep=0.5mm,fill=white] {\tiny P};
          \draw ($(v3)!.5!(v4)$) node[rectangle,draw=red,inner sep=0.5mm,fill=white] {\tiny L};
          \draw ($(v2)!.5!(v4)$) node[rectangle,draw=red,inner sep=0.5mm,fill=white] {\tiny R};
          \fill[red] ($(v2)!.5!(v3)!1/3!(v4)$) circle (0.05);
          \fill[red] (0,-1.75) circle (0.1);
        \end{scope}

        \begin{scope}[xshift=3.2cm]
          \coordinate (v0) at (-10:1.5);
          \coordinate (v1) at (30:1.5);
          \coordinate (v2) at (70:1.5);
          \coordinate (v3) at (110:1.5);
          \coordinate (v4) at (150:1.5);
          \coordinate (v5) at (190:1.5);
          \coordinate (v6) at (230:1.5);
          \coordinate (v7) at (270:1.5);
          \coordinate (v8) at (310:1.5);
          
          \draw (v0)--(v1)--(v2)--(v3)--(v4)--
          (v5)--(v6)--(v7)--(v8)--cycle;
          \draw (v7)--(v4);
          \draw (v2)--(v4);
          \draw (v5)--(v7);
          \draw (v2)--(v8);
          \draw (v1)--(v8);
          \draw (v4)--(v8);
          \draw[red,thick] (v2)--(v4)--(v8)--cycle;
          \draw ($(v2)!.5!(v4)$) node[rectangle,draw=red,inner sep=0.5mm,fill=white] {\tiny P};
          \draw ($(v4)!.5!(v8)$) node[rectangle,draw=red,inner sep=0.5mm,fill=white] {\tiny L};
          \draw ($(v2)!.5!(v8)$) node[rectangle,draw=red,inner sep=0.5mm,fill=white] {\tiny R};
          \fill[black] ($(v2)!.5!(v3)!1/3!(v4)$) circle (0.05);
          \fill[black] (0,-1.75) circle (0.1);
          \draw[dashed] ($(v2)!.5!(v3)!1/3!(v4)$)--($(v2)!.5!(v4)!1/3!(v8)$);
          \draw (0,-1.75) -- (0.25,-2.25);
          \fill[red] ($(v2)!.5!(v4)!1/3!(v8)$) circle (0.05);
          \fill[red] (0.25,-2.25) circle (0.1);
        \end{scope}

        \begin{scope}[xshift=6.4cm]
          \coordinate (v0) at (-10:1.5);
          \coordinate (v1) at (30:1.5);
          \coordinate (v2) at (70:1.5);
          \coordinate (v3) at (110:1.5);
          \coordinate (v4) at (150:1.5);
          \coordinate (v5) at (190:1.5);
          \coordinate (v6) at (230:1.5);
          \coordinate (v7) at (270:1.5);
          \coordinate (v8) at (310:1.5);
          
          \draw (v0)--(v1)--(v2)--(v3)--(v4)--
          (v5)--(v6)--(v7)--(v8)--cycle;
          \draw (v7)--(v4);
          \draw (v2)--(v4);
          \draw (v5)--(v7);
          \draw (v2)--(v8);
          \draw (v1)--(v8);
          \draw (v4)--(v8);
          \draw[red,thick] (v7)--(v4)--(v8)--cycle;
          \draw ($(v4)!.5!(v8)$) node[rectangle,draw=red,inner sep=0.5mm,fill=white] {\tiny P};
          \draw ($(v4)!.5!(v7)$) node[rectangle,draw=red,inner sep=0.5mm,fill=white] {\tiny L};
          \draw ($(v7)!.5!(v8)$) node[rectangle,draw=red,inner sep=0.5mm,fill=white] {\tiny R};
          \fill[black] ($(v2)!.5!(v3)!1/3!(v4)$) circle (0.05);
          \fill[black] (0,-1.75) circle (0.1);
          \draw[dashed] ($(v2)!.5!(v3)!1/3!(v4)$)--($(v2)!.5!(v4)!1/3!(v8)$);
          \draw (0,-1.75) -- (0.25,-2.25);
          \fill[black] ($(v2)!.5!(v4)!1/3!(v8)$) circle (0.05);
          \fill[black] (0.25,-2.25) circle (0.1);
          \draw[dashed] ($(v2)!.5!(v4)!1/3!(v8)$)--($(v7)!.5!(v4)!1/3!(v8)$);
          \draw (0.25,-2.25) -- (0,-2.75);
          \fill[red] ($(v7)!.5!(v4)!1/3!(v8)$) circle (0.05);
          \fill[red] (0,-2.75) circle (0.1);
        \end{scope}

        \begin{scope}[xshift=9.6cm]
          \coordinate (v0) at (-10:1.5);
          \coordinate (v1) at (30:1.5);
          \coordinate (v2) at (70:1.5);
          \coordinate (v3) at (110:1.5);
          \coordinate (v4) at (150:1.5);
          \coordinate (v5) at (190:1.5);
          \coordinate (v6) at (230:1.5);
          \coordinate (v7) at (270:1.5);
          \coordinate (v8) at (310:1.5);
          
          \draw (v0)--(v1)--(v2)--(v3)--(v4)--
          (v5)--(v6)--(v7)--(v8)--cycle;
          \draw (v7)--(v4);
          \draw (v2)--(v4);
          \draw (v5)--(v7);
          \draw (v2)--(v8);
          \draw (v1)--(v8);
          \draw (v4)--(v8);
          \draw[red,thick] (v7)--(v4)--(v5)--cycle;
          \draw ($(v7)!.5!(v4)$) node[rectangle,draw=red,inner sep=0.5mm,fill=white] {\tiny P};
          \draw ($(v4)!.5!(v5)$) node[rectangle,draw=red,inner sep=0.5mm,fill=white] {\tiny L};
          \draw ($(v5)!.5!(v7)$) node[rectangle,draw=red,inner sep=0.5mm,fill=white] {\tiny R};
          \fill[black] ($(v2)!.5!(v3)!1/3!(v4)$) circle (0.05);
          \fill[black] (0,-1.75) circle (0.1);
          \draw[dashed] ($(v2)!.5!(v3)!1/3!(v4)$)--($(v2)!.5!(v4)!1/3!(v8)$);
          \draw (0,-1.75) -- (0.25,-2.25);
          \fill[black] ($(v2)!.5!(v4)!1/3!(v8)$) circle (0.05);
          \fill[black] (0.25,-2.25) circle (0.1);
          \draw[dashed] ($(v2)!.5!(v4)!1/3!(v8)$)--($(v7)!.5!(v4)!1/3!(v8)$);
          \draw (0.25,-2.25) -- (0,-2.75);
          \fill[black] ($(v7)!.5!(v4)!1/3!(v8)$) circle (0.05);
          \fill[black] (0,-2.75) circle (0.1);
          \draw[dashed] ($(v7)!.5!(v4)!1/3!(v8)$)--($(v7)!.5!(v4)!1/3!(v5)$);
          \draw (0,-2.75) -- (-0.25,-3.25);
          \fill[red] ($(v7)!.5!(v4)!1/3!(v5)$) circle (0.05);
          \fill[red] (-0.25,-3.25) circle (0.1);
        \end{scope}

        \begin{scope}[xshift=12.8cm]
          \coordinate (v0) at (-10:1.5);
          \coordinate (v1) at (30:1.5);
          \coordinate (v2) at (70:1.5);
          \coordinate (v3) at (110:1.5);
          \coordinate (v4) at (150:1.5);
          \coordinate (v5) at (190:1.5);
          \coordinate (v6) at (230:1.5);
          \coordinate (v7) at (270:1.5);
          \coordinate (v8) at (310:1.5);
          
          \draw (v0)--(v1)--(v2)--(v3)--(v4)--
          (v5)--(v6)--(v7)--(v8)--cycle;
          \draw (v7)--(v4);
          \draw (v2)--(v4);
          \draw (v5)--(v7);
          \draw (v2)--(v8);
          \draw (v1)--(v8);
          \draw (v4)--(v8);
          \draw[red,thick] (v7)--(v6)--(v5)--cycle;
          \draw ($(v7)!.5!(v5)$) node[rectangle,draw=red,inner sep=0.5mm,fill=white] {\tiny P};
          \draw ($(v5)!.5!(v6)$) node[rectangle,draw=red,inner sep=0.5mm,fill=white] {\tiny L};
          \draw ($(v6)!.5!(v7)$) node[rectangle,draw=red,inner sep=0.5mm,fill=white] {\tiny R};
          \fill[black] ($(v2)!.5!(v3)!1/3!(v4)$) circle (0.05);
          \fill[black] (0,-1.75) circle (0.1);
          \draw[dashed] ($(v2)!.5!(v3)!1/3!(v4)$)--($(v2)!.5!(v4)!1/3!(v8)$);
          \draw (0,-1.75) -- (0.25,-2.25);
          \fill[black] ($(v2)!.5!(v4)!1/3!(v8)$) circle (0.05);
          \fill[black] (0.25,-2.25) circle (0.1);
          \draw[dashed] ($(v2)!.5!(v4)!1/3!(v8)$)--($(v7)!.5!(v4)!1/3!(v8)$);
          \draw (0.25,-2.25) -- (0,-2.75);
          \fill[black] ($(v7)!.5!(v4)!1/3!(v8)$) circle (0.05);
          \fill[black] (0,-2.75) circle (0.1);
          \draw[dashed] ($(v7)!.5!(v4)!1/3!(v8)$)--($(v7)!.5!(v4)!1/3!(v5)$);
          \draw (0,-2.75) -- (-0.25,-3.25);
          \fill[black] ($(v7)!.5!(v4)!1/3!(v5)$) circle (0.05);
          \fill[black] (-0.25,-3.25) circle (0.1);
          \draw[dashed] ($(v7)!.5!(v4)!1/3!(v5)$)--($(v7)!.5!(v6)!1/3!(v5)$);
          \draw (-0.25,-3.25) -- (0,-3.75);
          \fill[red] ($(v7)!.5!(v6)!1/3!(v5)$) circle (0.05);
          \fill[red] (0,-3.75) circle (0.1);
        \end{scope}

        \begin{scope}[xshift=16cm]
          \coordinate (v0) at (-10:1.5);
          \coordinate (v1) at (30:1.5);
          \coordinate (v2) at (70:1.5);
          \coordinate (v3) at (110:1.5);
          \coordinate (v4) at (150:1.5);
          \coordinate (v5) at (190:1.5);
          \coordinate (v6) at (230:1.5);
          \coordinate (v7) at (270:1.5);
          \coordinate (v8) at (310:1.5);
          
          \draw (v0)--(v1)--(v2)--(v3)--(v4)--
          (v5)--(v6)--(v7)--(v8)--cycle;
          \draw (v7)--(v4);
          \draw (v2)--(v4);
          \draw (v5)--(v7);
          \draw (v2)--(v8);
          \draw (v1)--(v8);
          \draw (v4)--(v8);
          \draw[red,thick] (v8)--(v1)--(v2)--cycle;
          \draw ($(v8)!.5!(v2)$) node[rectangle,draw=red,inner sep=0.5mm,fill=white] {\tiny P};
          \draw ($(v8)!.5!(v1)$) node[rectangle,draw=red,inner sep=0.5mm,fill=white] {\tiny L};
          \draw ($(v2)!.5!(v1)$) node[rectangle,draw=red,inner sep=0.5mm,fill=white] {\tiny R};
          \fill[black] ($(v2)!.5!(v3)!1/3!(v4)$) circle (0.05);
          \fill[black] (0,-1.75) circle (0.1);
          \draw[dashed] ($(v2)!.5!(v3)!1/3!(v4)$)--($(v2)!.5!(v4)!1/3!(v8)$);
          \draw (0,-1.75) -- (0.25,-2.25);
          \fill[black] ($(v2)!.5!(v4)!1/3!(v8)$) circle (0.05);
          \fill[black] (0.25,-2.25) circle (0.1);
          \draw[dashed] ($(v2)!.5!(v4)!1/3!(v8)$)--($(v7)!.5!(v4)!1/3!(v8)$);
          \draw (0.25,-2.25) -- (0,-2.75);
          \fill[black] ($(v7)!.5!(v4)!1/3!(v8)$) circle (0.05);
          \fill[black] (0,-2.75) circle (0.1);
          \draw[dashed] ($(v7)!.5!(v4)!1/3!(v8)$)--($(v7)!.5!(v4)!1/3!(v5)$);
          \draw (0,-2.75) -- (-0.25,-3.25);
          \fill[black] ($(v7)!.5!(v4)!1/3!(v5)$) circle (0.05);
          \fill[black] (-0.25,-3.25) circle (0.1);
          \draw[dashed] ($(v7)!.5!(v4)!1/3!(v5)$)--($(v7)!.5!(v6)!1/3!(v5)$);
          \draw (-0.25,-3.25) -- (0,-3.75);
          \fill[black] ($(v7)!.5!(v6)!1/3!(v5)$) circle (0.05);
          \fill[black] (0,-3.75) circle (0.1);
          \draw[dashed] ($(v2)!.5!(v4)!1/3!(v8)$)--($(v2)!.5!(v1)!1/3!(v8)$);
          \draw (0.25,-2.25) -- (0.5,-2.75);
          \fill[red] ($(v2)!.5!(v1)!1/3!(v8)$) circle (0.05);
          \fill[red] (0.5,-2.75) circle (0.1);
        \end{scope}

        \begin{scope}[xshift=19.2cm]
          \coordinate (v0) at (-10:1.5);
          \coordinate (v1) at (30:1.5);
          \coordinate (v2) at (70:1.5);
          \coordinate (v3) at (110:1.5);
          \coordinate (v4) at (150:1.5);
          \coordinate (v5) at (190:1.5);
          \coordinate (v6) at (230:1.5);
          \coordinate (v7) at (270:1.5);
          \coordinate (v8) at (310:1.5);
          
          \draw (v0)--(v1)--(v2)--(v3)--(v4)--
          (v5)--(v6)--(v7)--(v8)--cycle;
          \draw (v7)--(v4);
          \draw (v2)--(v4);
          \draw (v5)--(v7);
          \draw (v2)--(v8);
          \draw (v1)--(v8);
          \draw (v4)--(v8);
          \draw[red,thick] (v8)--(v1)--(v0)--cycle;
          \draw ($(v8)!.5!(v1)$) node[rectangle,draw=red,inner sep=0.5mm,fill=white] {\tiny P};
          \draw ($(v8)!.5!(v0)$) node[rectangle,draw=red,inner sep=0.5mm,fill=white] {\tiny L};
          \draw ($(v1)!.5!(v0)$) node[rectangle,draw=red,inner sep=0.5mm,fill=white] {\tiny R};
          \fill[black] ($(v2)!.5!(v3)!1/3!(v4)$) circle (0.05);
          \fill[black] (0,-1.75) circle (0.1);
          \draw[dashed] ($(v2)!.5!(v3)!1/3!(v4)$)--($(v2)!.5!(v4)!1/3!(v8)$);
          \draw (0,-1.75) -- (0.25,-2.25);
          \fill[black] ($(v2)!.5!(v4)!1/3!(v8)$) circle (0.05);
          \fill[black] (0.25,-2.25) circle (0.1);
          \draw[dashed] ($(v2)!.5!(v4)!1/3!(v8)$)--($(v7)!.5!(v4)!1/3!(v8)$);
          \draw (0.25,-2.25) -- (0,-2.75);
          \fill[black] ($(v7)!.5!(v4)!1/3!(v8)$) circle (0.05);
          \fill[black] (0,-2.75) circle (0.1);
          \draw[dashed] ($(v7)!.5!(v4)!1/3!(v8)$)--($(v7)!.5!(v4)!1/3!(v5)$);
          \draw (0,-2.75) -- (-0.25,-3.25);
          \fill[black] ($(v7)!.5!(v4)!1/3!(v5)$) circle (0.05);
          \fill[black] (-0.25,-3.25) circle (0.1);
          \draw[dashed] ($(v7)!.5!(v4)!1/3!(v5)$)--($(v7)!.5!(v6)!1/3!(v5)$);
          \draw (-0.25,-3.25) -- (0,-3.75);
          \fill[black] ($(v7)!.5!(v6)!1/3!(v5)$) circle (0.05);
          \fill[black] (0,-3.75) circle (0.1);
          \draw[dashed] ($(v2)!.5!(v4)!1/3!(v8)$)--($(v2)!.5!(v1)!1/3!(v8)$);
          \draw (0.25,-2.25) -- (0.5,-2.75);
          \fill[black] ($(v2)!.5!(v1)!1/3!(v8)$) circle (0.05);
          \fill[black] (0.5,-2.75) circle (0.1);
          \draw[dashed] ($(v2)!.5!(v1)!1/3!(v8)$)--($(v0)!.5!(v1)!1/3!(v8)$);
          \draw (0.5,-2.75) -- (0.25,-3.25);
          \fill[red] ($(v0)!.5!(v1)!1/3!(v8)$) circle (0.05);
          \fill[red] (0.25,-3.25) circle (0.1);
        \end{scope}
      \end{tikzpicture}
    \end{center}

    Conversely, starting with a tree with $\ell$ children on the left
    and $r$ children on the right, we can iteratively build triangles,
    starting from our parent edge, which have an $(\ell+2)$-gon on the
    left and an $(r+2)$-gon on the right \emph{relative to our parent
      edge}, as such:

    \begin{center}
      \begin{tikzpicture}[scale=0.75]
        \begin{scope}
          \coordinate (v0) at (-10:1.5);
          \coordinate (v1) at (30:1.5);
          \coordinate (v2) at (70:1.5);
          \coordinate (v3) at (110:1.5);
          \coordinate (v4) at (150:1.5);
          \coordinate (v5) at (190:1.5);
          \coordinate (v6) at (230:1.5);
          \coordinate (v7) at (270:1.5);
          \coordinate (v8) at (310:1.5);
          \draw (v0)--(v1)--(v2)--(v3)--(v4)--
          (v5)--(v6)--(v7)--(v8)--cycle;

          \draw[red,thick] (v0)--(v1)--(v2)--(v3)--(v4)--
          (v5)--(v6)--(v7)--(v8)--cycle;
          \draw ($(v2)!.5!(v3)$) node[rectangle,draw=red,inner sep=0.5mm,fill=white] {\tiny P};
          \draw[red] (0,1) -- ++ (-0.25,-0.5);
          \draw[red] (0,1) -- ++ (0.25,-0.5);
          \draw (-0.25,0.5) -- ++ (-0.25,-0.5);
          \draw (0.25,0.5) -- ++ (-0.25,-0.5);
          \draw (0.25,0.5) -- ++ (0.25,-0.5);
          \draw (-0.5,0) -- ++ (0.25,-0.5);
          \fill[red] (0,1) circle (0.1);
          \fill (-0.25,0.5) circle (0.1);
          \fill (0.25,0.5) circle (0.1);
          \fill (-0.5,0) circle (0.1);
          \fill (0,0) circle (0.1);
          \fill (0.5,0) circle (0.1);
          \fill (-0.25,-0.5) circle (0.1);
        \end{scope}

        \begin{scope}[xshift=3.2cm]
          \coordinate (v0) at (-10:1.5);
          \coordinate (v1) at (30:1.5);
          \coordinate (v2) at (70:1.5);
          \coordinate (v3) at (110:1.5);
          \coordinate (v4) at (150:1.5);
          \coordinate (v5) at (190:1.5);
          \coordinate (v6) at (230:1.5);
          \coordinate (v7) at (270:1.5);
          \coordinate (v8) at (310:1.5);
          \draw (v0)--(v1)--(v2)--(v3)--(v4)--
          (v5)--(v6)--(v7)--(v8)--cycle;

          \draw (v2)--(v7);
          \draw (v3)--(v7);

          \draw[red,thick] (v3)--(v4)--(v5)--(v6)--(v7)--cycle;
          \draw ($(v3)!.5!(v7)$) node[rectangle,draw=red,inner sep=0.5mm,fill=white] {\tiny P};
          \draw[red] (-0.75,0.5) -- ++ (-0.25,-0.5);
          \draw (-1,0) -- ++ (0.25,-0.5);

          \draw (0.75,0.5) -- ++ (-0.25,-0.5);
          \draw (0.75,0.5) -- ++ (0.25,-0.5);

          \fill[red] (-0.75,0.5) circle (0.1);
          \fill (-1,0) circle (0.1);
          \fill (-0.75,-0.5) circle (0.1);

          \fill (0.75,0.5) circle (0.1);
          \fill (0.5,0) circle (0.1);
          \fill (1,0) circle (0.1);

        \end{scope}

        \begin{scope}[xshift=6.4cm]
          \coordinate (v0) at (-10:1.5);
          \coordinate (v1) at (30:1.5);
          \coordinate (v2) at (70:1.5);
          \coordinate (v3) at (110:1.5);
          \coordinate (v4) at (150:1.5);
          \coordinate (v5) at (190:1.5);
          \coordinate (v6) at (230:1.5);
          \coordinate (v7) at (270:1.5);
          \coordinate (v8) at (310:1.5);
          \draw (v0)--(v1)--(v2)--(v3)--(v4)--
          (v5)--(v6)--(v7)--(v8)--cycle;

          \draw (v2)--(v7);
          \draw (v3)--(v7);
          \draw (v3)--(v6);

          \draw[red,thick] (v3)--(v4)--(v5)--(v6)--cycle;
          \draw ($(v3)!.5!(v6)$) node[rectangle,draw=red,inner sep=0.5mm,fill=white] {\tiny P};
          \draw[red] (-1.25,0.25) -- ++ (0.25,-0.5);

          \draw (0.75,0.5) -- ++ (-0.25,-0.5);
          \draw (0.75,0.5) -- ++ (0.25,-0.5);

          \fill[red] (-1.25,0.25) circle (0.1);
          \fill (-1,-0.25) circle (0.1);

          \fill (0.75,0.5) circle (0.1);
          \fill (0.5,0) circle (0.1);
          \fill (1,0) circle (0.1);

        \end{scope}

        \begin{scope}[xshift=9.6cm]
          \coordinate (v0) at (-10:1.5);
          \coordinate (v1) at (30:1.5);
          \coordinate (v2) at (70:1.5);
          \coordinate (v3) at (110:1.5);
          \coordinate (v4) at (150:1.5);
          \coordinate (v5) at (190:1.5);
          \coordinate (v6) at (230:1.5);
          \coordinate (v7) at (270:1.5);
          \coordinate (v8) at (310:1.5);
          \draw (v0)--(v1)--(v2)--(v3)--(v4)--
          (v5)--(v6)--(v7)--(v8)--cycle;

          \draw (v2)--(v7);
          \draw (v3)--(v7);
          \draw (v3)--(v6);
          \draw (v4)--(v6);

          \draw[red,thick] (v0)--(v1)--(v2)--(v7)--(v8)--cycle;
          \draw ($(v2)!.5!(v7)$) node[rectangle,draw=red,inner sep=0.5mm,fill=white] {\tiny P};
          \draw[red] (1,0.5) -- ++ (-0.25,-0.5);
          \draw[red] (1,0.5) -- ++ (0.25,-0.5);

          \fill[red] (1,0.5) circle (0.1);
          \fill (0.75,0) circle (0.1);
          \fill (1.25,0) circle (0.1);
        \end{scope}

        \begin{scope}[xshift=12.8cm]
          \coordinate (v0) at (-10:1.5);
          \coordinate (v1) at (30:1.5);
          \coordinate (v2) at (70:1.5);
          \coordinate (v3) at (110:1.5);
          \coordinate (v4) at (150:1.5);
          \coordinate (v5) at (190:1.5);
          \coordinate (v6) at (230:1.5);
          \coordinate (v7) at (270:1.5);
          \coordinate (v8) at (310:1.5);
          \draw (v0)--(v1)--(v2)--(v3)--(v4)--
          (v5)--(v6)--(v7)--(v8)--cycle;

          \draw (v2)--(v7);
          \draw (v3)--(v7);
          \draw (v3)--(v6);
          \draw (v4)--(v6);
          \draw (v0)--(v2);
          \draw (v0)--(v7);
        \end{scope}
      \end{tikzpicture}
    \end{center}


}

\end{enumerate}

\vfill
\begin{center}
  \fbox{
    \begin{minipage}{6in}
      \begin{cjhebrew}
        /sty 'bnyM bwnwt /sny btyM; /sl/s 'bnyM bwnwt /s/sh btyM; 'rb` 'bnyM b
        wnwt 'rb`h w`/sryM btyM; .hm/s 'bnyM bwnwt m'h w`/sryM btyM; /s/s 'bnyM 
bwnwt /s
        b` m'wt w`/sryM btyM; /sb` 'bnyM bwnwt .hm/st 'lpyM w'rb`yM btyM; mk'N w
'ylK .s'
        w.h/swb mh /s'yN hph ykwl ldbr w'yN h'wzN ykwlh l/smw`
      \end{cjhebrew}\\
      \phantom0\hfill---\cjRL{spr hy.syrh pr.S d${}'$ m/snh .t${}''$z}

      \answer{[Two stones (or letters) build two houses (or words),
        three stones build six houses, four stones build twenty-four
        houses, five stones build one hundred twenty houses, six
        stones build seven and twenty houses, seven stones build five
        thousand forty houses; thenceforth are numbers which the mouth
        can not speak and the ear can not hear.]\\
        \phantom0\hfill---Sefer Yetzira, Chapter 4, Verse 16}
    \end{minipage}
  }
\end{center}

\end{document}
