%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|