{\catcode`\^^M=\active %
  \gdef\adrbox{\catcode`\^^M=\active %
  \def^^M{\egroup\hbox\bgroup}}}
\def\adresse{\par\nobreak%
  \vskip 24pt plus 6pt minus 3pt%
  \hbox to \hsize\bgroup\hfill%
  \def\fin{\egroup\egroup\hskip2em\egroup\vfill\eject}%
  \adrbox\vbox\bgroup\hbox\bgroup}
\def\fin{\vfill\eject}

\catcode'32=9
\magnification=1200

\voffset=1cm
\hoffset=0cm
%\hoffset=1cm
\font\tenpc=cmcsc10
%\font\eightpc=cmcsc8

% 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=eufm8
\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

%���������������������� dactylographie fran�aise �����������������

\catcode`\;=\active
\def;{\relax\ifhmode\ifdim\lastskip>\z@
\unskip\fi\kern\fontdimen2 \font\kern -1.2 \fontdimen3 \font\fi\string;}

\catcode`\:=\active
\def:{\relax\ifhmode\ifdim\lastskip>\z@\unskip\fi\penalty\@M\ \fi\string:}

\catcode`\!=\active
\def!{\relax\ifhmode\ifdim\lastskip>\z@
\unskip\fi\kern\fontdimen2 \font \kern -1.1 \fontdimen3 \font\fi\string!}

\catcode`\?=\active
\def?{\relax\ifhmode\ifdim\lastskip>\z@
\unskip\fi\kern\fontdimen2 \font \kern -1.1 \fontdimen3 \font\fi\string?}

\def\^#1{\if#1i{\accent"5E\i}\else{\accent"5E #1}\fi}
\def\"#1{\if#1i{\accent"7F\i}\else{\accent"7F #1}\fi}

\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}, t.\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}

\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 }

\catcode`\@=12


\pageno=79
\titrecourant={\'ENUM\'ERATION EN BIOLOGIE MOL\'ECULAIRE}
\auteurcourant={M. VAUCHASSADE DE CHAUMONT ET G. VIENNOT}

\eightpoint
\leftline{Publ. I.R.M.A. Strasbourg, $\oldstyle 1984$, 229/S--08}
\leftline{Actes 8\emini\ S\'eminaire Lotharingien, p. 79--86}

\tenpoint
\let\it=\sl

\vglue 1.5cm
\centerline{{\bf POLYN\^OMES ORTHOGONAUX ET PROBL\`EMES}} 
\vskip 5pt
\centerline{{\bf D'\'ENUM\'ERATION EN BIOLOGIE MOL\'ECULAIRE}}
\vskip 2.8mm
\centerline{\sevenrm PAR}
\vskip 2.8mm
\centerline{{\petcap M. {VAUCHASSADE} de {CHAUMONT}
{\sevenrm ET} G\'erard {VIENNOT}}} 
\vskip 24pt
\resume{Le but de cet expos\'e est de montrer 
comment certains polyn\^omes de Techebycheff 
g\'en\'eralis\'es \`a un param\`etre 
permettent de d\'enombrer les structures secondaires d'acides
nucl\'eiques simple-brin ayant une complexit\'e donn\'ee.}

\vskip 0pt plus 10pt
\section I. Introduction|La stucture primaire des acides
nucl\'eiques simple-brin (acide ribonucl\'eique ou ARN, ARN
messager, ARN de transfert, etc.) est constitu\'ee par
l'encha\^\i nement lin\'eaire de nucl\'eotides reli\'es par des
liaisons phosphodiesters. Chaque nucl\'eotide est caract\'eris\'e
par la base qu'il contient. Pour les ARN, il y a quatre
bases possibles: Ad\'enine, Cytosine, Guanine, Uracycle. Cette
structure primaire est cod\'ee par un mot sur un alphabet \`a quatre
lettres A, C, G, U. Les liaisons hydrog\`ene replient la
mol\'ecule sur elle-m\^eme pour former une
figure planaire : la {\it structure secondaire}.

Les liaisons hydrog\`ene ne peuvent se croiser. \pc WATERMAN|
[11] a d\'efini math\'ematiquement la notion de structure
secondaire comme une certaine famille de {\it graphes} (en fait
{\it cartes\/}) {\it planaires}. Cette famille contient toutes
les structures secondaires connues. Notons \'egalement que l'on
ne s'int\'eresse qu'au dessin form\'e par les liaisons,
c'est-\`a-dire, que l'on oublie l'\'etiquetage des sommets du
graphe par les bases A, C, G, U.

Les biologistes s'int\'eressent particuli\`erement \`a la
pr\'ediction des structures secondaires, la structure primaire 
\'etant connue (voir, par exemple, \pc TINOCO|\ et al. [10]).
Les liaisons hydrog\`ene \'etant de faible \'energie, la
stabilit\'e de la mol\'ecule d\'epend beaucoup de ses
``\'epingles \`a cheveux'', c'est-\`a-dire de r\'egions
contenant des liaisons hydrog\`ene parall\`eles. Un param\`etre
de {\it complexit\'e} (appel\'e aussi {\it ordre}) d'une structure
secondaire a \'et\'e d\'efini par \pc MITIKO| \pc G\^O| [4] et \pc
WATERMAN|~[11] pour le calcul de l'\'energie libre des \'epingles \`a
cheveux entre elles est plus ``compliqu\'ee."

Le probl\`eme combinatoire sous-jacent est de d\'enombrer toutes
les structures secondaires possibles de complexit\'e~$k$. Soit
donc $a_{n,k}$ le nombre de structures secondaires ayant~$n$
bases (c'est-\`a-dire les sommets du graphe) et de complexit\'e
$k$. \pc WATERMAN|\ a montr\'e que $a_{n,1}$ est
asymptotiquement \'equivalent \`a $\lambda ^n$, en d\'esignant
par $\lambda $ la plus grande racine de l'\'equation
$x^2-2x^3-1=0$ (soit $\lambda =2,2055\ldots$).

Notons $s_k(t)=\sum _{n\geq 0}a_{n,k}t^n$
la s\'erie g\'en\'eratrice des structures d'ordre $k$.
Le r\'esultat fondamental de l'expos\'e
est le suivant :

\th Th\'eor\`eme 1|La s\'erie g\'en\'eratrice des structures secondaires
d'ordre~$k$ est
$$
s_k(t)={t^{(5.2^{k-1}-2)}\over (1-t)Z_1\ldots Z_k}, 
$$
dans lequel $Z_1$, \dots~, $Z_k$ d\'esigne la suite de polyn\^omes
d\'efinis par la r\'ecurrence
$$
Z_1=1-2\,t-t^2, \quad Z_{k+1}=Z_k^2-2\,t^{5.2^{k-1}}\quad
(k\ge 1).
$$
\finth

La m\'ethode employ\'ee, ch\`ere \`a M.-P. \pc SCH\"UTZENBERGER|,
consiste \`a coder les objets combinatoires ayant une s\'erie
alg\'ebrique (ou rationnelle) par les mots d'un {\it langage
alg\'ebrique} (ou ``context-free," au sens de la th\'eorie des
langages en Informatique Th\'eorique).  La s\'erie g\'en\'eratrice
(ordinaire) s'obtient par passage \`a l'image commutative de la
{\it s\'erie g\'en\'eratrice non-commutative} form\'ee par la
somme formelle des mots du langage (plus pr\'ecis\'ement en
envoyant par morphisme toutes les variables sur la m\^eme
variable $t$). La s\'erie g\'en\'eratrice des mots du langage est
solution d'un syst\`eme alg\'ebrique (en s\'eries formelles \`a
variables non-commutatives).  Chaque \'equation traduit une
propri\'et\'e combinatoire des objets. Ce passage au
non-commutatif est ainsi un interm\'ediaire commode entre
l'objet combinatoire et la s\'erie g\'en\'eratrice classique.

La r\'esolution du syst\`eme provenant des structures secondaires
n\'ecessite la m\'ethodologie des interpr\'etations combinatoires
des {\it polyn\^omes orthogonaux}. En particulier, apparaissent
des ``polyn\^omes de Tchebycheff" $F_n(x,b)$ \`a un param\`etre~$b$,
qui sont orthogonaux pour la forme lin\'eaire
$P\mapsto \int_\alpha^\beta P\,d\psi$,
d\'efinie par ses {\it moments} :
$$
\mu _n(b)=\int _\alpha ^\beta x^n\,d\psi 
=\sum _{k\geq 1}{1\over n}
{n\choose k}{n\choose k-1}
b^k.\leqno(1)
$$
Pour $b=1$, le polyn\^ome $F_n(x,1)$ est le polyn\^ome
$U_n(x/2)$, dans lequel $U_n$ est le {\it polyn\^ome
de Tchebycheff} de deuxi\`eme esp\`ece d\'efini par
$$
\sin(n+1)\theta =\sin\theta \,U_n(\cos\theta ).\leqno(2)
$$

Cet expos\'e est un r\'esum\'e d'un article qui sera publi\'e
ult\'erieurement. Il a fait l'objet d'une communication au congr\`es
{\it Mathematics in Biology and Medicine} [Bari, Italie. Juillet
1983].

\section 2. Codage par des mots|On peut coder les structures
secondaires ayant $n$ bases par des mots de longueur~$n$ sur
l'alphabet $X=\{a,x,\overline x\}$. On parcourt les sommets de
la structure secondaire selon l'ordre de la s\'equence primaire,
en \'ecrivant~$x$ (resp.~$\overline x$) lorsque l'on rencontre
une liaison hydrog\`ene pour la premi\`ere fois (resp. deuxi\`eme
fois). Lorsque la base n'est pas reli\'ee par une liaison
hydrog\`ene, on \'ecrit~$a$. La d\'efinition des structures
secondaires donn\'ee par \pc WATERMAN|~[11] permet de
caract\'eriser l'ensemble~${\cal S}$ des mots ainsi obtenus. Ce
sont les mots~$w$ v\'erifiant les trois conditions suivantes :

\def\xb{{\overline x}}

\decale (3)|pour toute factorisation $w=uv$, $|u|_x\ge
|u|_\xb$ (dans lequel $|u|_z$ d\'esigne le nombre
d'occurrences de la lettre $z$ dans le mot~$u$) ;

\decale (4)|$|w|_x=|w|_\xb$ ;

\decale (5)|$w$ n'a pas de facteur $x\xb$ (c'est-\`a-dire, qu'il
n'y a pas de factorisation $w=ux\xb v$.

\rem Remarque|Classiquement, les mots sur l'alphabet
$\{a,x,\xb\}$ v\'erifiant (3) et (4) sont appel\'es {\it mots de
Motzkin}. Le nombre de tels mots de longueur~$n$ est le nombre
de Motzkin~$M_n$.

\medskip
Les mots sur l'alphabet $\{x,\xb\}$ v\'erifiant (3) et (4.) sont
appel\'es {\it mots de Dyck}. Le nombre de tels mots de longueur
$2n$ est le classique {\it nombre de Catalan} $C_n={1\over
n}{2n\choose n}$. La condition (5) traduit le fait que deux
bases ne peuvent \^etre reli\'ees \`a la fois par des liaisons
phosphodiesters et hydrog\`ene.

Notons $S=\sum_{w\in S} w$ la s\'erie g\'en\'eratrice formelle en
variables non commutatives $x\in X$ (\`a coefficients dans $\bf
Z$). Elle est solution de l'\'equation alg\'ebrique
$$
S=1+aS+x(S-1)\xb\, S.\leqno(6) 
$$
Par le morphisme $\varphi$ envoyant toutes les lettres $a$,
$x$, $\xb$ sur la lettre~$t$, on obtient la s\'erie g\'en\'eratrice
des structures secondaires, d\'enombr\'ees selon le nombre de
bases (voir aussi \pc STEIN|, \pc WATERMAN|~[5])
$$
s(t)={1\over 2t^2}
\Bigl(t^2-t+1-(1+t(t^3-2t^2-t-2))^{1/2}\Bigr).\leqno(7) 
$$

\section 3. Complexit\'e d'une structure secondaire|Nous
d\'efinissons l'ordre d'un mot, traduisant la d\'efinition de la
complexit\'e d'une structure secondaire de~[11]. Soit $w$ un mot
de Motzkin (v\'erifiant (3) et (4)) et $\alpha(w)$ le mot (de Dyck)
obtenu en enlevant les lettres~$a$. Une {\it pyramide} d'un mot
de Dyck est un facteur de la forme $x^p\xb^p$. Une pyramide
est dite {\it maximale} si elle n'est pas facteur d'une autre
pyramide. Tout mot de Dyck $w$ admet une d\'ecomposition unique
en pyramides maximales de la forme
$w=u_1v_2\ldots u_qv_qu_{q+1}$ avec $q\ge 1$ et $v_1$,
\dots~, $v_q$ pyramides maximales. On d\'efinit alors
$\pi(w)=u_1\ldots u_{q+1}$ (op\'erateur suppression des
pyramides maximales). L'{\it ordre} d'un mot $w\in S$ codant
une structure secondaire est le minimum des entiers~$k$ tels
que
$$
\pi^k(\alpha(w))=e\quad ({\rm mot\ vide}).\leqno(8) 
$$

\rem Exemple|Soit 
$w=x\,x\,x\,\xb\,x\,x\,\xb\,\xb\,\xb\,x\,
\xb\,\xb\,x\,x\,\xb\,x\,\xb\,\xb$, alors\hfil\break
\indent\indent
$\pi(w)=x\,x\,\xb\,\xb\,x\,\xb$,\quad $\pi^2(w)=e$.

\noindent
Le mot $w$ est d'ordre 2 (on a indiqu\'e les d\'ecompositions en
pyramides maximales).

\rem Remarque|Les pyramides maximales du mot de Dyck
$\alpha(w)$ correspondent aux \'epingles \`a cheveux de la
structure secondaire cod\'ee par~$w$.

\medskip
Dans notre formalisme, on peut \'enoncer commod\'ement une
propri\'et\'e r\'ecemment mise en \'evidence \`a Strasbourg au
laboratoire du professeur J.-P. \pc EBEL|~[8] : les ARN de la
petite sous-unit\'e ribosomale de diverses exp\`eces ont ``en
gros" le m\^eme mot de Dyck $\alpha(w)$ associ\'e (bien que le
nombre de bases puisse varier de 954 pour l'ARN 12-S des
mitochondries humaines \`a 1825 pour l'ARN 18-S du cytomlasme
de Xenopus laevis).

Pour $k\ge 1$ la s\'erie g\'en\'eratrice non commutative $S_k$ des
mots codant les structures secondaires d'ordre~$k$ est
solution du syst\`eme alg\'ebrique suivant :
$$
\eqalign{S_k&=S_{\le k}-S_{\le k-1}\quad (k\ge 1);\cr
S_{\le k}&=(1-T_{\le k})^{-1}\quad (k\ge 0);\cr 
T_{\le k}&=T_0+T_1+\cdots +T_k\quad (k\ge 0);\cr
T_k&=xS_{\le k-2}T_{k-1}
S_{\le k-2}T_{k-1}S_{\le k-1}\xb%\cr 
%&\qquad{}
+xS_{\le k-1}T_kS_{\le k-1}\xb\ (k\ge 2);\cr 
T_0&=a;\cr
T_1&=xS_0T_1S_0\xb+xS_0T_0\xb.\cr}\leqno(9)
$$
La s\'erie $S_{\le k}$ est la s\'erie g\'en\'eratrice des mots codant
les structures secondaires d'ordre $\le k$. Un mot de Motzkin
est dit {\it premier} lorsqu'il ne peut se factoriser en produit
de $p\ge 2$ mots de Motzkin. La notation~$T_k$ (resp.~$T_{\le
k}$) d\'esigne la s\'erie g\'en\'eratrice des mots de Motzkin premiers
codant les structures secondaires.

\section 4. Mots de Dyck d'ordre donn\'e|Soit $D_k$ la s\'erie
g\'en\'eratrice non-commutative des mots de Dyck d'ordre~$k$.
Cette s\'erie v\'erifie un syst\`eme analogue \`a~(9), mais en
rempla\c cant les deux derni\`eres \'equations par
 $$
T_0=0,\qquad T_1=\sum_{n\ge 1} x^n\xb^n.\leqno(10) 
$$
L'image par le morphisme $\varphi$ envoyant $x$ et $\xb$
sur~$t$ donne la s\'erie g\'en\'eratrice ordinaire $d_k(t)$ (resp.
$d_{\le k}(t)$) des mots de Dyck d'ordre~$k$ (resp.~$\le k$).

\th Proposition 2|On a
$$
d_k(t)={t^{(2^{k+1}-2)}\over R_{(2^{k+1}-1)}(t)},
\qquad
d_{\le k}(t)={R_{(2^{k+1}-2)}(t)\over R_{(2^{k+1}-1)}(t)},
$$
o\`u $R_n(t)$ d\'esigne le polyn\^ome r\'eciproque du polyn\^ome
$F_n(t)=U_n(t/2)$ d\'efini en $(2)$.
\finth

La preuve repose sur les deux identit\'es suivantes
$$
\leqalignno{
R_p^2-t^2R_{p-1}^2&=R_{2p}\quad (1\le p);&(11)\cr
R_{q+1}R_p-R_qR_{p+1}&=t^{2q+2}R_{p-q-1}\quad (1\le
q<p).&(12)\cr}
 $$
Nous en donnons des preuves bijectives simples : (11) repose
sur une interpr\'etation de $R_p$ par des {\it pavages (valu\'es)
de dominos} deux \`a deux disjoints du segment $[1,p]$ ; (12)
repose sur l'interpr\'etation de $R_p/R_{p+1}$ comme s\'erie
g\'en\'eratrice des ``chemins de Dyck" associ\'es aux mots de Dyck
et de hauteur born\'ee~$p$ (voir \pc KREWERAS|~[3]).

\section 5. R\'esolution dy syst\`eme (9)|On remarque que les
polyn\^omes $F_n(x)=U_n(x/2)$ sont orthogonaux pour la suite
des moments $\pi_n=C_n$ (nombre de Catalan). La condition (3)
n\'ecessite de comptabiliser les ``pics" (ou les facteurs $x\xb$)
des mots de Dyck, c'est-\`a-dire, d'introduire une variable
formelle non-commutative~$b$ dans (9) par la relation suivante
$$
T_1=xS_0T_1S_0\xb+xS_0b\xb.\leqno(13) 
$$
Il est bien classique [3] que la distribution des mots de Dyck
selon le nombre de pics est donn\'ee par les {\it nombres de
Runyon} (appel\'es aussi nombres de Narayana ${1\over
n}{n\choose k}{n\choose k-1}$. On est donc conluit \`a
chercher des polyn\^omes orthogonaux $F_n(x,b)$ (\`a un
param\`etre~$b$) pour la suite de moments d\'efinis par~(1). Ces
polyn\^omes se r\'eduisent \`a $F_n(x)$ pour $b=1$.

Nous donnons une preuve purement bijective du fait que ces
polyn\^omes sont donn\'es par la r\'ecurrence suivante :
$$\displaylines{\rlap{(14)}\hfill
F_{n+1}(x,b)=xF_n(x,b)-\lambda_nF_{n-1}(x,b),\hfill\cr
\noalign{\hbox{avec}}
\lambda_n=\cases{1,&si $n$ impair ;\cr
b,&si $n$ pair.\cr}\cr}
$$
En introduisant le param\`etre~$b$ dans les bijections prouvant
(11) et (12), on prouve l'analogue de ces relations.

Soit maintenant $H_n(x,b)$ le polyn\^ome r\'eciproque (\`a un
param\`etre) du polyn\^ome $F_n(x-1,b)$. Posons
$V_n(x)=H_n(x,x)$. On d\'emontre par r\'ecurrence sur~$k$ que la
s\'erie $s_k=\varphi(S_k)$ est donn\'ee par l'expression suivante :
$$
s_k={t^{(5.2^{k-1}-2)}\over V_{(2^{k+1}-1)}}.\leqno(15) 
$$
En fait $V_n$ est d\'efini par la r\'ecurrence
$$\displaylines{\rlap{(16)}\hfill
V_0=1,\quad V_1=x,\quad
V_{n+1}=(1-x)V_n-\lambda_nV_{n-1},\hfill\cr
\noalign{\hbox{avec}}
\lambda_n=\cases{x^2,&pour $n$ impair ;\cr
x^3,&pour $n$ pair.\cr}\cr
\noalign{\hbox{Une bijection prouve la relation}}
\rlap{(17)}\hfill
V_{2^{k+1}-1}=V_{2^k-1}Z_k\qquad (k\ge 1),\hfill\cr}
$$
dans laquelle $Z_k$ est un polyn\^ome obtenu comme somme de
``pavages" valu\'es sur un cercle ayant $2^k$ points, de dominos
et monominos deux \`a deux disjoints. Une autre bijection sur ces
pavages prouve la r\'ecurrence :
$$
Z_{k+1}=Z_k^2-2t^{5.2^{k-1}}\qquad (k\ge 1).\leqno(18) 
$$
On obtient ainsi le th\'eor\`eme 1.

\rem Remarque finale|Il est curieux de constater que la s\'erie
ordinaire $d_k(t)$ de la Proposition 2 est la m\^eme que celle
donnant la s\'erie g\'en\'eratrice des {\it arbres binaires} ayant un
{\it nombre de Strahler} \'egal \`a~$k$. Ce nombre est un param\`etre
introduit en Hydrographie Fluviale par \pc STRAHLER|~[9],
apparaissant aussi en Informatique Th\'eorique~[1], et aussi en
Botanique et Anatomie (voir pages 113 et 225 de la traduction
fran\c caise~[6]). On trouvera dans \pc FRAN\c CON|~[2]
d'int\'eressantes consid\'erations bijectives montrant que ces
deux param\`etres ont m\^eme distribution qu'un troisi\`eme : le plus
grand entier inf\'erieur ou \'egal au logarithme (en base 2) de la
hauteur maximale des chemins de Dyck associ\'es.

\vfill\eject
\vglue 44pt
{\eightpoint
\centerline{BIBLIOGRAPHIE}
\bigskip
\article 1|Flajolet (Philippe), Raoult (Jean-Claude) et Vuillemin
(Jean)|The number of registers required for evaluating
arithmetic expressions|Theor. Comp. Sc.|9|1979|99--125|

\divers 2|Fran\c con (Jean)|Sur le nombre de registres
n\'ecessaires \`a l'\'evaluation d'une expression arithm\'etique, 
\`a para\^\i tre dans {\sl R.A.I.R.O}|

\article 3|Kreweras (Germain)|Sur les \'eventails de
segments|Cahiers du B.U.R.O.|15|1970|3--41|

\article 4|Mitiko G\^o|Statistical mechanics of biopolymers and
its application to the melting transition of polynucleotides|J.
Phys. Soc. Japan|23|1967|597--607|

\article 5|Stein (P.R.) and Waterman (M.S.)|On some new sequences
generalizing the Catalan and Motzkin numbers|Discrete
Math.|26|1979|261--272|

\livre 6|Stevens (P.R.)|Patterns in Nature|Little, Brown and Co.,
1974 [Traduction fran\c caise : {\sl Les formes dans la
nature}\pointir Paris, Seuil, 1978]|

\divers 7|Stiegler (P.), Carbon (P.), Zuker (M.), Ebel (J.-P.) and
Ehresmann (C.)|{\sl Nucleic Acids Res.}, t. {\bf 9}, 1981, p.
2153--2172|

\article 8|Stiegler (P.), Carbon (P.), Ebel (J.-P.) and
Ehresmann (C.)|A general secondary structure model for
procaryotic and euraryotic RNA's of the small ribosomal
subunits|Europ. J. Biochem.|120|1981|487--495|

\divers 9|Strahler (A.N.)|Hypsometric (area-altitude) analysis
of erosional topology, {\sl Bull. Geological Soc. Amer.}, 1952,
p.~1117--1142|

\article 10|Tinoco (I.), Uhlenbeck (0.C.) and Levine
(M.D.)|Estimation of secondary structure in ribonucleic
acids|Nature|230|1971|362--367|

\divers 11|Waterman (Michael S.)|Secondary structure of
single-stranded nucleic acids, in {\sl Studies in Foundations
and Combinatorics} (Adv. in Math., suppl.) t.~{\bf 1}, {\oldstyle
1978}, p. 167--172|

}


\vskip 1cm
\adresse
{\petcap M. Vauchassade de Chaumont},
Universit\'e de Bordeaux II,
Bordeaux, France

et

G\'erard {\petcap Viennot},
U.E.R. de math\'e\-ma\-tiques et d'informatique, 
Universit\'e de Bordeaux I, 
351, cours de la Lib\'eration, 
33405 Talence Cedex, France.

\fin
\bye
