\documentclass[12pt]{amsart}
\usepackage{amsmath} \usepackage{amsthm} \usepackage{amstext}
\usepackage{amsfonts} \usepackage{graphicx} \usepackage{latexsym}
\usepackage{epsfig}
% \input epsf
\def\p{\partial} \def\O{\Omega} \def\c{\cal} \def\a{\alpha}
\def\r{\rho} \def\e{\epsilon} \def\g{\gamma} \def\d{\delta}
\def\D{\Delta} \def\t{\theta} \def\T{\Theta} \def\N{\nabla}
\def\L{\Lambda} \def\l{\lambda} \def\m{\mu} \def\f{\frac}
\def\dis{\displaystyle} \def\s{\sigma}
\newcommand{\lx}{\left} \newcommand{\rx}{\right}
\setlength{\parindent}{0in} \setlength{\parskip}{\baselineskip}
\setlength{\textheight}{9.0in} \setlength{\textwidth}{6.5in}
\setlength{\topmargin}{0.0in} \setlength{\evensidemargin}{0in}
\setlength{\oddsidemargin}{0in}

\begin{document} %(
\baselineskip 24pt

\title{Problem Set 08}
% YOUR NAME GOES HERE under Author
\author{Your Name}
\maketitle

{\bf NOTE}: This is due Wednesday, November 23rd, at 4PM.  You may
either turn it in in class on Tuesday, or submit it via email
(marc@coral-lab.org).  If you email it to me, I must receive it before
4PM Wednesday (at which point I'll be posting the answers online, and
leaving to eat turkey).  For the email submissions, I prefer pdf, but
if you can't figure out how to make pdf, I'll accept Word docs, rtf,
LaTeX source, and plain old text.  (If there's another format that you
plan to use that I don't have listed, let me know.)

\begin{enumerate} %(

\item Kompleck City is a square 9 blocks on a side.  On the northeast
corner is Vlad Urr's Royal Shack, and on the southwest corner is The
Great Library of Kompleck City.  There are 21 streets in Kompleck
City.  These are all one-way streets.  One of the streets, called
``The Zim Bob Way'', goes underground from Count Urr's Royal Shack to
The Great Library.  The remaining 20 streets are arranged in a 10 by
10 grid. 10 of these streets (Ave.\ $X_0$ through Ave.\ $X_9$) go from
south to north, and 10 (Ave.\ $Y_0$ through Ave.\ $Y_9$) go from west
to east.  For every day of his reign, Count Urr goes to the Royal
Library (along The Zim Bob Way), then returns along a different path
to survey his realm.

(An example path would be where Count Urr takes Zim Bob Way to The
Great Library (at the intersection of $X_0$ and $Y_0$), then Ave.\
$X_0$ to Ave.\ $Y_1$, then $Y_1$ all the way to $X_3$, then $X_3$ to
$Y_9$, then $Y_9$ back to his Shack at the intersection of $X_9$ and
$Y_9$.)

\begin{enumerate} %( 
\item If Count Urr decides to represent a map of Kompleck City as a
graph, how many nodes and how many edges should that graph have?
(Hint, were Kompleck City 1 block on a side, 2 by 2, or 3 by 3, the
number of edges and nodes would be 5 and 4, 13 and 9, and 25 and 16,
respectively.)

% Answer below this line.

\item How long must Count Urr's reign last if he is to take every
possible path through his realm? (Hint, you might want to try this on
a smaller grid first.  For example, the number of paths, were Kompleck
City 1 by 1, 2 by 2, and 3 by 3, would be 2, 6, and 20, respectively.)

% Answer below this line.

\end{enumerate} %)

\item A {\em undirected hyperedge} is like an ordinary undirected 
edge except it may be between\footnote{Grammatically and
etymologically, I should write ``among'', since between is specific to
2 things.} any number of nodes (well, any number $\geq 2$).  {\em
Undirected hypergraphs} are a superset of regular undirected graphs
that may contain hyper-edges (so all undirected graphs are
hypergraphs).  For example, I can have a graph that has 4 nodes: $A$,
$B$, $C$, and $D$, and the following hyperedges:
\begin{itemize} %(
\item $\lx\{A, B\rx\}$ (This is just a regular undirected edge between
$A$ and $B$)
\item $\lx\{C, D\rx\}$ (Another regular edge between $C$ and $D$)
\item $\lx\{A, C, D\rx\}$ (A hyperedge among (``bethreen''?) $A$, $C$,
and $D$.  Note that, since this is undirected, this is the same as the
hyperedge $\lx\{C, D, A\rx\}$.)
\item $\lx\{A, B, C, D\rx\}$ (A hyperedge befourn $A$, $B$, $C$,
and $D$.)
\end{itemize} %)

\begin{enumerate} %( 
\item How many plain\footnote{By ``plain'' I mean without self loops
or multiple edges.  The hyperedges $\lx\{A, B, C\rx\}$ and $\lx\{A,
B\rx\}$ wouldn't count as multiple edges.} undirected hypergraphs are
there that have:
\begin{enumerate} %( 
\item  2 nodes: ($A$ and $B$)

% Answer below this line.

\item  3 nodes: ($A$, $B$, and $C$)

% Answer below this line.

\item  4 nodes: ($A$, $B$, $C$, and $D$)

% Answer below this line.

\end{enumerate} %)

\item  Write a general expression for the number of plain undirected
hypergraphs that have $n$ nodes.  (Hint, you may use the $\sum$
operator, but not ellipses ``$\cdots$''.)

% Answer below this line.

\item  BONUS: Write a {\em closed form} general expression for the
number of plain undirected hypergraphs that have $n$ nodes.  (You can
use this answer here for part b too.)

% Answer below this line.

\end{enumerate} %)

\end{enumerate} %)
\end{document} %)