\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \def\t{Tak\'{a}cs} \def\a{\ensuremath{\mathcal A}} \def\b{\ensuremath{\mathcal B}} \def\s{\ensuremath{\mathcal S}} \newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \begin{center} \vskip 1cm{\LARGE\bf A Combinatorial Derivation of the \\ \ \\ Number of Labeled Forests } \vskip 1cm \large David Callan \\ Department of Statistics \\ University of Wisconsin-Madison \\ 1210 W. Dayton St. \\ Madison, WI \ 53706-1693 \\ \href{mailto:callan@stat.wisc.edu}{\tt callan@stat.wisc.edu} \\ \end{center} \vskip .2 in \begin{abstract} Lajos \t\ gave a somewhat formidable alternating sum expression for the number of forests of unrooted trees on $n$ labeled vertices. Here we use a weight-reversing involution on suitable tree configurations to give a combinatorial derivation of \t' result. \end{abstract} \newtheorem{theorem}{Theorem}[section] \newtheorem{proposition}{Proposition}[section] \newtheorem{corollary}{Corollary}[section] \newtheorem{lemma}{Lemma}[section] %path-generating code courtesy of Christian Krattenthaler %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %Input-Datei zum Erzeugen von Gitterpunktwegen.% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %LaTeX-Version% %%%%%%%%%%%%%%% %entering a path: % \Pfad(x-coordinate of starting point,y-coordinate of final %point),path % as 1-2-3-4-word\endPfad %(1=step in x-direction, 2=step in y-direction, 3=upward diagonal step, %4=downward diagonal step) % %entering a dotted path: % \SPfad(x-coordinate of starting point,y-coordinate of starting %point),path % as 1-2-3-4-word\endSPfad %(1=step in x-direction, 2=step in y-direction, 3=upward diagonal step, %4=downward diagonal step) % %coordinate-axes: % \Koordinatenachsen(length of positive x-axes, length of positive %y-axes)(length of negative x-axes, length of negative y-axes) %The length of negative axes are entered as negative numbers. % %lattice: % \Gitter(number of points in positive x-direction, number of points %in positive y-direction)(number of points in negative x-direction, %number of points in negative y-direction) % %diagonal lines: % \Diagonale(x-coordinate of SW-most point,y-coordinate of SW-most %point)length of the projection on the x-axes % %antidiagonal lines: % \AntiDiagonale(x-coordinate of NW-most point,y-coordinate of NW-most %point)length of the projection on the x-axes % %labelling of points: % \Label[location?]{[label]}(x-coordinate,y-coordinate) %where: % [location?]=\l,\lo,\lu,\r,\ro,\ru,\o,\u %and l=left, r=right, u=bottom, o=top. %In addition, if by \Einheit?cm the basic unit is changed, there exist %\llo,\loo,\llu,\luu,\rro,\roo,\rru,\ruu. % %The basic unit can be changed by entering % \Einheit=?cm %The default is \Einheit=0.5cm. % %The thickness of the paths can be changed by entering % \PfadDicke{?cm} %The default is \PfadDicke=1pt. % %The following point sizes are available: %\DuennPunkt, \NormalPunkt, \DickPunkt. Syntax: % \DickPunkt(x-coordinate,y-coordinate), etc. % %Besides, a circle is available by \Kreis. Syntax: % \Kreis(x-coordinate,y-coordinate) % \catcode`\@=11 \font\tenln = line10 \font\tenlnw = linew10 \thicklines \newskip\Einheit \Einheit=.6cm \newcount\xcoord \newcount\ycoord \newdimen\xdim \newdimen\ydim \newdimen\PfadD@cke \newdimen\Pfadd@cke \PfadD@cke2pt \Pfadd@cke0.3pt \def\PfadDicke#1{\PfadD@cke#1 \divide\PfadD@cke by2 \Pfadd@cke\PfadD@cke \multiply\PfadD@cke by2} \long\def\LOOP#1\REPEAT{\def\BODY{#1}\ITERATE} \def\ITERATE{\BODY \let\next\ITERATE \else\let\next\relax\fi \next} \let\REPEAT=\fi \def\Punkt{\hbox{\raise-2pt\hbox to0pt{\hss\scriptsize$\bullet$\hss}}} \def\DuennPunkt(#1,#2){\unskip \raise#2 \Einheit\hbox to0pt{\hskip#1 \Einheit \raise-1.5pt\hbox to0pt{\hss\tiny$\bullet$\hss}\hss}} \def\NormalPunkt(#1,#2){\unskip \raise#2 \Einheit\hbox to0pt{\hskip#1 \Einheit \raise-3pt\hbox to0pt{\hss\large$\bullet$\hss}\hss}} \def\DickPunkt(#1,#2){\unskip \raise#2 \Einheit\hbox to0pt{\hskip#1 \Einheit \raise-4pt\hbox to0pt{\hss\Large$\bullet$\hss}\hss}} \def\Kreis(#1,#2){\unskip \raise#2 \Einheit\hbox to0pt{\hskip#1 \Einheit \raise-4pt\hbox to0pt{\hss\Large$\circ$\hss}\hss}} \def\Diagonale(#1,#2)#3{\unskip\leavevmode \xcoord#1\relax \ycoord#2\relax \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \unitlength\Einheit \line(1,1){#3}\hss}} \def\AntiDiagonale(#1,#2)#3{\unskip\leavevmode \xcoord#1\relax \ycoord#2\relax \advance\xcoord by -0.05\relax \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \unitlength\Einheit \line(1,-1){#3}\hss}} \def\Pfad(#1,#2),#3\endPfad{\unskip\leavevmode \xcoord#1 \ycoord#2 \thicklines\ZeichnePfad#3\endPfad\thinlines} \def\ZeichnePfad#1{\ifx#1\endPfad\let\next\relax \else\let\next\ZeichnePfad \ifnum#1=1 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \vrule height\Pfadd@cke width1 \Einheit depth\Pfadd@cke\hss}% \advance\xcoord by 1 \else\ifnum#1=2 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \hbox{\hskip-\PfadD@cke\vrule height1 \Einheit width\PfadD@cke depth0pt}\hss}% \advance\ycoord by 1 \else\ifnum#1=3 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \unitlength\Einheit \line(1,1){1}\hss} \advance\xcoord by 1 \advance\ycoord by 1 \else\ifnum#1=4 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \unitlength\Einheit \line(1,-1){1}\hss} \advance\xcoord by 1 \advance\ycoord by -1 \fi\fi\fi\fi \fi\next} \def\hSSchritt{\leavevmode\raise-.4pt\hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise-.4pt\hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise-.4pt\hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise-.4pt\hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise-.4pt\hbox to0pt{\hss.\hss}\hskip.2\Einheit} \def\vSSchritt{\vbox{\baselineskip.2\Einheit\lineskiplimit0pt \hbox{.}\hbox{.}\hbox{.}\hbox{.}\hbox{.}}} \def\DSSchritt{\leavevmode\raise-.4pt\hbox to0pt{% \hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise.2\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise.4\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise.6\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise.8\Einheit\hbox to0pt{\hss.\hss}\hss}} \def\dSSchritt{\leavevmode\raise-.4pt\hbox to0pt{% \hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise-.2\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise-.4\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise-.6\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise-.8\Einheit\hbox to0pt{\hss.\hss}\hss}} \def\SPfad(#1,#2),#3\endSPfad{\unskip\leavevmode \xcoord#1 \ycoord#2 \ZeichneSPfad#3\endSPfad} \def\ZeichneSPfad#1{\ifx#1\endSPfad\let\next\relax \else\let\next\ZeichneSPfad \ifnum#1=1 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \hSSchritt\hss}% \advance\xcoord by 1 \else\ifnum#1=2 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \hbox{\hskip-2pt \vSSchritt}\hss}% \advance\ycoord by 1 \else\ifnum#1=3 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \DSSchritt\hss} \advance\xcoord by 1 \advance\ycoord by 1 \else\ifnum#1=4 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \dSSchritt\hss} \advance\xcoord by 1 \advance\ycoord by -1 \fi\fi\fi\fi \fi\next} \def\Koordinatenachsen(#1,#2){\unskip \hbox to0pt{\hskip-.5pt\vrule height#2 \Einheit width.5pt depth1 \Einheit}% \hbox to0pt{\hskip-1 \Einheit \xcoord#1 \advance\xcoord by1 \vrule height0.25pt width\xcoord \Einheit depth0.25pt\hss}} \def\Koordinatenachsen(#1,#2)(#3,#4){\unskip \hbox to0pt{\hskip-.5pt \ycoord-#4 \advance\ycoord by1 \vrule height#2 \Einheit width.5pt depth\ycoord \Einheit}% \hbox to0pt{\hskip-1 \Einheit \hskip#3\Einheit \xcoord#1 \advance\xcoord by1 \advance\xcoord by-#3 \vrule height0.25pt width\xcoord \Einheit depth0.25pt\hss}} \def\Gitter(#1,#2){\unskip \xcoord0 \ycoord0 \leavevmode \LOOP\ifnum\ycoord<#2 \loop\ifnum\xcoord<#1 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit\Punkt\hss}% \advance\xcoord by1 \repeat \xcoord0 \advance\ycoord by1 \REPEAT} \def\Gitter(#1,#2)(#3,#4){\unskip \xcoord#3 \ycoord#4 \leavevmode \LOOP\ifnum\ycoord<#2 \loop\ifnum\xcoord<#1 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit\Punkt\hss}% \advance\xcoord by1 \repeat \xcoord#3 \advance\ycoord by1 \REPEAT} \def\Label#1#2(#3,#4){\unskip \xdim#3 \Einheit \ydim#4 \Einheit \def\lo{\advance\xdim by-.5 \Einheit \advance\ydim by.5 \Einheit}% \def\llo{\advance\xdim by-.25cm \advance\ydim by.5 \Einheit}% \def\loo{\advance\xdim by-.5 \Einheit \advance\ydim by.25cm}% %NEW DEF \O := \OX \def\o{\advance\ydim by.25cm}% \def\ro{\advance\xdim by.5 \Einheit \advance\ydim by.5 \Einheit}% \def\rro{\advance\xdim by.25cm \advance\ydim by.5 \Einheit}% \def\roo{\advance\xdim by.5 \Einheit \advance\ydim by.25cm}% \def\l{\advance\xdim by-.30cm}% \def\r{\advance\xdim by.30cm}% \def\lu{\advance\xdim by-.5 \Einheit \advance\ydim by-.6 \Einheit}% \def\llu{\advance\xdim by-.25cm \advance\ydim by-.6 \Einheit}% \def\luu{\advance\xdim by-.5 \Einheit \advance\ydim by-.30cm}% \def\u{\advance\ydim by-.30cm}% \def\ru{\advance\xdim by.5 \Einheit \advance\ydim by-.6 \Einheit}% \def\rru{\advance\xdim by.25cm \advance\ydim by-.6 \Einheit}% \def\ruu{\advance\xdim by.5 \Einheit \advance\ydim by-.30cm}% #1\raise\ydim\hbox to0pt{\hskip\xdim \vbox to0pt{\vss\hbox to0pt{\hss$#2$\hss}\vss}\hss}% } \catcode`\@=12 \renewcommand{\baselinestretch}{1.0} \vspace{5mm} \t\ \cite{takacs} used Lagrange inversion to obtain the alternating sum expression \begin{equation} \frac{n!}{n+1} \sum_{j=0}^{\lfloor n/2 \rfloor} (-1)^{j} \frac{(2j+1)(n+1)^{n-2j}}{2^{j} j! (n-2j)!} \label{eq:1} \end{equation} for the number of forests of unrooted trees on $[n]=\{1,2,\ldots,n\}$ \htmladdnormallink{A001858}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001858}. This contrasts with Cayley's simple expression $(n+1)^{n-1}$ \htmladdnormallink{A000272}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000272} for the number of forests of rooted trees on $[n]$. Here we use well-known counts for forests of rooted trees to give a combinatorial derivation of \t's result: we present (\ref{eq:1}) as the total weight of certain weighted tree configurations in which forests of unrooted trees show up with weight $+1$ and we exhibit a weight-reversing involution that cancels out the weights of all other configurations. First, rewrite (\ref{eq:1}) as \begin{equation} \sum_{0\le j \le n/2}^{}\ (-1)^{j}\phantom{\int_{}^{}}\underbrace{\binom{n}{2j}(2j-1)!!}_{A}\phantom{\int_{}^{}} \underbrace{(2j+1)(n+1)^{(n+1)-(2j+1)-1}\phantom{\int_{}^{}}}_{B} \label{eq:2} \end{equation} where $(2j-1)!!=1\cdot 3\cdot 5 \ldots (2j-1)$ is the double factorial. The factor $B$ is the number of forests on $[0,n]$ consisting of $2j+1$ trees rooted at a specified set of $2j+1$ roots \cite[Theorem 3.3, p.\:17]{moon} (see also \cite[\S 2.1]{pitman} for a recent elegant proof). The factor $A$ is the number of ways to select $2j$ elements from $[n]$ and then divide them up into pairs; in other words, to form a perfect matching on some $2j$ elements of $[n]$. These $2j$ elements, together with 0, serve nicely as the specified roots to construct configurations counted by the product $AB$. Define a \emph{partially-paired rooted} (PPR, for short) \emph{$n$-forest} to be a tree rooted at 0 and zero or more (unordered) pairs of rooted trees, the vertex sets of all the trees forming a partition of $[0,n]$. The \emph{pair-count} of a PPR forest is its number of pairs of trees. The product $AB$ is then the number of PPR $n$-forests with pair-count $j$. If we define the \emph{weight} of a PPR forest of pair-count $j$ to be $(-1)^{j}$, then the right hand side of (1) is the total weight of all PPR $n$-forests. To include the objects we're trying to count among these PPR $n$-forests, we suppose each tree in an unrooted forest to be rooted at its \emph{smallest} vertex. Then forests of unrooted trees on $[n]$ correspond precisely to PPR $n$-forests with pair-count 0 and each child of vertex 0 smaller than all its descendants (delete vertex 0 to get the forest of unrooted trees). A vertex $v$ in a rooted tree is \emph{inversion-initiating} if at least one descendant of $v$ is $