%Submitted to Volker S for Pierre L memory volume 6/11/08 
%Article-id: 0805.0817, Article password: j5xkh 
% THIS DOCUMENT IS WRITTEN IN LATEX 2e
%
% TO FIND THE TITLE:  search for the command \title using your word 
% processor
%
\documentclass[12pt,reqno]{amsart}
\usepackage{amssymb,latexsym,amsthm,amsmath}
\usepackage{pstricks,pst-node,pst-tree}
\usepackage{graphicx, pst-plot}

\newcommand{\ben}{\begin{enumerate}}
\newcommand{\een}{\end{enumerate}}
\newcommand{\ble}{\begin{lem}}
\newcommand{\ele}{\end{lem}}
\newcommand{\bth}{\begin{thm}}
\renewcommand{\eth}{\end{thm}}
\newcommand{\bpr}{\begin{prop}}
\newcommand{\epr}{\end{prop}}
\newcommand{\bco}{\begin{cor}}
\newcommand{\eco}{\end{cor}}
\newcommand{\bcon}{\begin{conj}}
\newcommand{\econ}{\end{conj}}
\newcommand{\bde}{\begin{defn}}
\newcommand{\ede}{\end{defn}}
\newcommand{\bex}{\begin{exa}}
\newcommand{\eex}{\end{exa}}
\newcommand{\barr}{\begin{array}}
\newcommand{\earr}{\end{array}}
\newcommand{\btab}{\begin{tabular}}
\newcommand{\etab}{\end{tabular}}
\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\bea}{\begin{eqnarray*}}
\newcommand{\eea}{\end{eqnarray*}}
\newcommand{\bce}{\begin{center}}
\newcommand{\ece}{\end{center}}
\newcommand{\bpi}{\begin{picture}}
\newcommand{\epi}{\end{picture}}
\newcommand{\bpp}{\begin{picture}}
\newcommand{\epp}{\end{picture}}
\newcommand{\bfi}{\begin{figure} \begin{center}}
\newcommand{\efi}{\end{center} \end{figure}}
\newcommand{\bprf}{\begin{proof}}
\newcommand{\eprf}{\end{proof}\medskip}
\newcommand{\capt}{\caption}
\newcommand{\bsl}{\begin{slide}{}}
\newcommand{\esl}{\end{slide}}
\newcommand{\bfr}{\begin{frame}}
\newcommand{\efr}{\end{frame}}

\newcommand{\fti}[1]{\frametitle{#1}}

\newcommand{\pscb}[1]{\pscirclebox{#1}}

%\newcommand{\ch}{\choose}
\newcommand{\bib}{thebibliography}
\newcommand{\pf}{{\bf Proof}\hspace{7pt}}
\newcommand{\prf}{{\bf Proof.\hspace{7pt}}}
%\newcommand{\qed}{\rule{1ex}{1ex}}
\newcommand{\hqed}{\hfill \qed}
\newcommand{\hqedm}{\hfill \qed \medskip}
\newcommand{\Qed}{\rule{1ex}{1ex} \medskip}
\newcommand{\qqed}{\qquad\rule{1ex}{1ex}}
\newcommand{\Qqed}{\qquad\rule{1ex}{1ex}\medskip}
\newcommand{\eqed}[1]{$\textcolor{white}{\qed}\hfill{\dil#1}\hfill\qed$}
\newcommand{\mc}[3]{\multicolumn{#1}{#2}{#3}}
%\newcommand{\Mc}[1]{\multicolumn{#1}{c}{}}
%\newcommand{\mc}[2]{\multicolumn{#1}{#2}}
\newcommand{\ul}{\underline}
\newcommand{\ol}{\overline}
\newcommand{\hor}{\mbox{--}}
\newcommand{\hs}[1]{\hspace{#1}}
\newcommand{\hso}[1]{\hspace{-1pt}}
\newcommand{\vs}[1]{\vspace{#1}}
\newcommand{\qmq}[1]{\quad\mbox{#1}\quad}
\newcommand{\ssk}{\smallskip}
\newcommand{\msk}{\mediumskip}
\newcommand{\bsk}{\bigskip}
\newcommand{\rp}[2]{\rule{#1pt}{#2pt}}
\newcommand{\st}[1]{\rule{#1pt}{0pt}}
%\newcommand{\st}[1]{\rule{#1}{0pt}}
\newcommand{\mbl}[1]{\makebox(0,0)[l]{#1}}
\newcommand{\mbr}[1]{\makebox(0,0)[r]{#1}}
\newcommand{\mbt}[1]{\makebox(0,0)[t]{#1}}
\newcommand{\mbb}[1]{\makebox(0,0)[b]{#1}}
\newcommand{\mbc}[1]{\makebox(0,0){#1}}
\newcommand\mar[1]{\marginpar{\raggedleft#1}}
\newcommand{\pmo}[2]{\put(#1){\makebox(0,0){#2}}}

\newcommand{\emp}{\emptyset}
\newcommand{\indu}{\uparrow}
\newcommand{\rest}{\downarrow}
\newcommand{\sm}{\hspace{-2pt}\setminus\hspace{-2pt}}
\newcommand{\sbs}{\subset}
\newcommand{\sbe}{\subseteq}
\newcommand{\sps}{\supset}
\newcommand{\spe}{\supseteq}
\newcommand{\setm}{\setminus}
\newcommand{\asy}{\thicksim}
\newcommand{\dle}{<\hspace{-6pt}\cdot}
\newcommand{\dge}{\cdot\hspace{-6pt}>}
\newcommand{\lec}{\lessdot}
\newcommand{\grc}{\gtrdot}
\newcommand{\iso}{\cong}
%\newcommand{\con}{\equiv}
\newcommand{\Cong}{\equiv}
\newcommand{\conm}[1]{\stackrel{#1}{\equiv}}

\newcommand{\widevec}{\overrightarrow}
%makes a wide arrow over stuff if have \overrightarrow{stuff} 
\newcommand{\Ch}{\hat{C}}
\newcommand{\eh}{\hat{e}}
\newcommand{\Gh}{\hat{G}}
\newcommand{\ih}{\hat{\imath}}
\newcommand{\jh}{\hat{\jmath}}
\newcommand{\gh}{\hat{g}}
\newcommand{\mh}{\hat{0}}
\newcommand{\Mh}{\hat{1}}
\newcommand{\Dh}{\hat{D}}
\newcommand{\lah}{\hat{\la}}
\newcommand{\zh}{\hat{0}}
\newcommand{\oh}{\hat{1}}
\newcommand{\Ph}{\hat{P}}
\newcommand{\ph}{\hat{p}}
\newcommand{\Pih}{\hat{\Pi}}
\newcommand{\bbPh}{\hat{\bbP}}
\newcommand{\Qh}{\hat{Q}}
\newcommand{\Sh}{\hat{S}}
\newcommand{\lh}{\hat{l}}
\newcommand{\xh}{\hat{x}}
\newcommand{\Yh}{\hat{Y}}
\newcommand{\ptn}{\vdash}
\newcommand{\cpn}{\models}
\newcommand{\lt}{\lhd}
\newcommand{\gt}{\rhd}
\newcommand{\lte}{\unlhd}
\newcommand{\gte}{\unrhd}
\newcommand{\jn}{\vee}
\newcommand{\Jn}{\bigvee}
\newcommand{\mt}{\wedge}
\newcommand{\Mt}{\bigwedge}
\newcommand{\bdy}{\partial}
\newcommand{\sd}{\bigtriangleup}
\newcommand{\case}[4]{\left\{\barr{ll}#1&\mbox{#2}\\#3&\mbox{#4}\earr\right.}
\newcommand{\fl}[1]{\lfloor #1 \rfloor}
\newcommand{\ce}[1]{\lceil #1 \rceil}
\newcommand{\flf}[2]{\left\lfloor\frac{#1}{#2}\right\rfloor}
\newcommand{\cef}[2]{\left\lceil\frac{#1}{#2}\right\rceil}
\newcommand{\gau}[2]{\left[ \barr{c} #1 \\ #2 \earr \right]}
\newcommand{\setc}[2]{\{left{#1}\ :\ #2\}}
\newcommand{\setl}[2]{\{left{#1}\ |\ #2\}}
\newcommand{\qst}{$q$-Stirling numbers}
\newcommand{\qbi}{$q$-binomial coefficients}
\newcommand{\del}{\nabla}
\newcommand{\pde}[2]{\frac{\partial#1}{\partial#2}}
\newcommand{\spd}[2]{\frac{\partial^2\hspace{-2pt}#1}{\partial#2^2}}
\newcommand{\ode}[2]{\ds\frac{d#1}{d#2}}
\def\<{\langle}
\def\>{\rangle}
\newcommand{\fall}[2]{\langle{#1}\rangle_{#2}}
\newcommand{\nor}[1]{\parallel{#1}\parallel}
\newcommand{\ipr}[2]{\langle{#1},{#2}\rangle}
\newcommand{\spn}[1]{\langle{#1}\rangle}
%\newcommand{\lb}{\left\{}
%\newcommand{\rb}{\right\}}
\newcommand{\ree}[1]{(\ref{#1})}
\newcommand{\rpl}{$\longleftarrow$}

\newcommand{\ra}{\rightarrow}
\newcommand{\Ra}{\Rightarrow}
\newcommand{\lta}{\leftarrow}
\newcommand{\rla}{\leftrightarrow}
\newcommand{\lra}{\longrightarrow}
\newcommand{\lla}{\longleftarrow}
\newcommand{\Lra}{\Longrightarrow}
\newcommand{\llra}{\longleftrightarrow}
\newcommand{\Llra}{\Longleftrightarrow}
\newcommand{\ve}[1]{\stackrel{\ra}{#1}}


\newcommand{\al}{\alpha}
\newcommand{\be}{\beta}
\newcommand{\ga}{\gamma}
\newcommand{\de}{\delta}
\newcommand{\ep}{\epsilon}
\newcommand{\vep}{\varepsilon}
\newcommand{\io}{\iota}
\newcommand{\ka}{\kappa}
\newcommand{\la}{\lambda}
\newcommand{\mut}{\tilde{\mu}}
\newcommand{\om}{\omega}
\newcommand{\Phit}{\tilde{\Phi}}
\newcommand{\Psit}{\tilde{\Psi}}
\newcommand{\rhot}{\tilde{\rho}}
\newcommand{\si}{\sigma}
\renewcommand{\th}{\theta}
%       NOTE THAT \th HAS BEEN RENEWCOMMANDed
\newcommand{\ze}{\zeta}
\newcommand{\Al}{\Alpha}
\newcommand{\Ga}{\Gamma}
\newcommand{\De}{\Delta}
\newcommand{\Ep}{\epsilon}
\newcommand{\La}{\Lambda}
\newcommand{\Om}{\Omega}
\newcommand{\Si}{\Sigma}
\newcommand{\Th}{\Theta}
\newcommand{\Ze}{\Zeta}


\newcommand{\0}{{\bf 0}}
\newcommand{\1}{{\bf 1}}
\newcommand{\2}{{\bf 2}}
\newcommand{\3}{{\bf 3}}
\newcommand{\4}{{\bf 4}}
\newcommand{\5}{{\bf 5}}
\newcommand{\6}{{\bf 6}}
\newcommand{\7}{{\bf 7}}
\newcommand{\8}{{\bf 8}}
\newcommand{\9}{{\bf 9}}
\newcommand{\ba}{{\bf a}}
\newcommand{\bb}{{\bf b}}
\newcommand{\bc}{{\bf c}}
\newcommand{\bd}{{\bf d}}
\newcommand{\bfe}{{\bf e}}
\newcommand{\bff}{{\bf f}}
\newcommand{\bg}{{\bf g}}
\newcommand{\bh}{{\bf h}}
\newcommand{\bi}{{\bf i}}
\newcommand{\bj}{{\bf j}}
\newcommand{\bk}{{\bf k}}
\newcommand{\bl}{{\bf l}}
\newcommand{\bm}{{\bf m}}
\newcommand{\bn}{{\bf n}}
\newcommand{\bp}{{\bf p}}
\newcommand{\bq}{{\bf q}}
\newcommand{\br}{{\bf r}}
\newcommand{\bs}{{\bf s}}
\newcommand{\bt}{{\bf t}}
\newcommand{\bu}{{\bf u}}
\newcommand{\bv}{{\bf v}}
\newcommand{\bw}{{\bf w}}
\newcommand{\bx}{{\bf x}}
\newcommand{\by}{{\bf y}}
\newcommand{\bz}{{\bf z}}
\newcommand{\bA}{{\bf A}}
\newcommand{\bB}{{\bf B}}
\newcommand{\bC}{{\bf C}}
\newcommand{\bE}{{\bf E}}
\newcommand{\bF}{{\bf F}}
\newcommand{\bG}{{\bf G}}
\newcommand{\bH}{{\bf H}}
\newcommand{\bN}{{\bf N}}
\newcommand{\bP}{{\bf P}}
\newcommand{\bQ}{{\bf Q}}
\newcommand{\bR}{{\bf R}}
\newcommand{\bS}{{\bf S}}
\newcommand{\bT}{{\bf T}}
\newcommand{\bX}{{\bf X}}
\newcommand{\bXh}{\hat{{\bf X}}}
\newcommand{\bZ}{{\bf Z}}
\newcommand{\bep}{{\bf \ep}}
\newcommand{\bcdot}{{\bf \cdot}}
\newcommand{\bmpl}{
\hspace{2pt}
\begin{pspicture}(.3,.3)
\psline[linewidth=1.5pt,arrows=cc-cc](.15,0)(.15,.3)
\psline[linewidth=1.5pt,arrows=cc-cc](0,.15)(.3,.15)
\end{pspicture}
\hspace{2pt}
}
\newcommand{\bmmi}{
\hspace{2pt}
\begin{pspicture}(.3,.3)
\psline[linewidth=1.5pt,arrows=cc-cc](0,.15)(.3,.15)
\end{pspicture}
\hspace{2pt}
}
\newcommand{\bma}{\mbox{\boldmath $a$}}
\newcommand{\bmb}{\mbox{\boldmath $b$}}
\newcommand{\bmk}{\mbox{\boldmath $k$}}
\newcommand{\bml}{\mbox{\boldmath $l$}}
\newcommand{\bmn}{\mbox{\boldmath $n$}}
\newcommand{\bbC}{{\mathbb C}}
\newcommand{\bbF}{{\mathbb F}}
\newcommand{\bbN}{{\mathbb N}}
\newcommand{\bbP}{{\mathbb P}}
\newcommand{\bbQ}{{\mathbb Q}}
\newcommand{\bbR}{{\mathbb R}}
\newcommand{\bbS}{{\mathbb S}}
\newcommand{\bbZ}{{\mathbb Z}}
\newcommand{\cA}{{\mathcal A}}
\newcommand{\cAB}{{\mathcal AB}}
\newcommand{\cAD}{{\mathcal AD}}
\newcommand{\cB}{{\mathcal B}}
\newcommand{\cBC}{{\mathcal BC}}
\newcommand{\cC}{{\mathcal C}}
\newcommand{\cD}{{\mathcal D}}
\newcommand{\cDB}{{\mathcal DB}}
\newcommand{\cE}{{\mathcal E}}
\newcommand{\cF}{{\mathcal F}}
\newcommand{\cG}{{\mathcal G}}
\newcommand{\cH}{{\mathcal H}}
\newcommand{\cI}{{\mathcal I}}
\newcommand{\cIF}{{\mathcal IF}}
\newcommand{\cJ}{{\mathcal J}}
\newcommand{\cK}{{\mathcal K}}
\newcommand{\cL}{{\mathcal L}}
\newcommand{\cm}{{\mathcal m}}
\newcommand{\cM}{{\mathcal M}}
\newcommand{\cN}{{\mathcal N}}
\newcommand{\cNBC}{{\mathcal NBC}}
\newcommand{\cO}{{\mathcal O}}
\newcommand{\cP}{{\mathcal P}}
\newcommand{\cPD}{{\mathcal PD}}
\newcommand{\cR}{{\mathcal R}}
\newcommand{\cRF}{{\mathcal RF}}
\newcommand{\cS}{{\mathcal S}}
\newcommand{\cT}{{\mathcal T}}
\newcommand{\cTb}{\ol{\mathcal T}}
\newcommand{\cV}{{\mathcal V}}
\newcommand{\cW}{{\mathcal W}}
\newcommand{\cX}{{\mathcal X}}
\newcommand{\cY}{{\mathcal Y}}
\newcommand{\cZ}{{\mathcal Z}}

\newcommand{\df}{\dot{f}}
\newcommand{\dF}{\dot{F}}
\newcommand{\fg}{{\mathfrak g}}
\newcommand{\fgt}{\tilde{\mathfrak g}}
\newcommand{\fgl}{{\mathfrak gl}}
\newcommand{\fL}{{\mathfrak L}}
\newcommand{\fS}{{\mathfrak S}}
\newcommand{\fsl}{{\mathfrak sl}}
\newcommand{\at}{\tilde{a}}
\newcommand{\ct}{\tilde{c}}
\newcommand{\dt}{\tilde{d}}
\newcommand{\pt}{\tilde{p}}
\newcommand{\Bt}{\tilde{B}}
\newcommand{\Gt}{\tilde{G}}
\newcommand{\Ht}{\tilde{H}}
\newcommand{\Kt}{\tilde{K}}
\newcommand{\Nt}{\tilde{N}}
\newcommand{\St}{\tilde{S}}
\newcommand{\Xt}{\tilde{X}}
\newcommand{\alt}{\tilde{\alpha}}
\newcommand{\bet}{\tilde{\beta}}
\newcommand{\rht}{\tilde{\rho}}
\newcommand{\Pit}{\tilde{\Pi}}
\newcommand{\tal}{\tilde{\alpha}}
\newcommand{\tbe}{\tilde{\beta}}
\newcommand{\tPi}{\tilde{\Pi}}
\newcommand{\ab}{\ol{a}}
\newcommand{\Ab}{\ol{A}}
\newcommand{\Bb}{\ol{B}}
\newcommand{\cb}{\ol{c}}
\newcommand{\Cb}{{\ol{C}}}
\newcommand{\db}{\ol{d}}
\newcommand{\Db}{\ol{D}}
\newcommand{\eb}{\ol{e}}
\newcommand{\Eb}{\ol{E}}
\newcommand{\fb}{\ol{f}}
\newcommand{\Fb}{\ol{F}}
\newcommand{\Gb}{\ol{G}}
\newcommand{\Hb}{\ol{H}}
\newcommand{\ib}{\ol{\imath}}
\newcommand{\Ib}{\ol{I}}
\newcommand{\jb}{\ol{\jmath}}
\newcommand{\Jb}{\ol{J}}
\newcommand{\kb}{\ol{k}}
\newcommand{\Kb}{\ol{K}}
\newcommand{\nb}{\ol{n}}
\newcommand{\pb}{\ol{p}}
\newcommand{\Pb}{\ol{P}}
\newcommand{\Phib}{\ol{\Phi}}
\newcommand{\Qb}{\ol{Q}}
\newcommand{\rb}{\ol{r}}
\newcommand{\Rb}{\ol{R}}
\newcommand{\Sb}{\ol{S}}
\newcommand{\tb}{\ol{t}}
\newcommand{\Tb}{\ol{T}}
\newcommand{\Ub}{\ol{U}}
\newcommand{\Wb}{\ol{W}}
\newcommand{\xb}{\ol{x}}
\newcommand{\Xb}{\ol{X}}
\newcommand{\yb}{\ol{y}}
\newcommand{\Yb}{\ol{Y}}
\newcommand{\zb}{\ol{z}}
\newcommand{\Zb}{\ol{Z}}
\newcommand{\pib}{\ol{\pi}}
\newcommand{\sib}{\ol{\si}}
\newcommand{\degb}{\ol{\deg}}
\newcommand{\vj}{\vec{\jmath}}
\newcommand{\vr}{\vec{r}}
\newcommand{\vv}{\vec{v}}
\newcommand{\vw}{\vec{w}}
\newcommand{\ttab}{\{t\}}
\newcommand{\stab}{\{s\}}


\newcommand{\Age}{\operatorname{Age}}
\newcommand{\Aut}{\operatorname{Aut}}
\newcommand{\abl}{\operatorname{al}}
\newcommand{\BC}{\operatorname{BC}}
\newcommand{\capa}{\operatorname{cap}}
\newcommand{\codim}{\operatorname{codim}}
\newcommand{\ch}{\operatorname{ch}}
%Commented out \ch for choose
\newcommand{\col}{\operatorname{col}}
\newcommand{\ctt}{\operatorname{ct}}
\newcommand{\Der}{\operatorname{Der}}
\newcommand{\des}{\operatorname{des}}
\newcommand{\Des}{\operatorname{Des}}
\newcommand{\diag}{\operatorname{diag}}
\newcommand{\Diag}{\operatorname{Diag}}
\newcommand{\diam}{\operatorname{diam}}
\newcommand{\End}{\operatorname{End}}
\newcommand{\ev}{\operatorname{ev}}
\newcommand{\eval}{\operatorname{eval}}
\newcommand{\Eval}{\operatorname{Eval}}
\newcommand{\FPF}{\operatorname{FPF}}
\newcommand{\gen}{\operatorname{gen}}
\newcommand{\Harm}{\operatorname{Harm}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\im}{\operatorname{im}}
\newcommand{\imaj}{\operatorname{imaj}}
\newcommand{\inc}{\operatorname{inc}}
\newcommand{\Ind}{\operatorname{Ind}}
\newcommand{\inter}{\operatorname{int}}
\newcommand{\Inter}{\operatorname{Int}}
\newcommand{\inv}{\operatorname{inv}}
\newcommand{\Inv}{\operatorname{Inv}}
\newcommand{\lcm}{\operatorname{lcm}}
\newcommand{\LHS}{\operatorname{LHS}}
\newcommand{\Mat}{\operatorname{Mat}}
\newcommand{\maj}{\operatorname{maj}}
\newcommand{\Mod}{\operatorname{mod}}
\newcommand{\NBB}{\operatorname{NBB}}
\newcommand{\nin}{\operatorname{nin}}
\newcommand{\Nin}{\operatorname{Nin}}
\newcommand{\nul}{\operatorname{nul}}
\newcommand{\od}{\operatorname{od}}
\newcommand{\per}{\operatorname{per}}
\newcommand{\Pete}{\operatorname{Pete}}
\newcommand{\pfa}{\operatorname{pf}}
\newcommand{\Pm}{\operatorname{pm}}
\newcommand{\PM}{\operatorname{PM}}
\newcommand{\Pol}{\operatorname{Pol}}
\newcommand{\rad}{\operatorname{rad}}
\newcommand{\RHS}{\operatorname{RHS}}
\newcommand{\rk}{\operatorname{rk}}
\newcommand{\rank}{\operatorname{rank}}
\newcommand{\reg}{\operatorname{reg}}
\newcommand{\row}{\operatorname{row}}
\newcommand{\sdiam}{\operatorname{sdiam}}
\newcommand{\sgn}{\operatorname{sgn}}
\newcommand{\sign}{\operatorname{sign}}
\newcommand{\sh}{\operatorname{sh}}
\newcommand{\shu}{\hspace{10pt}
\raisebox{10pt}{
\bpi(0,0)(10,10)
\put(0,0){\line(1,0){10}}
\put(0,0){\line(0,1){10}}
\put(5,0){\line(0,1){10}}
\put(10,0){\line(0,1){10}}
\epi
\hspace{1pt}
}}
\newcommand{\slack}{\operatorname{slack}}
\newcommand{\spa}{\operatorname{span}}
\newcommand{\sta}{\operatorname{st}}
\newcommand{\summ}{\operatorname{sum}}
\newcommand{\Supp}{\operatorname{Supp}}
\newcommand{\sus}{\operatorname{susp}}
\newcommand{\Sym}{\operatorname{Sym}}
\newcommand{\SYT}{\operatorname{SYT}}
\newcommand{\tang}{\operatorname{tang}}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\tri}{\operatorname{tri}}
\newcommand{\wed}{\operatorname{wedge}}
\newcommand{\wt}{\operatorname{wt}}







\newcommand{\new}[1]{\vs{5pt}\ensuremath{\blacktriangleright}#1\ensuremath{\blacktriangleleft}\vs{5pt}}
\newcommand{\bul}{\bullet}
\newcommand{\dil}{\displaystyle}
\newcommand{\dsum}{\dil\sum}
\newcommand{\dint}{\dil\int}
%\newcommand{\dfrac}{\dil\frac}
\newcommand{\scl}{\scriptstyle}
\newcommand{\ssl}{\scriptscriptstyle}
\newcommand{\foz}{\footnotesize}
\newcommand{\scz}{\scriptsize}
\newcommand{\cho}{\choose}

\newcommand{\Schu}{Sch\"utzenberger}
\newcommand{\aim}{Adv.\ in Math.\/}
\newcommand{\bams}{Bull.\ Amer.\ Math.\ Soc.\/}
\newcommand{\cjm}{Canad.\ J. Math.\/}
\newcommand{\dm}{Discrete Math.\/}
\newcommand{\dmj}{Duke Math.\ J.\/}
\newcommand{\ejc}{European J. Combin.\/}
\newcommand{\jaa}{J. Algebra\/}
\newcommand{\jac}{J. Algebraic Combin.\/}
\newcommand{\jas}{J. Algorithms\/}
\newcommand{\jams}{J. Amer.\ Math.\ Soc.\/}
\newcommand{\jct}{J. Combin.\ Theory\/}
\newcommand{\jcta}{J. Combin.\ Theory Ser. A\/}
\newcommand{\jctb}{J. Combin.\ Theory Ser. B\/}
\newcommand{\jgt}{J. Graph Theory\/}
\newcommand{\jram}{J. Reine Angew.\ Math.\/}
\newcommand{\pjm}{Pacific J. Math.\/}
\newcommand{\pams}{Proc.\ Amer.\ Math.\ Soc.\/}
\newcommand{\plms}{Proc.\ London Math.\ Soc.\/}
\newcommand{\tams}{Trans.\ Amer.\ Math.\ Soc.\/}
\newcommand{\pja}{Proc.\ Japan Acad.\ Ser.\ A  Math\/}
\newcommand{\sv}{Springer-Verlag Lecture Notes in Math.\/}
\newcommand{\crgs}{Combinatoire et Repr\'{e}sentation du 
    Groupe Sym\'{e}trique, Strasbourg 1976, D. Foata ed.}
\newcommand{\caup}{Cambridge University Press}
\newcommand{\oup}{Oxford University Press} 
\newcommand{\pr}{preprint}
\newcommand{\ip}{in preparation}
\newcommand{\ds}{\displaystyle}


\newcommand{\Prob}{\operatorname{Prob}}
\newcommand{\cFb}{\ol{\cF}}
\newcommand{\Tha}{\hat{T}}
\newcommand{\n}[1]{\cnode*{.1}{#1}}
\newcommand{\mm}{\hspace*{-50pt}m{\binom m2}\hspace*{-50pt}}
\newcommand{\fone}{\frac{m-2}{3m}}
\newcommand{\ftwo}{\frac{m-1}{2m^2}}
\newcommand{\fthr}{\frac{m}{m^2}}
\newcommand{\ffou}{\frac{m}{m^3}}
\newcommand{\tone}{\frac{1}{2\cdot 3}}
\newcommand{\ttwo}{\frac{1}{2\cdot 1}}

\setlength{\topmargin}{.1in}
\setlength{\textheight}{8in}
\setlength{\textwidth}{5.8in}
\setlength{\evensidemargin}{.4in}
\setlength{\oddsidemargin}{.4in}


\newtheorem{thm}{Theorem}[section]
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{exa}[thm]{Example}
\newtheorem{question}[thm]{Question}

\newbox\Adr
\setbox\Adr\vbox{
\centerline{\sc Bruce E. Sagan$^1$}
\vskip18pt
\centerline{Department of Mathematics, Michigan State University,}
\centerline{East Lansing, MI 48824-1027, USA}
\vskip8pt
}

\begin{document}

\title{Probabilistic proofs of hook length formulas involving trees
}

\author[Bruce E. Sagan]{\leavevmode\box\Adr}

\thanks{$^1$ This material is based on research done while working at the
 National Science Foundation (NSF). The views
expressed do not necessarily reflect those of the NSF.}

\keywords{algorithm, hook length, probability, tree}
\subjclass[2000]{Primary 05A19;
	Secondary 60C05}
\dedicatory{This paper is dedicated to the memory of Pierre
Leroux.  In fact, reference~\cite{sy:pat} was written while both Sagan
and Yeh were visiting the Universit\'e de Qu\'ebex \`a Montr\'eal and
partaking of Leroux's legendary hospitality.}


\begin{abstract}

Recently, Han discovered two formulas involving binary
trees which have the interesting property that hooklengths appear as
exponents.  The purpose of this note is to give a probabilistic proof
of one of Han's formulas.  Yang has generalized Han's results to
ordered trees.  We show how the probabilistic approach can also be
used in Yang's setting, as well as for a generalization of Han's
formula in terms of certain infinite trees.

\end{abstract}
\maketitle

%First page headline in LaTeX for S\'eminaire Lotharingien de Combinatoire
%--first part
\thispagestyle{myheadings}
\font\rms=cmr8 
\font\its=cmti8 
\font\bfs=cmbx8

\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 61A \rms (2009), Article~B61Ab\hfill}
\def\thepage{}

\section{Introduction and definitions}

Frame, Robinson, and Thrall~\cite{frt:hgs} discovered the hook formula
for standard Young tableaux.  Greene, Nijenhuis, and
Wilf~\cite{gnw:ppf} then gave a probabilistic proof of this result
where the hook lengths appeared in a very natural way.  The same trio
also used probabilistic methods to prove the sum of squares formula
for the symmetric group~\cite{gnw:apm}.  Sagan~\cite{sag:srs} and
Sagan and Yeh~\cite{sy:pat} gave probabilistic algorithms for proving
hook formulas for shifted Young tableaux and trees, respectively.

Recently, inspired by an identity of Postnikov~\cite{pos:pab},
Han~\cite{han:nhl} proved two identities involving binary 
trees which have the interesting property that hooklengths appear as
exponents.  (Han~\cite{han:agp} also discovered an identity with this
same property which generalizes Postnikov's.)  Han's demonstration was
by algebraic manipulation of recursions.  Yang~\cite{yan:ghh}
generalized Han's identities to weighted ordered 
trees.  Again, the proofs were algebraic in nature, this time using
generating functions.  

The purpose of this note is to give a probabilistic proof of Han's
first formula which is similar in some ways to the second algorithm of
Greene, Nijenhuis, and Wilf.  
A weighted version of the algorithm 
proves the analogous identity of Yang.  A second generalization of
Han's original formula to certain infinite trees is also demonstrated by
this method.  The rest of this section is devoted to the necessary
definitions to state the identities to be proved.  Section~\ref{a}
gives the probabilistic algorithm and proofs.  The final section is
devoted to indicating how Han's second formula might be demonstrated
probabilistically.  



\bfi
$$
\begin{psmatrix}[rowsep=15pt,colsep=25pt]
      &      &\n{a1}&&      &\n{b1}&&      &\n{c1}&      &&\n{d1}&      &&\n{e1}&      &\\
      &\n{a2}&      &&\n{b2}&      &&\n{c2}&      &\n{c3}&&      &\n{d2}&&      &\n{e2}&\\
\n{a3}&      &      &&      &\n{b3}&&      &      &      &&\n{d3}&      &&      &      &\n{e3}
\end{psmatrix}
\ncline{a1}{a3}
\ncline{b1}{b2}
\ncline{b2}{b3}
\ncline{c1}{c2}
\ncline{c1}{c3}
\ncline{d1}{d2}
\ncline{d2}{d3}
\ncline{e1}{e3}
$$
\vspace{5pt}
\capt{The trees in $\cB(3)$}
\label{B3}
\efi

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL BRUCE E. SAGAN}{\SMALL PROBABLISTIC PROOFS OF HOOK LENGTH
FORMULAS INVOLVING TREES}
%
%


For any tree, $T$, we denote the vertex set of $T$ by $V(T)$.
If no confusion will result, we
will often write $v\in T$ and $|T|$ in place of the more cumbersome
$v\in V(T)$ and $|V(T)|$, where $|\cdot|$ denotes cardinality.
If $T$ is rooted and $v\in T$,
then the set of children of $v$ will be denoted $C_v$, and we let
$c_v=|C_v|$.
The {\it hook  of $v$\/}, $H_v$, is the set of
descendents of $v$ (including $v$ itself) with corresponding {\it hook
length\/} $h_v=|H_v|$.

A {\it binary tree\/}, $T$, is a rooted tree where every vertex has
either no children, a left child, a right child, or both children.
Let $\cB$ denote the family of all binary trees and 
let 
$$
\cB(n)=\{T\in \cB\ :\ |T|=n\}.
$$
For example, the trees in $\cB(3)$ are displayed in Figure~\ref{B3}.
In what follows, we will use similar notation for other families of
trees.  The formula of Han which we will prove is as follows.
\bth[Han]
For each positive integer $n$ we have
\beq
\label{H}
\sum_{T\in \cB(n)} \prod_{v\in T} \frac{1}{h_v 2^{h_v-1}} =\frac{1}{n!}.
\eeq
\eth



\bfi
$$
\begin{psmatrix}[rowsep=15pt,colsep=23pt]
\n{a1}&&      &\n{b1}&      &&      &\n{c1}&      &&      &\n{d1}&      &&      &\n{e1}&\\
\n{a2}&&      &\n{b2}&      &&\n{c2}&      &\n{c3}&&\n{d2}&      &\n{d3}&&\n{e2}&\n{e3}&\n{e4}\\
\n{a3}&&\n{b3}&      &\n{b4}&&\n{c4}&      &      &&      &      &\n{d4}&&      &\\
\n{a4}\\
m^3   &&      &\mm   &      &&      &\mm   &      &&      &\mm   &      &&      &{\binom m3}
\end{psmatrix}
\ncline{a1}{a4}
\ncline{b1}{b2}
\ncline{b2}{b3}
\ncline{b2}{b4}
\ncline{c1}{c2}
\ncline{c1}{c3}
\ncline{c2}{c4}
\ncline{d1}{d2}
\ncline{d1}{d3}
\ncline{d3}{d4}
\ncline{e1}{e2}
\ncline{e1}{e3}
\ncline{e1}{e4}
$$
\vspace{5pt}
\capt{The trees in $\cO(4)$ and their weights}
\label{O4}
\efi

Now consider finite ordered trees weighted by
$$
w(T)=\prod_{v\in T} {\binom m{ c_v}},
$$
where $m$ is a variable.  Let $\cO$ denote the family of weighted
ordered trees.  
The trees in $\cO(4)$ along with their weights are shown in Figure~\ref{O4}.
Then the identity of Yang we are considering is
equivalent to:
\bth[Yang]
For each positive integer $n$ we have
\beq
\label{Y}
\sum_{T\in \cO(n)}w(T) \prod_{v\in T} \frac{1}{h_v m^{h_v-1}} =\frac{1}{n!}.
\eeq
\eth

Some comments about this result are in order.  First of all, it is
remarkable because the right-hand side of the equation does not depend
on $m$.  Secondly, it implies Han's formula by letting $m=2$, since
then $w(T)$ is just the number of ways of turning an ordered tree into
a binary tree.  Finally, Yang's weighting was actually
$$
w(T)=\prod_{v\in T} {\binom m {c_v}} s^{c_v}= s^{|T|-1}\prod_{v\in T} 
{\binom m {c_v}},
$$
where $s$ is another parameter.  So one can recover Yang's equation by
multiplying both sides of~\ree{Y} by $s^{n-1}$.  Also, Yang assumes
that $m$ and $s$ are constants satisfying certain conditions, but it
is clearly not necessary to do so.

\bfi
$$
\begin{psmatrix}[rowsep=15pt,colsep=25pt]
      &      &      &&      &      &       &      &\n{t1}&      &      &      &      &&      &      \\
      &      &      &&      &\Tb=  &       &\n{t2}&      &\n{t3}&      &      &      &&      &      \\
      &      &      &&      &      &\n{t4} &\n{t5}&\n{t6}&\n{t7}&      &      &      &&      &      \\
      &      &      &&      &      &\vdots &\vdots&\vdots&\vdots&      &      &      &&      &      \\[20pt]
      &      &\n{a1}&&      &\n{b1}&       &      &\n{c1}&      &      &\n{d1}&      &&\n{e1}&      \\
      &\n{a2}&      &&\n{b2}&      &       &\n{c2}&      &      &\n{d2}&      &\n{d3}&&      &\n{e2}\\
\n{a3}&      &      &&\n{b3}&      &       &      &\n{c3}&      &      &      &      &&      &\n{e3}
\end{psmatrix}
\ncline{a1}{a3}
\ncline{b1}{b2}
\ncline{b2}{b3}
\ncline{c1}{c2}
\ncline{c2}{c3}
\ncline{d1}{d2}
\ncline{d1}{d3}
\ncline{e1}{e2}
\ncline{e2}{e3}
\ncline{t1}{t2}
\ncline{t1}{t3}
\ncline{t2}{t4}
\ncline{t2}{t5}
\ncline{t2}{t6}
\ncline{t3}{t7}
$$
\vspace{5pt}
\capt{The subtrees in $\cTb(3)$ for the given $\Tb$}
\label{T3}
\efi


For our second generalization of equation~\ree{H}, consider a fixed,
infinite, ordered tree $\Tb$ such that $0<\cb_v<\infty$ for all $v\in
\Tb$.  We are using $\cb_v$ for the number of children of $v$ to
emphasize that this is being calculated in $\Tb$.
Let $\cTb$ be the family of all subtrees of $\Tb$ which contain the root of
$\Tb$.  Since $\Tb$ is 
ordered, its vertices are distinguishable, i.e., $V(\Tb)$ is a set
rather than a multiset.  So we consider two subtrees $T,T'$ to be
equal if and only if $V(T)=V(T')$.  For example, $\cTb=\cB$ if we
let $\Tb$ be the tree with $\cb_v=2$ for all $v\in \Tb$.  As another
illustration, Figure~\ref{T3} shows part of one possible $\Tb$ and the
corresponding trees in $\cTb(3)$.
\bth
For each positive integer $n$ and each tree $\Tb$ satisfying the above
restrictions, we have
\beq
\label{S}
\sum_{T\in \cTb(n)} \prod_{v\in T} \frac{1}{h_v \cb_v^{h_v-1}}=\frac{1}{n!}.
\eeq
\eth

\section{The algorithm}
\label{a}

For any rooted tree $T$, an {\it increasing labeling of $T$\/} is a
bijection 
$$
\ell:T\ra\{1,2,\ldots,|T|\}
$$ 
such that for any $v\in T$ and
any $w\in C_v$ we have $\ell(v)<\ell(w)$.  We will often let $L=L(T)$
stand for an increasing labeling of $T$ viewed as $T$ with the labels
attached to its vertices.  Similarly, we will write $L(\cF)$ for the
family of all increasing labelings of trees in the family $\cF$.
Let $f^T$ be the number of
increasing labelings $L(T)$ where $T$ has distinguishable vertices.
The following hook length formula for $f^T$ is well known and easy to
prove
\beq
\label{fT}
f^T=\frac{n!}{\prod_{v\in T} h_v}.
\eeq
So if we multiply any of the three identities from the previous
section by $n!$, we obtain a sum of the form
$$
\sum_{T\in\cF(n)} f^T \pi(T) = 1
$$
where $\cF$ is a family of trees and $\pi(T)$ is a product.
We wish to interpret $\pi(T)$ as the
probability of obtaining an increasing labeling $L$ of $T$ for an
appropriate probability distribution on $L(\cF(n))$.  The identity
will then follow since
$$
1=\sum_{L\in L(\cF(n))} \Prob(L) 
= \sum_{T\in\cF(n)} \sum_{L=L(T)} \pi(T)
= \sum_{T\in\cF(n)} f^T \pi(T).
$$
Note that $\Prob(L)$ will depend on $T$ where $L=L(T)$, but not on the
specific labeling of $T$.

The probability distribution will be obtained by
specifying the parameters in the following basic algorithm which takes
as input a positive integer $n$ and a family of trees $\cF$ and
outputs a labeling $L$ of some $T\in\cF(n)$.  
\ben
\item Let $L$ consist of a single root labeled $1$.
\item While $|L|<n$, consider all possible leaves $v$ one could add to
  $L$ and still stay in $L(\cF)$.  Pick one such leaf, label
  it $|L|+1$, and add it to $L$ with probability $\Prob(v,L)$. 
\item Output $L$.
\een
It will be convenient to also use the notation $\Prob(v,L)$ when 
$v\in L$.  In that case, it should be interpreted as $\Prob(v,L')$
where $L'$ is subtree of $L$ induced by those vertices with labels
less than $\ell(v)$.

To finish the proofs, we just need to specify for each of the three
families what the probabilities $\Prob(v,L)$ are, and prove that they
describe a probality distribution such that all increasing labelings $L$
of a given tree are equally likely with the common value being 
$$
\Prob(L)=\prod_{v\in L} \Prob(v,L) =\pi(T).
$$


\begin{proof}[Proof of\/ \em\ree{H}]
Given a tree $T$ rooted at $r$ and $v\in T$ we let $P_v$ be the unique
$r\hor v$ path.  The {\it depth of $v$\/}, $d_v$, is the length of $P_v$. 
In the algorithm, let
$$
\Prob(v,L)=\frac{1}{2^{d_v}}.
$$
For example, Figure~\ref{ProbB} shows one of the trees $T$ in $\cB(3)$
along with these probabilities for each possible leaf $v$ which could
be added to $T$.  To further distinguish such leaves from the nodes of $T$,
the corresponding edges are dashed.

\bfi
$$
\begin{psmatrix}[rowsep=10pt,colsep=30pt]
      &       & \n{a} &       \\
      &       &       &       \\
      & \n{b} &       & \n{c} \\
      &\st{20}&       & 1/2   \\
\n{d} &       & \n{e} &       \\
 1/4  &       &       &       \\
      & \n{f} &       & \n{g} \\
      & 1/8   &       & 1/8      
\end{psmatrix}
\ncline{a}{b}
\ncline[linestyle=dashed]{a}{c}
\ncline[linestyle=dashed]{b}{d}
\ncline{b}{e}
\ncline[linestyle=dashed]{e}{f}
\ncline[linestyle=dashed]{e}{g}
$$
\vspace{5pt}
\capt{A tree in  $\cB(3)$ and the probabilities of its additional leaves}
\label{ProbB}
\efi





We first need a lemma which will be used in all three proofs.  So we
will state it in general terms.
\ble
\label{F}
For each of the three families $\cF$ under consideration and
for each $L\in L(\cF)$ we have
\beq
\label{sumv}
\sum_{v} \Prob(v,L)=1
\eeq
where the sum is over all leaves $v$ which could be added to $L$.
\ele

\medskip\noindent
{\it Proof of the lemma for $\cF=\cB$.}  We induct on $|L|$ where
the base case is easy to do.  Given $L$, let $w$ be the leaf of $L$
such that $\ell(w)=|L|$ and let $L'=L-w$.
Then the
terms in the sum for $L'$ are the same as those in the sum for $L$
except that the summand $1/2^{d_w}$ in the former has been replaced by 
$1/2^{d_w+1}+1/2^{d_w+1}$.  Since these two expressions are equal, so
are the sums, and we are done by induction.\qed

\medskip
Next we need to verify that for $L=L(T)$ we have $\Prob(L)=\pi(T)$, i.e.,
$$
\Prob(L)=\prod_{v\in T}\frac{1}{2^{h_v-1}}
$$
Again, let $\ell(w)=|L|$ and $L'=L-w$.  Then the hook lengths in $L$
are the same as those in $L'$ except that the $d_w$ vertices on
the path $P_w-w$ 
have all been increased by one.  Note also that $w$ itself does not
contribute to the product above since $1/2^{h_w-1}=1$.  So, by induction,
\beq
\label{B}
\Prob(L) =\Prob(w,L')\Prob(L')
=\frac{1}{2^{d_w}}\prod_{v'\in T'}\frac{1}{2^{h_{v'}-1}}
=\prod_{v\in T}\frac{1}{2^{h_v-1}}.
\eeq

There remains to show that $\Prob(L)$ defines a probability
distribution.  But using the Lemma and induction as well as our usual
notation:
\bea
\sum_{L\in L(\cB(n))} \Prob(L)
&=&\dil\sum_{L\in L(\cB(n))} \Prob(w,L')\Prob(L')\\[10pt]
&=&\dil\sum_{L'\in L(\cB(n-1))} \Prob(L') \sum_w \Prob(w,L')\\[10pt]
&=&\dil\sum_{L'\in L(\cB(n-1))} \Prob(L')\\[10pt]
&=&1.
\eea
This finishes the proof of~\ree{H}.\end{proof}

Note that the proof that $\Prob(L)$ forms a probability distribution
only depends on Lemma~\ref{F}.  So in the next two proofs, we will
skip this step.

\begin{proof}[Proof of\/ \em\ree{Y}]   
Note that the left-hand side of~\ree{Y} is a
rational function of $m$, so clearing denominators gives a polynomial
equation.  Thus it suffices to prove that this identity holds for
infinitely many values of $m$.  We will provide a proof for all real numbers
$m\ge M$ where $M$ is chosen sufficiently large such that 
$0\le \Prob(v,L)\le 1$ for all $v\in L\in L(\cO(n))$.  This will be
possible because $\Prob(v,L)$ will be asymptotic to, but smaller than
or equal to, $1/m^{d_v-1}$.   Specifically, let
$$
\Prob(v,L)=\frac{m-c_p}{(c_p+1)m^{d_v}}
$$
where $p$ is the parent of $v$.  Remember that, according to our
convention following the description of the algorithm, $c_p$ is
calculated in the subtree of $L$ induced by those vertices with labels
less that $\ell(v)$.  In particular, $c_p$ does not count $v$ itself.
Figure~\ref{ProbO} displays a tree of $\cO(4)$ and the probabilities
of the leaves which can be added to it.


\bfi
$$
\begin{psmatrix}[rowsep=10pt,colsep=50pt]
      &       & \n{a} &       &        \\
      &       &       &       &        \\
      &       &       &       &        \\
\n{b} & \n{c} & \n{d} & \n{e} & \n{f}  \\
\fone &       & \fone &       & \fone  \\
      &       &       &       &        \\
      & \n{g} & \n{h} & \n{i} & \n{j}  \\
      & \fthr & \ftwo &       & \ftwo  \\
      &       &       &       &        \\
      &       &       & \n{k} &        \\
      &       &       & \ffou &      
\end{psmatrix}
\ncline[linestyle=dashed]{a}{b}
\ncline{a}{c}
\ncline[linestyle=dashed]{a}{d}
\ncline{a}{e}
\ncline[linestyle=dashed]{a}{f}
\ncline[linestyle=dashed]{c}{g}
\ncline[linestyle=dashed]{e}{h}
\ncline{e}{i}
\ncline[linestyle=dashed]{e}{j}
\ncline[linestyle=dashed]{i}{k}
$$
\vspace{5pt}
\capt{A tree in  $\cO(4)$ and the probabilities of its additional leaves}
\label{ProbO}
\efi



Our first order of business will be to prove Lemma~\ref{F} in this
setting.

\medskip\noindent
{\it Proof of the Lemma for $\cF=\cO$.}  As before, we induct on
$L$, keeping the notation the same as the first proof.  We also let
$p$ be the parent of $w$ and write $p'$ if we are considering $p$ as a
vertex of $L'$. So $c_p=c_{p'}+1$ and the terms in the sum for $L'$
corresponding to the $c_{p'}+1$ possible children which could be added to
$p'$ give a total of
$$
(c_{p'}+1)\frac{m-c_{p'}}{(c_{p'}+1)m^{d_w}}=\frac{m-c_p+1}{m^{d_w}}.
$$
In the sum for $L$, these terms are replaced by $c_p+1$ summands for
children of $p$ and one for a child of $w$, giving
$$
(c_p+1)\frac{m-c_p}{(c_p+1)m^{d_w}}+\frac{m}{m^{d_w+1}}=\frac{m-c_p+1}{m^{d_w}}.
$$
Since these two contributions are the same and all other terms in two
sums match up, we are done.\qed
\medskip


We next need to show that $\Prob(L)=\pi(T)$ for $\cF=\cO$.  Keeping
our usual notation we have $\Prob(L)/\Prob(L')=\Prob(w,L')$.  So the
desired equality will follow by induction, the reasoning applied to
obtain~\ree{B}, and the computation
$$
\frac{\pi(T)}{\pi(T')}=
\frac{\prod_{v\in T}{\binom m {c_v}}/m^{h_v-1}}{\prod_{v'\in T'}
{\binom m {c_{v'}}}/m^{h_{v'}-1}}
=\frac{{\binom m {c_p}}{\binom m {c_w}}}{{\binom m {c_{p'}}} m^{d_w}}
=\frac{m-c_{p'}}{(c_{p'}+1)m^{d_w}}=\Prob(v,L').
$$
This completes the proof for $\cO$.\end{proof}



\bfi
$$
\begin{psmatrix}[rowsep=10pt,colsep=30pt]
       &      &\n{t1}&      \\
       &      &      &      \\
       &\n{t2}&      &\n{t3}\\
       &      &      &      \\
\n{t4} &\n{t5}&\n{t6}&\n{t7}\\
\tone  &\tone &\tone &\ttwo
\end{psmatrix}
\ncline{t1}{t2}
\ncline{t1}{t3}
\ncline[linestyle=dashed]{t2}{t4}
\ncline[linestyle=dashed]{t2}{t5}
\ncline[linestyle=dashed]{t2}{t6}
\ncline[linestyle=dashed]{t3}{t7}
$$
\vspace{5pt}
\capt{A subtree in $\cTb(3)$ and additional leaves}
\label{ProbT}
\efi

\begin{proof}[Proof of\/ \em\ree{S}]  
For this case, we proceed as usual, but letting
$$
\Prob(v,L)=\prod_{x\in P_v-v} \frac{1}{\cb_x}.
$$
Figure~\ref{ProbT} gives an example using a tree from $\cTb(3)$ where
$\cTb$ is as in Figure~\ref{T3}.

\medskip\noindent
{\it Proof of the Lemma for $\cF=\cTb$.} Now in passing from the sum
for $L'$ to the sum for $L$, a single term 
$\prod_{x\in P_w-w} 1/\cb_x$ has been replaced by $\cb_w$ terms all
equal to $\prod_{x\in P_w} 1/\cb_x$.  Clearly this does not change the
sum.\qed

\medskip
The proof that $\Prob(L)=\pi(t)$ is just like the one for $\cB$ except
that the hook length powers of 2 are replaced by powers of $\cb_x$.
So we are done with the case of $\cTb$.\end{proof}


\section{An open problem}

As remarked in the introduction, Han actually proved two formulas
in~\cite{han:nhl}, both having hook lengths as exponents.  We have
unable to give a probabilistic proof of the second one.  But will
indicate how one might go in the hopes that someone else may be
able to push it through.

Call a binary tree {\it complete\/} if every vertex has 0 or 2
children.  Given a binary tree $T$ on $n$ nodes it has 
{\it completion $\Tha$\/} which is the complete binary tree obtained from $T$
by adding all $n+1$ possible leaves.  If $T$ is the tree with the
solid edges in Figure~\ref{ProbB} then $\Tha$ is the tree which also
includes the dashed edges.
It is not hard to show
using~\ree{fT} that
\beq
\label{fTh}
f^{\Tha}=\frac{(2n+1)!}{\prod_{v\in T} (2h_v+1)}.
\eeq

Han's second formula is
$$
\sum_{T\in\cB(n)}\prod_{v\in T} \frac{1}{(2h_v+1)2^{2h_v-1}}=\frac{1}{(2n+1)!}.
$$
Using~\ree{fTh}, this can be rewritten as
$$
\sum_{T\in\cB(n)}f^{\Tha}\prod_{v\in T} \frac{1}{2^{2h_v-1}}=1.
$$
It would be very interesting to find a probability distribution on increasing labelings of
complete trees $\Tha$ whose probabilities are given by $\prod_{v\in T}
1/2^{2h_v-1}$.  Once this is done, similar ideas should prove the
generalization to $\cO$ due to Yang~\cite{yan:ghh}.  It is not clear
how to generalize Han's formula to the $\cTb$ case, but would be
interesting to do if possible.






\bibliographystyle{acm}

\begin{thebibliography}{1}

\bibitem{frt:hgs}
{\sc Frame, J.~S., Robinson, G. d.~B., and Thrall, R.~M.}
\newblock The hook graphs of the symmetric group.
\newblock {\em Canad. J. Math. 6\/} (1954), 316--325.

\bibitem{gnw:ppf}
{\sc Greene, C., Nijenhuis, A., and Wilf, H.~S.}
\newblock A probabilistic proof of a formula for the number of {Y}oung tableaux
  of a given shape.
\newblock {\em Adv. in Math. 31}, 1 (1979), 104--109.

\bibitem{gnw:apm}
{\sc Greene, C., Nijenhuis, A., and Wilf, H.~S.}
\newblock Another probabilistic method in the theory of {Y}oung tableaux.
\newblock {\em J. Combin. Theory Ser. A 37}, 2 (1984), 127--135.

\bibitem{han:nhl}
{\sc Han, G.-N.}
\newblock New hook length formulas for binary trees.
\newblock {\em Combinatorica},
\newblock to appear, preprint {\texttt{ar$\chi$iv:0804.3638}}.

\bibitem{han:agp}
{\sc Han, G.-N.}
\newblock Yet another generalization of {P}ostnikov's hook formula for binary
  trees.
\newblock {\em SIAM J. Discrete Math.},  23 (2009), 661--664. 

\bibitem{pos:pab}
{\sc Postnikov, A.}
\newblock Permutohedra, associahedra, and beyond.
\newblock {\em Internat. Math. Res. Not.}, 2009, Article~rnn153v1-rnn153.

\bibitem{sag:srs}
{\sc Sagan, B.}
\newblock On selecting a random shifted {Y}oung tableau.
\newblock {\em J. Algorithms 1}, 3 (1980), 213--234.

\bibitem{sy:pat}
{\sc Sagan, B.~E., and Yeh, Y.~N.}
\newblock Probabilistic algorithms for trees.
\newblock {\em Fibonacci Quart. 27}, 3 (1989), 201--208.

\bibitem{yan:ghh}
{\sc Yang, L. L.~M.}
\newblock Generalizations of {H}an's hook length identities.
\newblock Preprint {\texttt{ar$\chi$iv:0805.0109}}.

\end{thebibliography}



\end{document}