%%%% Tex file to be used with  plain  and no other format
%%%% for the paper "Random permutations and Bernoulli sequences"
%%%% by   Dominique Foata
%%%%  10 pages of output

\magnification=1200

\font\tenpc=cmcsc10
% Charge des fontes de 8 et 6 points :
\font\eightrm=cmr8
\font\eighti=cmmi8
\font\eightsy=cmsy8
\font\eightbf=cmbx8
\font\eighttt=cmtt8
\font\eightit=cmti8
\font\eightsl=cmsl8
\font\sixrm=cmr6
\font\sixi=cmmi6
\font\sixsy=cmsy6
\font\sixbf=cmbx6

\skewchar\eighti='177 \skewchar\sixi='177
\skewchar\eightsy='60 \skewchar\sixsy='60

% Chargement des fontes AMS

\font\tengoth=eufm10
\font\tenbboard=msbm10
\font\eightgoth=eufm10 at 8pt
\font\eightbboard=msbm8
\font\sevengoth=eufm7
\font\sevenbboard=msbm7
\font\sixgoth=eufm6
\font\fivegoth=eufm5

\newfam\gothfam
\newfam\bboardfam

\catcode`\@=11

\def\raggedbottom{\topskip 10pt plus 36pt
\r@ggedbottomtrue}
\def\pc#1#2|{{\bigf@ntpc #1\penalty
\@MM\hskip\z@skip\smallf@ntpc #2}}

\def\tenpoint{%
  \textfont0=\tenrm \scriptfont0=\sevenrm \scriptscriptfont0=\fiverm
  \def\rm{\fam\z@\tenrm}%
  \textfont1=\teni \scriptfont1=\seveni \scriptscriptfont1=\fivei
  \def\oldstyle{\fam\@ne\teni}%
  \textfont2=\tensy \scriptfont2=\sevensy \scriptscriptfont2=\fivesy
  \textfont\gothfam=\tengoth \scriptfont\gothfam=\sevengoth
  \scriptscriptfont\gothfam=\fivegoth
  \def\goth{\fam\gothfam\tengoth}%
  \textfont\bboardfam=\tenbboard \scriptfont\bboardfam=\sevenbboard
  \scriptscriptfont\bboardfam=\sevenbboard
  \def\bboard{\fam\bboardfam}%
  \textfont\itfam=\tenit
  \def\it{\fam\itfam\tenit}%
  \textfont\slfam=\tensl
  \def\sl{\fam\slfam\tensl}%
  \textfont\bffam=\tenbf \scriptfont\bffam=\sevenbf
  \scriptscriptfont\bffam=\fivebf
  \def\bf{\fam\bffam\tenbf}%
  \textfont\ttfam=\tentt
  \def\tt{\fam\ttfam\tentt}%
  \abovedisplayskip=12pt plus 3pt minus 9pt
  \abovedisplayshortskip=0pt plus 3pt
  \belowdisplayskip=12pt plus 3pt minus 9pt
  \belowdisplayshortskip=7pt plus 3pt minus 4pt
  \smallskipamount=3pt plus 1pt minus 1pt
  \medskipamount=6pt plus 2pt minus 2pt
  \bigskipamount=12pt plus 4pt minus 4pt
  \normalbaselineskip=12pt
  \setbox\strutbox=\hbox{\vrule height8.5pt depth3.5pt width0pt}%
  \let\bigf@ntpc=\tenrm \let\smallf@ntpc=\sevenrm
  \let\petcap=\tenpc
  \normalbaselines\rm}
\def\eightpoint{%
  \textfont0=\eightrm \scriptfont0=\sixrm \scriptscriptfont0=\fiverm
  \def\rm{\fam\z@\eightrm}%
  \textfont1=\eighti \scriptfont1=\sixi \scriptscriptfont1=\fivei
  \def\oldstyle{\fam\@ne\eighti}%
  \textfont2=\eightsy \scriptfont2=\sixsy \scriptscriptfont2=\fivesy
  \textfont\gothfam=\eightgoth \scriptfont\gothfam=\sixgoth
  \scriptscriptfont\gothfam=\fivegoth
  \def\goth{\fam\gothfam\eightgoth}%
  \textfont\bboardfam=\eightbboard \scriptfont\bboardfam=\sevenbboard
  \scriptscriptfont\bboardfam=\sevenbboard
  \def\bboard{\fam\bboardfam}%
  \textfont\itfam=\eightit
  \def\it{\fam\itfam\eightit}%
  \textfont\slfam=\eightsl
  \def\sl{\fam\slfam\eightsl}%
  \textfont\bffam=\eightbf \scriptfont\bffam=\sixbf
  \scriptscriptfont\bffam=\fivebf
  \def\bf{\fam\bffam\eightbf}%
  \textfont\ttfam=\eighttt
  \def\tt{\fam\ttfam\eighttt}%
  \abovedisplayskip=9pt plus 2pt minus 6pt
  \abovedisplayshortskip=0pt plus 2pt
  \belowdisplayskip=9pt plus 2pt minus 6pt
  \belowdisplayshortskip=5pt plus 2pt minus 3pt
  \smallskipamount=2pt plus 1pt minus 1pt
  \medskipamount=4pt plus 2pt minus 1pt
  \bigskipamount=9pt plus 3pt minus 3pt
  \normalbaselineskip=9pt
  \setbox\strutbox=\hbox{\vrule height7pt depth2pt width0pt}%
  \let\bigf@ntpc=\eightrm \let\smallf@ntpc=\sixrm
  \normalbaselines\rm}

\let\bb=\bboard

\tenpoint
\frenchspacing
%���������������������� format de sortie �����������������

\newif\ifpagetitre
\newtoks\auteurcourant \auteurcourant={\hfil}
\newtoks\titrecourant \titrecourant={\hfil}

\def\appeln@te{}
\def\vfootnote#1{\def\@parameter{#1}\insert\footins\bgroup\eightpoint
  \interlinepenalty\interfootnotelinepenalty
  \splittopskip\ht\strutbox % top baseline for broken footnotes
  \splitmaxdepth\dp\strutbox \floatingpenalty\@MM
  \leftskip\z@skip \rightskip\z@skip
  \ifx\appeln@te\@parameter\indent \else{\noindent #1\ }\fi
  \footstrut\futurelet\next\fo@t}

\pretolerance=500 \tolerance=1000 \brokenpenalty=5000
\newdimen\hmargehaute \hmargehaute=0cm
\newdimen\lpage \lpage=13.3cm
\newdimen\hpage \hpage=20cm
\newdimen\lmargeext \lmargeext=1cm
\hsize=11.25cm
\vsize=18cm
\parskip 0pt
\parindent=12pt

\def\margehaute{\vbox to \hmargehaute{\vss}}%
\def\margebasse{\vss}

\output{\shipout\vbox to \hpage{\margehaute\nointerlineskip
  \corpsdepage\margebasse}
  \advancepageno \global\pagetitrefalse
  \ifnum\outputpenalty>-20000 \else\dosupereject\fi}

\def\corpsdepage{\hbox to \lpage{\hss\pagetexte\hskip\lmargeext}}
\def\pagetexte{\vbox{\makeheadline\pagebody\makefootline}}
\headline={\ifpagetitre\titleheadline \else
  \ifodd\pageno\rightheadline \else\leftheadline\fi\fi}
\def\leftheadline{\eightpoint\hfil\the\auteurcourant\hfil}
\def\rightheadline{\eightpoint\hfil\the\titrecourant\hfil}
\def\titleheadline{\hfill}
\pagetitretrue

\def\footnoterule{\kern-6\p@
  \hrule width 2truein \kern 5.6\p@} % the \hrule is .4pt high



\let\rmpc=\sevenrm
\def\pd#1#2 {\pc#1#2| }

\def\pointir{\discretionary{.}{}{.\kern.35em---\kern.7em}\nobreak
\hskip 0em plus .3em minus .4em }

\def\resume#1{\vbox{\eightpoint \pc R\'ESUM\'E|\pointir #1}}
\def\abstract#1{\vbox{\eightpoint \pc ABSTRACT|\pointir #1}}

\def\titre#1|{\message{#1}
              \par\vskip 30pt plus 24pt minus 3pt\penalty -1000
              \vskip 0pt plus -24pt minus 3pt\penalty -1000
              \centerline{\bf #1}
              \vskip 5pt
              \penalty 10000 }

\def\section#1|{\par\vskip .3cm
                {\bf #1}\pointir}

\def\ssection#1|{\par\vskip .2cm
                {\it #1}\pointir}

\long\def\th#1|#2\finth{\par\medskip
              {\petcap #1\pointir}{\it #2}\par\smallskip}

\long\def\tha#1|#2\fintha{\par\medskip
                    {\petcap #1.}\par\nobreak{\it #2}\par\smallskip}
\def\cf{{\it cf}}

\def\rem#1|{\par\medskip
            {{\it #1}\pointir}}

\def\rema#1|{\par\medskip
             {{\it #1.}\par\nobreak }}

%
\def\ieme{\raise 1ex\hbox{\pc{}i\`eme|}}
\def\omini{\raise 1ex\hbox{\pc{}o|}}
\def\emini{\raise 1ex\hbox{\pc{}e|}}
\def\ermini{\raise 1ex\hbox{\pc{}er|}}
\def\remini{\raise 1ex\hbox{\pc{}re|}}

%reference pour un article :
\def\article#1|#2|#3|#4|#5|#6|#7|
    {{\leftskip=7mm\noindent
     \hangindent=2mm\hangafter=1
     \llap{[#1]\hskip.35em}{#2}\pointir
     #3, {\sl #4}, vol.\nobreak\ {\bf #5}, {\oldstyle #6},
     p.\nobreak\ #7.\par}}
%reference pour un livre :
\def\livre#1|#2|#3|#4|
    {{\leftskip=7mm\noindent
    \hangindent=2mm\hangafter=1
    \llap{[#1]\hskip.35em}{#2}\pointir
    {\sl #3}\pointir #4.\par}}
%reference complementaire :
\def\divers#1|#2|#3|
    {{\leftskip=7mm\noindent
    \hangindent=2mm\hangafter=1
     \llap{[#1]\hskip.35em}{#2}\pointir
     #3.\par}}
%
\mathchardef\conj="0365
\def\dem{\par{\it D\'emonstration}\pointir}
\def\qed{\quad\raise -2pt\hbox{\vrule\vbox to 10pt{\hrule width 4pt
\vfill\hrule}\vrule}}

\def\virg{\raise 2pt\hbox{,}}   % virgule apr�s une fraction

\def\cqfd{\penalty 500 \hbox{\qed}\par\smallskip}

\long\def\entourer#1{\hbox{\vrule\vbox{\hrule\hbox{\kern15pt\vbox{\kern5pt
{#1}\kern5pt}\kern15pt}\hrule}\vrule}}
\def\\S {\vskip 5pt\hskip .5cm plus .1cm minus .1cm\relax}

%les differents retraits, voir aussi \item
\def\enonce#1|#2\finenonce{{\par\leftskip=36pt
\noindent\hbox to 0pt{\kern-\leftskip#1\hfill}{#2}\par}}

\def\senonce#1|#2\finsenonce{{\par\leftskip=36pt
\noindent\hbox to 0pt{\kern-24pt #1\hfill}{#2}\par}}

\def\ssenonce#1|#2\finssenonce{{\par\leftskip=48pt
\noindent\hbox to 0pt{\kern-24pt #1\hfill}{#2}\par}}

\def\decale#1|{\par\noindent\hskip 28pt\llap{#1}\kern 5pt}
\def\decaledecale#1|{\par\noindent\hskip 34pt\llap{#1}\kern 5pt}
% pour les titres en deux lignes et les sections sans point-tiret :
\def\titrea#1|#2|{\message{#1 #2}
  \par\vskip.5cm plus .1cm minus .1cm\penalty -1000
  \centerline{\bf #1}
  \centerline{\bf #2}
  \vskip 5pt
  \penalty 10000 }
\def\sectiona#1|{\par\vskip .3cm
  {\bf #1.}
  \par\nobreak\vskip 3pt }
\def\ssectiona#1|{\par\vskip .2cm
  {\it #1.}
  \par\nobreak\vskip 2pt }

\def\rest#1{\ifinner\setbox1=\hbox{$\textstyle{#1}$}
            \else\setbox1=\hbox{$\displaystyle{#1}$}\fi
            \dimen1=\ht1
            \advance\dimen1 by\dp1
            \divide\dimen1 by 2
            \box1\lower 2pt\hbox{$\left|\vbox to\dimen1{}\right.$}}

\def\displaylinesno#1{\displ@y\halign{
\hbox to\displaywidth{$\@lign\hfil\displaystyle##\hfil$}&
\llap{$##$}\crcr#1\crcr}}

\def\ldisplaylinesno#1{\displ@y\halign{ 
\hbox to\displaywidth{$\@lign\hfil\displaystyle##\hfil$}&
\kern-\displaywidth\rlap{$##$}\tabskip\displaywidth\crcr#1\crcr}}

\def\Eqalign#1{\null\,\vcenter{\openup\jot\m@th\ialign{
\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil
&&\quad\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil
\crcr#1\crcr}}\,}


% matrice justifi\'ee \`a droite : \hfil coef dans chaque ligne

\def\matrixd#1{\null \,\vcenter {\normalbaselines \m@th
\ialign {\hfil $##$&&\quad \hfil $##$\crcr
\mathstrut \crcr \noalign {\kern -\baselineskip } #1\crcr
\mathstrut \crcr \noalign {\kern -\baselineskip }}}\,}

\def\pmatrixd#1{\left(\matrixd{#1}\right)}

\def\lfq{\leavevmode\raise.3ex\hbox{$\scriptscriptstyle
\langle\!\langle$}\thinspace}
\def\rfq{\leavevmode\thinspace\raise.3ex\hbox{$\scriptscriptstyle
\rangle\!\rangle$}}


\catcode`\@=12

%%%%%%%%%%%%%%%%%% commands for grille.tex %%%%%%%%

\def\Grille{\setbox13=\vbox to 5mm{\hrule width 110mm\vfill}
\setbox13=\vbox{\offinterlineskip
   \copy13\copy13\copy13\copy13\copy13\copy13\copy13\copy13
   \copy13\copy13\copy13\copy13\box13\hrule width 110mm}
\setbox14=\hbox to 5mm{\vrule height 65mm\hfill}
\setbox14=\hbox{\copy14\copy14\copy14\copy14\copy14\copy14
   \copy14\copy14\copy14\copy14\copy14\copy14\copy14\copy14
   \copy14\copy14\copy14\copy14\copy14\copy14\copy14\copy14\box14}
\ht14=0pt\dp14=0pt\wd14=0pt
\setbox13=\vbox to 0pt{\vss\box13\offinterlineskip\box14}
\wd13=0pt\box13}

\def\grille{\noalign{\nointerlineskip\Grille\nointerlineskip}}

%������������������������������������������������������������������

\def\fleche(#1,#2)\dir(#3,#4)\long#5{%
\noalign{\nointerlineskip\leftput(#1,#2){\vector(#3,#4){#5}}\nointerlineskip}}

%������������������������������������������������������������������

\def\diagram#1{\def\normalbaselines{\baselineskip=0pt\lineskip=5pt}
\matrix{#1}}

\def\hfl#1#2#3{\smash{\mathop{\hbox to#3{\rightarrowfill}}\limits
^{\scriptstyle#1}_{\scriptstyle#2}}}

\def\gfl#1#2#3{\smash{\mathop{\hbox to#3{\leftarrowfill}}\limits
^{\scriptstyle#1}_{\scriptstyle#2}}}

\def\vfl#1#2#3{\llap{$\scriptstyle #1$}
\left\downarrow\vbox to#3{}\right.\rlap{$\scriptstyle #2$}}

%������������������������������������������������������������������


 \message{`lline' & `vector' macros from LaTeX}
 \catcode`@=11
\def\{{\relax\ifmmode\lbrace\else$\lbrace$\fi}
\def\}{\relax\ifmmode\rbrace\else$\rbrace$\fi}
\def\newcount{\alloc@0\count\countdef\insc@unt}
\def\newdimen{\alloc@1\dimen\dimendef\insc@unt}
\def\newwrite{\alloc@7\write\chardef\sixt@@n}

\newwrite\@unused
\newcount\@tempcnta
\newcount\@tempcntb
\newdimen\@tempdima
\newdimen\@tempdimb
\newbox\@tempboxa

\def\@spaces{\space\space\space\space}
\def\@whilenoop#1{}
\def\@whiledim#1\do #2{\ifdim #1\relax#2\@iwhiledim{#1\relax#2}\fi}
\def\@iwhiledim#1{\ifdim #1\let\@nextwhile=\@iwhiledim
        \else\let\@nextwhile=\@whilenoop\fi\@nextwhile{#1}}
\def\@badlinearg{\@latexerr{Bad \string\line\space or \string\vector
   \space argument}}
\def\@latexerr#1#2{\begingroup
\edef\@tempc{#2}\expandafter\errhelp\expandafter{\@tempc}%
%% error help message pieces.
\def\@eha{Your command was ignored.
^^JType \space I <command> <return> \space to replace it
  with another command,^^Jor \space <return> \space to continue without it.}
\def\@ehb{You've lost some text. \space \@ehc}
\def\@ehc{Try typing \space <return>
  \space to proceed.^^JIf that doesn't work, type \space X <return> \space to
  quit.}
\def\@ehd{You're in trouble here.  \space\@ehc}

\typeout{LaTeX error. \space See LaTeX manual for explanation.^^J
 \space\@spaces\@spaces\@spaces Type \space H <return> \space for
 immediate help.}\errmessage{#1}\endgroup}
\def\typeout#1{{\let\protect\string\immediate\write\@unused{#1}}}

% line & circle fonts
\font\tenln    = line10
\font\tenlnw   = linew10
%\font\tencirc  = circle10
%\font\tencircw = circlew10


\newdimen\@wholewidth
\newdimen\@halfwidth
\newdimen\unitlength 

\unitlength =1pt

%\newbox\@picbox
%\newdimen\@picht

\def\thinlines{\let\@linefnt\tenln \let\@circlefnt\tencirc
  \@wholewidth\fontdimen8\tenln \@halfwidth .5\@wholewidth}
\def\thicklines{\let\@linefnt\tenlnw \let\@circlefnt\tencircw
  \@wholewidth\fontdimen8\tenlnw \@halfwidth .5\@wholewidth}

\def\linethickness#1{\@wholewidth #1\relax \@halfwidth .5\@wholewidth}



\newif\if@negarg

\def\lline(#1,#2)#3{\@xarg #1\relax \@yarg #2\relax
\@linelen=#3\unitlength
\ifnum\@xarg =0 \@vline
  \else \ifnum\@yarg =0 \@hline \else \@sline\fi
\fi}

\def\@sline{\ifnum\@xarg< 0 \@negargtrue \@xarg -\@xarg \@yyarg -\@yarg
  \else \@negargfalse \@yyarg \@yarg \fi
\ifnum \@yyarg >0 \@tempcnta\@yyarg \else \@tempcnta -\@yyarg \fi
\ifnum\@tempcnta>6 \@badlinearg\@tempcnta0 \fi
\setbox\@linechar\hbox{\@linefnt\@getlinechar(\@xarg,\@yyarg)}%
\ifnum \@yarg >0 \let\@upordown\raise \@clnht\z@
   \else\let\@upordown\lower \@clnht \ht\@linechar\fi
\@clnwd=\wd\@linechar
\if@negarg \hskip -\wd\@linechar \def\@tempa{\hskip -2\wd\@linechar}\else
     \let\@tempa\relax \fi
\@whiledim \@clnwd <\@linelen \do
  {\@upordown\@clnht\copy\@linechar
   \@tempa
   \advance\@clnht \ht\@linechar
   \advance\@clnwd \wd\@linechar}%
\advance\@clnht -\ht\@linechar
\advance\@clnwd -\wd\@linechar
\@tempdima\@linelen\advance\@tempdima -\@clnwd
\@tempdimb\@tempdima\advance\@tempdimb -\wd\@linechar
\if@negarg \hskip -\@tempdimb \else \hskip \@tempdimb \fi
\multiply\@tempdima \@m
\@tempcnta \@tempdima \@tempdima \wd\@linechar \divide\@tempcnta \@tempdima
\@tempdima \ht\@linechar \multiply\@tempdima \@tempcnta
\divide\@tempdima \@m
\advance\@clnht \@tempdima
\ifdim \@linelen <\wd\@linechar
   \hskip \wd\@linechar
  \else\@upordown\@clnht\copy\@linechar\fi}

%\def\@hline{\ifnum \@xarg <0 \hskip -\@linelen \fi
%\vrule \@height \@halfwidth \@depth \@halfwidth \@width
%\@linelen \ifnum \@xarg <0 \hskip -\@linelen \fi}


\def\@hline{\ifnum \@xarg <0 \hskip -\@linelen \fi
\vrule height \@halfwidth depth \@halfwidth width \@linelen
\ifnum \@xarg <0 \hskip -\@linelen \fi}

\def\@getlinechar(#1,#2){\@tempcnta#1\relax\multiply\@tempcnta 8
\advance\@tempcnta -9 \ifnum #2>0 \advance\@tempcnta #2\relax\else
\advance\@tempcnta -#2\relax\advance\@tempcnta 64 \fi
\char\@tempcnta}

\def\vector(#1,#2)#3{\@xarg #1\relax \@yarg #2\relax
\@linelen=#3\unitlength
\ifnum\@xarg =0 \@vvector
  \else \ifnum\@yarg =0 \@hvector \else \@svector\fi
\fi}

\def\@hvector{\@hline\hbox to 0pt{\@linefnt
\ifnum \@xarg <0 \@getlarrow(1,0)\hss\else
    \hss\@getrarrow(1,0)\fi}}

\def\@vvector{\ifnum \@yarg <0 \@downvector \else \@upvector \fi}

\def\@svector{\@sline
\@tempcnta\@yarg \ifnum\@tempcnta <0 \@tempcnta=-\@tempcnta\fi
\ifnum\@tempcnta <5
  \hskip -\wd\@linechar
  \@upordown\@clnht \hbox{\@linefnt  \if@negarg
  \@getlarrow(\@xarg,\@yyarg) \else \@getrarrow(\@xarg,\@yyarg) \fi}%
\else\@badlinearg\fi}

\def\@getlarrow(#1,#2){\ifnum #2 =\z@ \@tempcnta='33\else
\@tempcnta=#1\relax\multiply\@tempcnta \sixt@@n \advance\@tempcnta
-9 \@tempcntb=#2\relax\multiply\@tempcntb \tw@
\ifnum \@tempcntb >0 \advance\@tempcnta \@tempcntb\relax
\else\advance\@tempcnta -\@tempcntb\advance\@tempcnta 64
\fi\fi\char\@tempcnta}

\def\@getrarrow(#1,#2){\@tempcntb=#2\relax
\ifnum\@tempcntb < 0 \@tempcntb=-\@tempcntb\relax\fi
\ifcase \@tempcntb\relax \@tempcnta='55 \or
\ifnum #1<3 \@tempcnta=#1\relax\multiply\@tempcnta
24 \advance\@tempcnta -6 \else \ifnum #1=3 \@tempcnta=49
\else\@tempcnta=58 \fi\fi\or
\ifnum #1<3 \@tempcnta=#1\relax\multiply\@tempcnta
24 \advance\@tempcnta -3 \else \@tempcnta=51\fi\or
\@tempcnta=#1\relax\multiply\@tempcnta
\sixt@@n \advance\@tempcnta -\tw@ \else
\@tempcnta=#1\relax\multiply\@tempcnta
\sixt@@n \advance\@tempcnta 7 \fi\ifnum #2<0 \advance\@tempcnta 64 \fi
\char\@tempcnta}



\def\@vline{\ifnum \@yarg <0 \@downline \else \@upline\fi}


\def\@upline{\hbox to \z@{\hskip -\@halfwidth \vrule
  width \@wholewidth height \@linelen depth \z@\hss}}

\def\@downline{\hbox to \z@{\hskip -\@halfwidth \vrule
  width \@wholewidth height \z@ depth \@linelen \hss}}

\def\@upvector{\@upline\setbox\@tempboxa\hbox{\@linefnt\char'66}\raise
     \@linelen \hbox to\z@{\lower \ht\@tempboxa\box\@tempboxa\hss}}

\def\@downvector{\@downline\lower \@linelen
      \hbox to \z@{\@linefnt\char'77\hss}}

%INITIALIZATION
\thinlines

\newcount\@xarg
\newcount\@yarg
\newcount\@yyarg
\newcount\@multicnt
\newdimen\@xdim
\newdimen\@ydim
\newbox\@linechar
\newdimen\@linelen
\newdimen\@clnwd
\newdimen\@clnht
\newdimen\@dashdim
\newbox\@dashbox
\newcount\@dashcnt
 \catcode`@=12


% macros supplementaires (J.D.)

\newbox\tbox
\newbox\tboxa

%\def\picbox(#1,#2,#3)#4{\setbox\tbox=\hbox{#4}%
%     \ht\tbox=#1 \wd\tbox=#2 \dp\tbox=#3 \box\tbox}

\def\leftzer#1{\setbox\tbox=\hbox to 0pt{#1\hss}%
     \ht\tbox=0pt \dp\tbox=0pt \box\tbox}

\def\rightzer#1{\setbox\tbox=\hbox to 0pt{\hss #1}%
     \ht\tbox=0pt \dp\tbox=0pt \box\tbox}

\def\centerzer#1{\setbox\tbox=\hbox to 0pt{\hss #1\hss}%
     \ht\tbox=0pt \dp\tbox=0pt \box\tbox}

% sytaxe: \image(hauteur totale reservee, distance
%    verticale de l'origine par rapport au bas de
%    la place reservee){materiel a inserer}
% L'origine est toujours centre horizontalement
%
\def\image(#1,#2)#3{\vbox to #1{\offinterlineskip
    \vss #3 \vskip #2}}

% \leftput place le materiel avec son point de reference
%    en #1,#2 unites \unitlength
% De meme pour \centerput et \rightput

\def\leftput(#1,#2)#3{\setbox\tboxa=\hbox{%
    \kern #1\unitlength
    \raise #2\unitlength\hbox{\leftzer{#3}}}%
    \ht\tboxa=0pt \wd\tboxa=0pt \dp\tboxa=0pt\box\tboxa}

\def\rightput(#1,#2)#3{\setbox\tboxa=\hbox{%
    \kern #1\unitlength
    \raise #2\unitlength\hbox{\rightzer{#3}}}%
    \ht\tboxa=0pt \wd\tboxa=0pt \dp\tboxa=0pt\box\tboxa}

\def\centerput(#1,#2)#3{\setbox\tboxa=\hbox{%
    \kern #1\unitlength
    \raise #2\unitlength\hbox{\centerzer{#3}}}%
    \ht\tboxa=0pt \wd\tboxa=0pt \dp\tboxa=0pt\box\tboxa}

\unitlength=1mm

\let\cput=\centerput

\def\put(#1,#2)#3{\noalign{\nointerlineskip
                               \centerput(#1,#2){$#3$}
                                \nointerlineskip}}
%%%%%%%%%%% end of grille.tex %%%%%%%%%

\raggedbottom
\def\cyc{\mathop{\rm cyc}\nolimits}
\def\fix{\mathop{\rm fix}\nolimits}
\def\succ{\mathop{\rm succ}\nolimits}
\def\Pr{\mathop{\hbox{\rm P}}\nolimits}
\def\Qr{\mathop{\rm Q}\nolimits}
\auteurcourant={DOMINIQUE FOATA}
\titrecourant={RANDOM PERMUTATIONS AND BERNOULLI SEQUENCES}


\vglue 3.5cm
\centerline{\sl RANDOM PERMUTATIONS AND BERNOULLI SEQUENCES}

\bigskip
\centerline{Dominique Foata}
\centerline{(Strasbourg)}

\vskip1cm
{\narrower

\abstract{The so-called first fundamental transformation provides a
natural combinatorial link between statistics involving cycle lengths of
random permutations and statistics dealing with runs on
Bernoulli sequences.}

}
\vskip1cm
\centerline{\bf 1. Introduction}

\medskip
Let $(X_n)$ $(n\ge 1)$ be a sequence of independent Bernoulli random
variables, the distribution of~$X_n$ being
$q_n\delta_0+p_n\delta_1$ with $0<p_n<1$ and $q_n=1-p_n$. For each
$n\ge2$ let $W_n$ denote the random variable
$W_n:=X_n+\sum\limits_{1\le k\le n-1}X_kX_{k+1}$. In other words, $W_n$,
when applied to a sequence of~0's and~1's, is the number of~1's within
the  first $(n-1)$ terms, which are themselves immediately followed by~1's,
plus one whenever the $n$-th term is also equal to~1.

Next, let ${\cal S}_n$ be the group of the permutations of the
interval $[1,n]=\{1,2,\ldots,n\}$. If $\sigma$ is such a permutation,
let $Z_n(\sigma)$ denote the number of {\it fixed points}
of~$\sigma$, i.e., the number of integers~$i$ such that $1\le i\le n$ and
$\sigma(i)=i$. When the equidistribution is taken over~${\cal S}_n$,
the distribution of the random variable~$Z_n$ is common knowledge. For
example, the generating function for~$Z_n$ is known to be (see [FF] p.~262)
$G_{Z_n}(s)={\bf E}[s^{Z_n}]=\sum\limits_{k=0}^n (s-1)^k/k!$, so
that, when $n$ tends to infinity, $Z_n$ tends to a Poisson random variable
with mean equal to~1 in distribution. When $p_k=1/k$ for $k=1,2,\ldots\,$,
the same limiting result holds for the sequence $(W_n)$ $(n\ge 1)$, a
result proved by several authors, Diaconis
[D], \'Emery [E], Joffe, Marchand, Perron, Popadiuk [JMPP]. The latter
authors also derive the distribution of~$W_n$ and notice that it is
identical with the distribution of~$Z_n$. They obtain a further extension
of this result when the fixed points of the permutations are only recorded
until a fixed bound.

The variables $W_n$ and $Z_n$ are defined on two different
probability spaces. A priori, there is no reason why their distributions
should be equal, so Joffe~[J] suggested that some intrinsic
link be found to explain that equality. It is the purpose of this
note to provide that link by using classical combinatorial techniques.

Assume that $n$ is a fixed integer, also that $p_k=1/k$ for
$k=1,2,\ldots, n$ and $p_{n+1}=1$, thus $X_{n+1}=1$. With this 
convention the variable~$W_n$ can be renamed as
$$
W_{[11]}:=\sum_{1\le k\le n}X_kX_{k+1}.
$$
In the same manner, let $Z_{[1]}(\sigma)$ denote the number of fixed
points of the permutation~$\sigma$ and let~$\Pr$ be the equirepartition on
the permutation group ${\cal S}_n$. Finally,~$\Qr$ will designate the
probability measure of the vector $(X_1,X_2,\ldots,X_n)$, that acts on the
set $\{0,1\}^n$.

Finding an intrinsic link boils down to defining a random variable~$Y$
such that the following diagramme is commutative.

\def\fleche(#1,#2)\dir(#3,#4)\long#5{%
{\leftput(#1,#2){\vector(#3,#4){#5}}}}


$$\vbox{\offinterlineskip
\centerput(0,0){$({\cal S}_n,\Pr)$}
\fleche(9,0)\dir(1,0)\long{10}
\centerput(30,0){$(\{0,1\}^n,\Qr)$}
\centerput(15,1){$Y$}
\fleche(30,-2)\dir(0,-1)\long{7}
\centerput(35,-6){$W_{[11]}$}
\fleche(8,-2)\dir(5,-2)\long{18}
\centerput(12,-8){$Z_{[1]}$}
\centerput(30,-13){$[0,n]$}
}\hskip4cm
$$

\vskip 1.7cm
\noindent
This means that $Z_{[1]}=W_{[11]}\circ Y$ and $\Qr$ is the image of the
measure~$\Pr$ under~$Y$, i.e., $\Qr=\Pr\circ Y^{-1}$. The variable~$Y$ is
defined by means of a classical bijection on the permutation group,
referred to as the {\it first fundamental transformation} (see [L],
p.~186--188).

The construction of the first fundamental transformation is recalled in the
next section. Then, the variable~$Y$ is defined in section~3 and shown to
have the properties described in the previous diagramme. In section~4
another variable~$Y_B$ is defined that takes the extension proposed by
Joffe and his coauthors [JMPP] into account. We conclude the note by
calculating various generating functions relevant to the problem under
study.  
                                   
\bigskip
\centerline{\bf 2. The first fundamental transformation}

\medskip
Let $\sigma$ be a permutation of order~$n$ having $r$~orbits $I_1$,
$I_2$, \dots~, $I_r$ [accordingly, $r$ cycles and we write $\cyc\sigma=r$].
The orbits are numbered in such a way that
$\max I_1<\max I_2<\cdots < \max I_r$. For each $j=1,2,\ldots, r$ let
$|I_j|$ be the the cardinality of~$I_j$ and let $\check \sigma_j$ be the
{\it initially dominated} word
$$
\check \sigma_j:=\sigma^{|I_j|}(\max I_j), \,
\sigma^{|I_j|-1}(\max I_j),
\ldots , \sigma^{2}(\max I_j),\sigma(\max I_j).
$$ 
Notice that $\sigma^{|I_j|}(\max I_j)=\max I_j$ and the word 
$\check \sigma_j$ contains all the elements of~$I_j$ once and only once.
To the permutation~$\sigma$ we now associate the juxtaposition product:
$\check \sigma:=\check\sigma_1 \check\sigma_2\ldots \check\sigma_r$.

\medskip
{\it Example}. --- Consider the permutation:
$$
\sigma =\left(\vcenter{
\halign{&$\;$\hfil#\hfil$\;$\cr
1&2&3&4&5&6&7&8&9\cr
8&5&7&4&3&9&2&6&1\cr
}}\right).
$$
The orbits of $\sigma $ written in increasing order according to their
maxima (in boldface) are:
$$
I_1=\{{\bf 4}\},\quad I_2=\{2,3,5,{\bf 7}\},\quad
I_3=\{1,6,8,{\bf 9}\}.
$$
Hence,\qquad
$\check\sigma_1=\sigma({\bf 4})={\bf 4}$;\qquad
$\check\sigma_2=\sigma^4({\bf 7}),\sigma^{3}({\bf 7}),
\sigma^{2}({\bf 7}),\sigma({\bf 7})={\bf 7},3,5,2$;\hfil\break
$\check\sigma_3=\sigma^4({\bf 9}),\sigma^{3}({\bf 9}),\sigma^{2}({\bf 9})
,\sigma({\bf 9})={\bf 9},6,8,1$ and
$$
\check \sigma={\bf4}, {\bf 7}, 3, 5,2,{\bf 9},6,8,1.
$$

Actually, the map $\sigma\mapsto \check \sigma$ is a bijection
of ${\cal S}_n$ onto the set~$R_n$ of all the rearrangements of the word
$1,2,\ldots,n$ and referred to as the {\it first fundamental
transformation}. The inverse bijection is defined as follows: start with a
rearrangement~$\tau$ of the word
$1,2,\ldots,n$; cut the word~$\tau$ before each {\it upper record},
that is, before each letter  greater than all the letters located 
{\it on its left}. The factors of~$\tau$ obtained in that way are {\it
initially dominated}, in the sense that they all begin with their greatest
letters. Moreover, the subword of~$\tau$ consisting of the first letters
of those factors is {\it increasing}. The sequence of those factors is
called the {\it increasing factorization} of~$\tau$ in {\it initially
dominated words}. The factorization is unique.

Once the factors of the factorisation are given, the cycles of the
permutation~$\sigma$ such that $\check\sigma=\tau$ can be reconstructed.
In the foregoing example the upper records of
$\check\sigma$ are {\bf 4}, {\bf 7}, {\bf 9}, so that the cycles
of~$\sigma$ can be reconstructed as:
${\bf 4}\leftarrow {\bf 4}$;\quad ${\bf 7}
\leftarrow3\leftarrow5\leftarrow2\leftarrow{\bf 7}$;\quad
${\bf 9}\leftarrow6\leftarrow8\leftarrow1\leftarrow{\bf 9}$.

\medskip
Now juxtapose the symbol~$\infty$ to the right of~$\check \sigma =\check
\sigma(1)\check\sigma(2)\ldots\check \sigma(n)$ and let 
$\check \sigma(n+1):=\infty$. The word $\check\sigma\infty=\check
\sigma(1)\check\sigma(2)\ldots\check \sigma(n)\check\sigma(n+1)$ gets one
more upper record. A careful study of the previous construction yields the
following property. 

\proclaim Property 1. The element $k$ $(1\le k\le n)$ is an orbit maximum
of~$\sigma$ if and only if $k$ is an upper record in $\check \sigma$. For
each $k=1,2\ldots,n$ there is a one-to-one correspondence between the
cycles of~$\sigma$, of length~$k$, and the factors
$\check \sigma(i)\check \sigma(i+1)\ldots \check \sigma(i+k)$, of length
$(k+1)$, of the word $\check \sigma\infty$, such that 
$\check \sigma(i)$ and $\check \sigma(i+k)$ are the only upper records of
the factor. Finally, the number, $\cyc \sigma$, of cycles of~$\sigma$
is equal to the number of upper records of the word~$\check\sigma$.

The above property is an immediate consequence of the construction of the
first fundamental transformation. Using the previous example we see that 
{\bf4, 7, 9} are the orbit maxima of~$\sigma$ and the upper records
of~$\check\sigma$. Moreover, the fixed point~{\bf4} corresponds to the
factor {\bf4,7}, where {\bf4} and {\bf7} are upper records. The cycles
of length~4 correspond to the ${\bf 7},3 ,5, 2, {\bf 9}$ and ${\bf
9},6,8,1,\infty$, both of length~5.


\goodbreak\bigskip
\centerline{\bf 3. Construction of the random variable $Y$}

\medskip
Consider a word~$\tau\infty$ belonging to~$R_n\infty$,
i.e., a rearrangement of the word $1,2,\ldots,n$ to the right of
which the letter~$\infty$ has been juxtaposed. Replace each upper
record of~$\tau$ by the letter~1 and the other letters by~0.
This yields a word belonging to
$1\{0,1\}^{n-1}1$, that is to say, a word, of length~$(n+1)$,
whose letters belong to the alphabet
$\{0,1\}$, beginning and ending with~1. Let $\psi(\tau\infty)$ denote the
binary word derived in this manner.

As, by convention, $X_{n+1}\equiv 1$, it makes sense to introduce the
random variables
$$
W_{[10^i1]}:=\sum_{1\le k\le n-i}
X_k(1-X_{k+1})(1-X_{k+2})\cdots (1-X_{k+i})X_{k+i+1},
$$
for $i=0,1,\ldots,n$, all defined on $\{0,1\}^n$. The variable
$W_{[10^i1]}$ enumerates the factor of the form $10^i1$ in a sequence
belonging to
$1\{0,1\}^{n-1}1$.
For $i=0$ we get back the
variable $W_{[11]}$ that enumerates the factors of the form~11.
In a similar way, for $k=1,2,\ldots,n$ and for each
permutation~$\sigma$ of order~$n$ let
$Z_{[k]}(\sigma)$ designate the number of cycles of~$\sigma$ of
length~$k$.

\proclaim Proposition 2. The map
$\sigma\mapsto \psi(\check \sigma\infty)$
is a surjection of the permutation group ${\cal S}_n$ 
onto the set $1\{0,1\}^{n-1}1$ having the property that
$$
Z_{[k]}(\sigma)=W_{[10^{k-1}1]} (\psi(\check \sigma\infty)).
$$
holds for each $k=1,2,\ldots, n$.

From all that has been said above the proposition is evident. What now
matters, for every word $v=x_1x_2\ldots x_nx_{n+1}\in 1\{0,1\}^{n-1}1$,
is to determine the number of permutations~$\sigma$ such that
$\psi(\check\sigma\infty)=v$ or, in an equivalent manner, the number of
rearrangements $\tau=y_1y_2\ldots y_n$ of the word $12\ldots n$ 
such that $\psi(\tau\infty)=v$. 

As this number depends on~$n$ and the sequence $1=i_r<i_{r-1}<\cdots
<i_2<i_1<i_0=n+1$ of the integers~$i$ such that $x_i=1$, denote this
number by $N(n;i_r,\ldots,i_1,i_0)$. The enumeration is trivial for
$n=1$. Assume $n\ge 2$. 

If $i_1=1$ (the word~$v$ is simply $10\ldots01$), all the suitable
words~$\tau$ are the rearrangements of $1,2,\ldots,n$ beginning with~$n$.
There are $(n-1)!$ such rearrangements, so that $N(n;1,n+1)=(n-1)!$

If $2\le i_1\le n$, then $x_{i_1}=1$. In all the suitable
rearrangements~$\tau=y_1y_2\ldots y_n$ we have $y_{i_1}=n$ and the right
factor
$y_{i_1+1}y_{i_1+2}\ldots y_n$, of length $(n-i_1)$, is made of distinct
letters taken from
$\{1,2,\ldots, n-1\}$. There are
$(n-1)(n-2)\cdots (n-1-(n-i_1)+1)=(n-1)(n-2)\cdots i_1$
possible factors, so that the following formula holds:
$$\displaylines{
N(n;i_r,\ldots,i_2,i_1,n+1)=
N(i_1-1;i_r,\ldots,i_2,i_1)\times i_1\cdots (n-2)(n-1);\cr
\noalign{\hbox{and by induction on $r$}}
\ N(n;i_r,\ldots,i_2,i_1,n+1)\hfill\cr
\hfill{}=
N(i_2-1;i_r,\ldots,i_3,i_2)\times i_2\cdots(i_1-2)
\times i_1\cdots (n-2)(n-1);\cr
\noalign{\hbox{and also}}
N(n;i_r,\ldots,i_2,i_1,n+1)={n!\over
(i_{r-1}-1)\cdots (i_2-1)(i_1-1)(i_0-1)},\cr}
$$
a formula that holds in all the cases.

We can then write
$$
\displaylines{
{N(n;i_r,\ldots,i_2,i_1,n+1)\over n!}\hfill\cr
\kern1cm{}
={1\over 1}{1\over 2}\cdots {i_{r-1}-2\over i_{r-1}-1}
{1\over i_{r-1}}{i_{r-1}\over i_{r-1}+1}
\cdots 
{i_{2}-2\over i_{2}-1}
{1\over i_{2}}{i_{2}\over i_{2}+1}
\cdots\hfill\cr
\hfill{}\times \cdots
{i_{1}-2\over i_{1}-1}
{1\over i_{1}}{i_{1}\over i_{1}+1}
\cdots {n-1\over n}.\cr
\kern1cm{}=
\Qr\{X_1=1\}\Qr\{X_2=0\}\cdots\hfill\cr
\kern2cm{}\times \Qr\{X_{i_{r-1}-1}=0\}
\Qr\{X_{i_{r-1}}=1\}\Qr\{X_{i_{r-1}+1}=0\}\cdots\hfill\cr
\kern2cm{}\times \Qr\{X_{i_{1}-1}=0\}
\Qr\{X_{i_{1}}=1\}\Qr\{X_{i_{1}+1}=0\}\cdots
\Qr\{X_{n}=0\}.\hfill\cr
}
$$
Now define
$$Y(\sigma):=\psi(\check \sigma\infty).$$ 
The previous calculation shows that
$$
\Pr\{Y=v\}={N(n;i_r,\ldots,i_2,i_1,n+1)\over n!}=\Qr\{v\},
$$
so that, when $\Pr$ is the equirepartition
on~${\cal S}_n$, the distribution of~$Y$ is the probability measure~$\Qr$.
Moreover Proposition~2 implies the following result.

\proclaim Proposition 3.
The two vectors
$
(Z_{[1]},Z_{[2]},\ldots, Z_{[n]})\ {\sl on}\ ({\cal S}_n,\Pr)$
and\hfil\break
$(W_{[11]},W_{[101]},\ldots, W_{[10^{n-1}1]})\ 
{\sl on}\ (\{0,1\}^{n},\Qr)$ are equally distributed.

\bigskip
\centerline{\bf 4. Construction of the variable $Y_B$}

\medskip
Joffe and his coauthors [JMPP] propose the following extension that we
will further extend: given an integer $B+n$ such that
$B\ge 0$ and $n\ge 1$ consider the permutation group ${\cal S}_{B+n}$ of
the permutations of order~$(B+n)$. Given such a permutation~$\sigma$, the
following operations are successively made: if
$\sigma(B+n)=B+n$, put this cycle of length~1 aside. Otherwise, set
$\sigma^2(B+n)$,
$\sigma^3(B+n)$,
\dots~, until, for the first time, $(B+n)$ occurs. 
The cycle containing $(B+n)$ is then obtained. Start again with the
greatest integer, less than
$(B+n)$, not occurring in the cycle already constructed. Continue this
procedure until~$n$ integers have been extracted. The purpose is to study 
the distribution of the random vector
$(Z_{[1]},Z_{[2]},\ldots, Z_{[n]})$ on the set of cycles that have been
extracted, the last one being possibly incomplete. 

To avoid any kind of ambiguity let us re-describe the construction by
saying that we make up a sequence of length~$n$ in the following way: if
$\sigma(B+n)=B+n$, take $\sigma(B+n)$ as the rightmost letter of that
sequence. Otherwise, form $\sigma(B+n)$,
$\sigma^2(B+n)$, then
$\sigma^3(B+n)$, \dots~, until, for the first time, $(B+n)$ occurs. Then,
$(B+n),\ldots,\sigma^2(B+n), \sigma(B+n)$ becomes the rightmost factor of
that sequence. Start again with the greatest integer, say $m$, that does
not occur in the cycle and form the factor
$m,\ldots,\sigma^2(m),\sigma(m)$, that is inserted to the left of the
previous factor. The procedure is stopped when, for the first time, the
length of the sequence is equal to~$n$.

This procedure is nothing but the  construction of the word
$$\check \sigma=\check\sigma(1)\check\sigma(2)\ldots\check\sigma(B+n)$$ 
defined in section~2, constructed from right to left, that is stopped as
soon as~$n$ letters have been obtained, that is, as soon as the right
factor
$\check\sigma(B+1)\check\sigma(B+2)\ldots \check\sigma(B+n)$, of
length~$n$, has been obtained.
Studying the distribution of the random vector
$(Z_{[1]},Z_{[2]},\ldots, Z_{[n]})$ on the cycles which are actually
extracted is equivalent to studying the distribution of the random vector
$(\check Z_{[1]},\check Z_{[2]},\ldots, \check Z_{[n]})$,
where for each $k=1,2,\ldots,n$ the $k$-th term $\check
Z_{[k]}(\sigma)$ designates the number of factors
$\check\sigma(i)\check\sigma(i+1)\ldots
\check\sigma(i+k)$ of the word $\check\sigma\infty$, of length
$(k+1)$, such that $i\ge B+1$ and such that the letters
$\check\sigma(i)$ and
$\check\sigma(i+k)$ are the only upper records of the factor.

As before, replace the upper records of 
$\check\sigma\infty$ by 1's and the other letters by~0's. This yields a
word belonging to $1\{0,1\}^{B+n-1}1$. Let $\psi_B(\check\sigma\infty)$
denote its right factor of length $(n+1)$, which is then a word belonging
to $\{0,1\}^{n}1$. 

Again, consider the sequence $(X_n)$ $(n\ge 1)$ of independent Bernoulli
random variables, such that for each~$n=1,2,\ldots$ the distribution
of~$X_n$ is
$(1-1/n)\delta_0+(1/n)\delta_1$. Denote the probability measure of the
random vector $(X_{B+1}, X_{B+2},\ldots, X_{B+n})$ 
by~$\Qr^{(B)}$ and assume that the variables $W_{[10^i1]}$ are this time
defined with a shift of~$B$ units, that is,
$$
W_{[10^i1]}:=\sum_{B+1\le k\le B+n-i}
X_k(1-X_{k+1})(1-X_{k+2})\cdots (1-X_{k+i})X_{k+i+1},
$$
where, by convention, $X_{B+n+1}\equiv 1$. Then, the analog of
Proposition~2 rewrites as follows.

\proclaim Proposition 4. The map
$\sigma\mapsto \psi_B(\check \sigma\infty)$
is a surjection of the group ${\cal S}_{B+n}$ onto the set $\{0,1\}^{n}1$,
such that for each $k=1,2,\ldots, n$ the following identity holds:
$$
\check Z_{[k]}(\sigma)=W_{[10^{k-1}1]} (\psi_B(\check
\sigma\infty)).
$$

For each word $v=x_1x_2\ldots x_nx_{n+1}\in \{0,1\}^{n}1$ let us
evaluate the number of permutations~$\sigma$ such that
$\psi_B(\check\sigma\infty)=v$. This number depends on~$B+n$ and on the
sequence
$1\le i_r<i_{r-1}<\cdots <i_2<i_1<i_0=n+1$ of the integers~$i$ such that
$x_i=1$. This number will be denoted by
$N(B+n;i_r,\ldots,i_1,i_0)$. Notice that this time
$1\le i_r$ holds instead of $1=i_r$ in the case $B=0$. As
$$\displaylines{N(B+i_r;i_r)=B!\,B(B+1)\cdots (B+i_r-2),\cr
\noalign{\hbox{we get the evaluation}}
N(B+n;i_r,\ldots,i_2,i_1,n+1)\hfill\cr
\hfill{}=
B!\, B\cdots (B+i_r-2)(B+i_r)\cdots (B+i_{r-1}-2)(B+i_{r-1})\cdots\cr
\hfill{}\times
\cdots (B+i_1-2)(B+i_1)\cdots (B+n-2)(B+n-1).\cr
}
$$
We can then write
$$
\displaylines{
{N(B+n;i_r,\ldots,i_2,i_1,n+1)\over (B+n)!}\hfill\cr
\kern1cm{}
={B\over B+1}{B+1\over B+2}\cdots {B+i_{r}-2\over B+i_{r}-1}
{1\over B+i_{r}}{B+i_{r}\over B+i_{r}+1}
\cdots \hfill\cr
\kern3cm{}\cdots\times
{B+i_{r-1}-2\over B+i_{r-1}-1}
{1\over B+i_{r-1}}{B+i_{r-1}\over B+i_{r-1}+1}
\cdots\hfill\cr
\kern3cm{} \cdots\times
{B+i_{1}-2\over B+i_{1}-1}
{1\over B+i_{1}}{B+i_{1}\over B+i_{1}+1}\cdots\hfill\cr
\kern3cm{} \cdots\times
{B+n-3\over B+n-2}
{B+n-2\over B+n-1}
{B+n-1\over B+n}.\hfill\cr
\kern1cm{}=
\Qr\{X_{B+1}=0\}\Qr\{X_{B+2}=0\}\cdots\hfill\cr
\kern2.2cm{} \cdots\times
\Qr\{X_{B+i_{r}-1}=0\}
\Qr\{X_{B+i_{r}}=1\}\Qr\{X_{B+i_{r}+1}=0\}\cdots\hfill\cr
\kern2.2cm{} \cdots\times
\Qr\{X_{B+i_{r-1}-1}=0\}
\Qr\{X_{i_{r-1}}=1\}\Qr\{X_{i_{r-1}+1}=0\}\cdots\hfill\cr
\kern2.2cm{} \cdots\times
 \Qr\{X_{B+i_{1}-1}=0\}
\Qr\{X_{B+i_{1}}=1\}\Qr\{X_{B+i_{1}+1}=0\}\cdots\hfill\cr
\kern2.2cm{} \cdots\times
\Qr\{X_{B+n-2}=0\}
\Qr\{X_{B+n-1}=0\}
\Qr\{X_{B+n}=0\}.\hfill\cr
}
$$
Then, define
$$Y_B(\sigma):=\psi_B(\check \sigma\infty).$$ 
The previous calculation shows that, when the equirepartition~$\Pr$
is taken over the group~${\cal S}_n$, the distribution of the
variable~$Y_B$ is, indeed, the probability measure~$\Qr^{(B)}$. 
Moreover, Proposition~4 implies the following result.

\proclaim Proposition 5. The two vectors
$(\check Z_{[1]},\check Z_{[2]},\ldots, \check Z_{[n]})\ {\sl
on}\ ({\cal S}_{B+n},\Pr)$ and
$(W_{[11]},W_{[101]},\ldots,
W_{[10^{n-1}1]})\  {\sl on}\ (\{0,1\}^{n},\Qr^{(B)})$ are equally
distributed.

\bigskip\goodbreak
\centerline{\bf 5. The generating functions}

\medskip
The distribution of the vector $(Z_{[1]}, Z_{[2]},\ldots, 
Z_{[n]})$ (in the case $B=0$) is a classic (see, e.g., [R] p.~68). It can
be expressed in three different ways. First, the generating function for
the vector is simply
$$G_n=
\sum{1\over k_1!\,k_2!\,\cdots k_n!}
\Bigl({t_1\over 1}\Bigr)^{k_1}
\Bigl({t_2\over 2}\Bigr)^{k_2}\cdots
\Bigl({t_n\over n}\Bigr)^{k_n},\leqno(5.1)
$$
where the sum is over all sequences $(k_1,k_2,\ldots, k_n)$
on nonnegative integers such that $k_1+2k_2+\cdots+nk_n=n$. 
This formula (valid for every $n\ge 0$) is still {\it
equivalent} to the exponential identity
$$
\sum_{n\ge 0}G_n\,u^n=\exp(ut_1+u^2{t_2\over 2}+u^3{t_3\over
3}+\cdots),\leqno(5.2)
$$
or still equivalent to the induction formula (that can be obtained by
taking the derivative of the previous identity)
$$
G_{n+1}={1\over n+1}\sum_{k=0}^n t_{k+1}\,G_{n-k}.\leqno(5.3)
$$
By Proposition~3 the above $G_n$ is also the generating function for the
vector
$(W_{[11]},W_{[101]},\ldots, W_{[10^{n-1}1]})$. Notice that the
generating function $\sum\limits_{k=0}^n (s-1)^k/k!$ for the variable 
$Z_{[11]}$, mentioned in the introduction, is a banal consequence of (5.3).

When $B$ is positive, only the induction formula (5.3) can be extended.
Again, let $G_n$ denote the generating function for either the vector
$(\check Z_{[1]},\check Z_{[2]},\ldots, \check Z_{[n]})$,
or the vector
$(W_{[11]},W_{[101]},\ldots, W_{[10^{n-1}]})$. We make the calculation
for the latter one. By induction, the generating polynomial for the
binary sequences of 0's and 1's ending with~1, of length
$(n+1)$, ending with~1 is $G_n\displaystyle{t_1\over B+n+1}$; for those
ending with $10$ 
$G_{n-1}\displaystyle{t_2\over B+n}{B+n\over B+n+1}$; \dots~; for those
of the form 
$10^n$ et
$0^{n+1}$, respectively
$$G_0\displaystyle{t_{n+1}\over B+1}{B+1\over B+2}
\cdots {B+n\over B+n+1}
\quad{\rm and}\quad {B\over B+1}{B+1\over B+2}
\cdots {B+n\over B+n+1}.$$
This yields the analog of (5.3), that is,
$$
G_{n+1}={1\over B+n+1}\Bigl(\sum_{k=0}^n t_{k+1}\,G_{n-k}+B\Bigr).
\leqno(5.4)
$$
Now, when we plug $t_1:=s$, $t_k:=1$ for $k\ge 2$ in the previous formula,
we immediately obtain the generating polynomial for $\check Z_{[1]}$ or for
$W_{[11]}$ in the form
$$
{\bf E}^{\hbox{\sevenrm P}}[s^{\check Z_{[1]}}]
={\bf E}^{\Qr^{(B)}}[s^{W_{[11]}}]=\sum_{k=0}^n {(s-1)^k\over
(B+1)_k},\leqno(5.5)
$$
a formula that was derived by Joffe et al. [JMPP] by means of a
probabilistic argument.


\vfill\eject\vglue 2cm
\centerline{\bf References}
\bigskip


\divers D|Persi Diaconis|Unpublished Manuscript|

\divers E|Michel \'Emery|Sur un probl\`eme de Diaconis, 
Unpublished Manu\-script, {\oldstyle 1998}|

\livre FF|Dominique Foata, Aim\'e Fuchs|Calcul des
Probabilit\'es|2nd edition, Dunod, Paris, {\oldstyle 2003}|

\divers J|Anatole Joffe|Sommes de produits de variables de Bernoulli et
permutations al\'eatoires\pointir S\'eminaire ``Calcul stochastique",
Strasbourg, Nov. 25, {\oldstyle 2003}|

\divers JMPP|Anatole Joffe, \'Eric Marchand, Fran\c cois Perron, Paul
Popadiuk|On Sums of Products of Bernoulli Variables
and Random Permutations, 8~p. to appear in {\sl Annals of Theoretical
Probability}|

\livre M|M. Lothaire|Combinatorics on Words|Addison-Wesley,
Reading, Mass., {\oldstyle1983} (Encyclopedia of Math. and its Appl., {\bf
17})|

\livre R|John Riordan|An Introduction to Combinatorial
Analysis|J. Wiley, New York, {\oldstyle1958}|

\bigskip\bigskip
{\parindent=0pt
Dominique Foata

Institut Lothaire

1, rue Murner

F-67000 Strasbourg, France

{\tt email: foata@math.u-strasbg.fr}

{\tt http://www-irma.u-strasbg.fr/$\sim$foata}

}
\bye

