       %prepared in LaTeX   
   
   
	\hfuzz = 100pt   
        \renewcommand{\b}{\bullet}
        \newcommand{\hf}{$\frac{1}{2}$}
        \newcommand{\third}{\frac{1}{3}}
        \newcommand{\minustwothirds}{-\frac{2}{3}}
        \newcommand{\fourthirds}{\frac{4}{3}}
        \newcommand{\ISpin}{{\rm ISpin}}   
        \newcommand{\End}{{\rm End}}
        \newcommand\F{{\bf F}}   
        \newcommand\G{{\bf G}}   
        \newcommand\HH{{\bf H}}   
        \newcommand\Z{{\mathbb Z}}   
	\newcommand\R{{\mathbb R}}   
	\newcommand\C{{\mathbb C}}   
        \renewcommand\H{{\mathbb H}}   
        \newcommand\K{{\mathbb K}} 
	\renewcommand\O{{\mathbb O}}   
        \newcommand\RP{{\mathbb {RP}}}   
        \newcommand\CP{{\mathbb {CP}}}   
        \newcommand\HP{{\mathbb {HP}}}   
        \newcommand\KP{{\mathbb {KP}}}   
        \newcommand\OP{{\mathbb {OP}}}   
        \renewcommand\P{{\mathbb P}}   
   
        \newcommand{\Cliff}{{\rm Cliff}}   
        \newcommand{\J}{{\rm J}} 
        \newcommand{\M}{{\rm M}}
  
	\renewcommand\S{{\rm S}}      
        \newcommand{\OO}{{\rm O}}   
	\newcommand{\SO}{{\rm SO}}   
	\newcommand{\SL}{{\rm SL}}   
        \newcommand{\PSL}{{\rm PSL}}   
	\newcommand{\SU}{{\rm SU}}   
        \newcommand{\Sp}{{\rm Sp}}
        \newcommand{\Spin}{{\rm Spin}}   
        \newcommand{\Pin}{{\rm Pin}}   
	\newcommand{\U}{{\rm U}}   
	\newcommand{\E}{{\rm E}}   
	\newcommand{\so}{{\mathfrak {so}}}   
	\newcommand{\Sl}{{\mathfrak {sl}}}   
	\newcommand{\symp}{{\mathfrak {sp}}}   
	\renewcommand{\u}{{\mathfrak {u}}}   
	\newcommand{\e}{{\mathfrak {e}}}   
	\newcommand{\f}{{\mathfrak {f}}}   
	\newcommand{\g}{{\mathfrak {g}}}   
	\newcommand{\su}{{\mathfrak {su}}}   
        \renewcommand{\a}{{\mathfrak {a}}}   
        \newcommand{\sa}{{\mathfrak {sa}}}   
        \newcommand{\h}{{\mathfrak {h}}}   
        \newcommand{\sh}{{\mathfrak {sh}}}   
        \newcommand{\coll}{{\mathfrak {coll}}}   
        \newcommand{\isom}{{\mathfrak {isom}}}   
        \newcommand{\Isom}{{\rm Isom}} 
        \newcommand{\Der}{{\mathfrak {der}}}   
        \newcommand{\Tri}{{\mathfrak {tri}}}  

   
	\newcommand{\et}{\hspace{-0.08in}{\bf .}\hspace{0.1in}}   
        \newcommand{\DOT}{\hspace{-0.08in}{\bf .}\hspace{0.1in}}   
 	\newcommand{\BOX}{\hbox {$\sqcap$ \kern -1em $\sqcup$}}   
	\newcommand{\qed}{\hskip 3em \hbox{\BOX} \vskip 2ex}   
   
        \renewcommand{\Re}{{\rm Re}}   
        \renewcommand{\Im}{{\rm Im}}   
	\newcommand{\Hom}{{\rm hom}}   
        \newcommand{\Aut}{{\rm Aut}}   
	\newcommand{\Inv}{{\rm Inv}}   
	\newcommand{\tensor}{\otimes}   
        \newcommand{\iso}{\cong}   
        \newcommand{\implies}{\Longrightarrow}   
        \newcommand{\impliedby}{\Longleftarrow}   
   
	\newcommand{\be}{\begin{equation}}   
        \newcommand{\ee}{\end{equation}}   
        \newcommand{\ba}{\begin{eqnarray}}   
        \newcommand{\ea}{\end{eqnarray}}   
        \newcommand{\ban}{\begin{eqnarray*}}   
        \newcommand{\ean}{\end{eqnarray*}}   
  
        \newcommand{\ad}{{\rm ad}}   
	\newcommand{\Cob}{{\rm Cob}}   
	\newcommand{\Vect}{{\rm Vect}}   
	\newcommand{\Hilb}{{\rm Hilb}}   
        \newcommand{\maps}{\colon}   
	\newcommand{\tr}{{\rm tr}}   
	\newcommand{\rank}{{\rm rank}}   
	\newcommand{\id}{{\rm id}}   
	\newcommand{\Fun}{{\rm Fun}}   
	\newcommand{\Ad}{{\rm Ad}}   
	\newcommand{\om}{\omega}   
	\newcommand{\eps}{\epsilon}  
 
	\newtheorem{thm}{Theorem}   
	\newtheorem{prop}{Proposition}   
	\newtheorem{lemma}{Lemma}   
	\newtheorem{corollary}{Corollary}   
	\newtheorem{ex}{Example}   
 
\documentclass{article} 
\usepackage{amsfonts,amssymb}
%\usepackage{latexsym}

	\textwidth 6in   
	\textheight 8.5in	\evensidemargin .25in   
	\oddsidemargin .25in   
	\topmargin .25in   
	\headsep 0in   
	\headheight 0in   
	\footskip .5in   
%If you want single spaced copy, delete the next two lines.   
%	\parskip 1.75\parskip plus 3pt minus 1pt   
%	\renewcommand{\baselinestretch}{1.5}   
	\pagestyle{plain}   
	\pagenumbering{none}   
	\begin{document}   
 
	\begin{center}   
	{\bf One-bonacci, Two-bonacci, Three-bonacci, Four...\\}   
	{\small John\ C.\ Baez, December 12, 2003\\}   
	\vspace{0.3cm}   
        \end{center}

\noindent
{\it 
Just as the $n$th Fibonacci number counts the number
of ways to take a totally ordered $n$-element set and chop it into 
blocks (substrings) of length 1 or 2, the $n$th {\bf Tribonacci 
number}, $t_n$, counts the number of ways to take a totally 
ordered $n$-element set and chop it into blocks of length 1, 2, or 3.
For example, $t_4 = 7$ since we have these 7 ways of chopping a
4-element totally ordered set into blocks of length 1, 2, or 3:
\[        \b|\b|\b|\b, \quad
\b\b|\b|\b, \quad \b|\b\b|\b, \quad \b|\b|\b\b, \quad \b\b|\b\b, \quad 
\b\b\b|\b, \quad \b|\b\b\b  .\]
We can also think of $t_n$ as counting the number of ways of writing
$n$ as a sum of 1's, 2's and 3's, where we keep track of the different 
orders of summation:
\[    4 =   1+1+1+1, \quad 2+1+1, \quad 1+2+1, 
\quad 1+1+2, \quad 2+2, \quad 3+1, \quad 1+3  .\]
Let $T$ be the structure type where a $T$-structure on the finite
set $S$ is a way of totally ordering $S$ and then chopping it into
blocks of length 1, 2, or 3.  The number of ways to put such a 
structure on the $n$-element set is
\[      |T_n| = n!\, t_n  \]
since there are $n!$ ways of ordering the set.  
The structure type $T$ thus has the generating function
\[          |T|(z) = \sum_{n = 0}^\infty { |T_n| \over n!} z^n  
                   = \sum_{n = 0}^\infty t_n z^n  
\]
}

\vskip 1em
\noindent
1.  Copying the case of the Fibonacci numbers, find 
an isomorphism between the structure type $T$ and some function 
involving $T$.

\vskip 1em
\noindent
2.  Decategorifying the above isomorphism, obtain an equation satisfied
by the generating function $|T|$.
 
\vskip 1em
\noindent
3.  Use this equation to derive a recurrence relation for the
Tribonacci numbers.

\vskip 1em
\noindent
4.  Solving the equation in part 2,
find $|T|(z)$ as an explicit function of $z$.

\vskip 1em
\noindent
5.  Find a closed-form expression for the 
pole of $|T|$ closest to the origin.  (If your algebra
skills are rusty, feel free to use a computer algebra
system such as Mathematica to solve the necessary cubic equation.)

\vskip 1em
\noindent
6.  Use part 5 and the souped-up version of Hadamard's theorem 
to show that
\[         t_n \sim c \tau^n  \]
for some constants $c,\tau > 0$, and find a closed-form expression
for $\tau$.  

\vskip 1em
\noindent
7.  Use a computer algebra system to calculate the 100th Tribonacci
number exactly, and also $\tau^{100}$.   Using these, estimate the
constant $c$.  {\it Extra Credit: guess or derive a closed-form 
expression for for $c$.}  

\vskip 1em
\noindent
8.  Generalizing from the Fibonacci and Tribonacci cases, define
the $n$th {\bf $k$-bonacci number} to be the number of
ways of taking a totally ordered $n$-element set and chopping it
into blocks of length $1,2,\dots,k$.  What is the generating function
for $k$-bonacci numbers?  What recurrence do they satisfy? 

\vskip 1em
\noindent
9.  Make a table of the $n$th $k$-bonacci number for $0 \le n \le 5$
and $1 \le k \le 5$.  Ponder the pattern.

\vskip 1em
\noindent
10.  Define the $n$th {\bf $\infty$-bonacci number} to be the number
of ways of chopping a totally ordered $n$-element set into blocks of
length $1,2,3,\dots$ --- that is, blocks of {\it arbitrary}
positive integral length.  What is the generating function for 
$\infty$-bonacci numbers?  Find a simple closed-form expression.

\vskip 1em
\noindent
11.  Using the generating function for $\infty$-bonacci numbers, 
find a closed-form expression of the $n$th $\infty$-bonacci number.

\vfill
\eject
\end{document}

 

