Développement des séries génératrices des marches unidimensionnelles

Informellement, une marche est une suite de déplacements élémentaires ef- fectués dans un ensemble (par exemple sur une grille). L’étude combinatoire des marches est un sujet très riche, qui touche à de nombreux domaines des mathé- matiques (combinatoire des mots, physique statistique, probabilités, dénombre- ments, . . .) et qui peut-être abordé avec des points de vue variés. C’est un domaine où les méthodes de calcul formel ont connu un certain succès, certes en offrant la possibilité d’expérimenter par le calcul, mais aussi dans certains cas comme outil de preuve. C’est ainsi par exemple qu’une conjecture de Gessel sur une famille par- ticulière de marches dans le plan a été prouvée rigoureusement à l’aide de l’ordi- nateur en 2009. Ici, je vais m’intéresser à un problème d’ordre calculatoire sur les marches unidimensionnelles. Dans l’exemple 24 p. 37, nous étions parvenus à calculer les valeurs d’une suite de probabilités b. Après avoir discuté les avantages et in- convénients de leur méthode, je vais présenter une nouvelle méthode pour comp- ter les marches unidimensionnelles. Sans plus attendre, définissons plus précisé- ment les marches à étudier et le vocabulaire associé., sont essentiellement unidimensionnelles. En effet, on peut les voir comme des marches sur Z, l’axe vertical, alors que l’axe horizontal ne sert qu’à représenter le temps qui augmente de 1 à chaque pas.

L’exemple intéressant le plus simple est S Æ {¡1,1}. Les S-excur- sions ne sont autres que les chemins de Dyck, bien-connus en combinatoire. Leschemins de Dyck sont en bijection avec les mots bien parenthésés sur l’alphabet {(,)} : on peut voir tous les pas 1 comme des parenthèses ouvrantes et les pas ¡1comme des parenthèses fermantes. La condition de positivité des excursions tra- duit le fait que le nombre de parenthèses ouvrantes doit être plus grand que le nombre de parenthèses fermantes dans tout préfixe.aux votes respectifs pour les deux candidats, tandis que les pas 0 correspondent aux votes blancs. L’altitude finale mesure alors le score de l’élection. Ainsi, les S- ponts sont les déroulements qui se terminent par une égalité.repose sur le développement complet de la série génératrice W(x, y) sera inélucta- blement quadratique en N par nature. Les deux autres méthodes que je vais pré- senter ont pour principal atout d’avoir une complexité linéaire ou quasi-linéaire en N. Comme il sera expliqué, cette amélioration a lieu au prix d’un pré-calcul. Lors de l’analyse de la complexité des algorithmes, ce pré-calcul doit bien sûr être pris en compte, et nous allons voir qu’il a son importance : il peut dominer la com- plexité si l’on ne prend pas garde.

En passant par une équation algébrique

On a vu dans la proposition 106 que les séries B, E, et M sont algébriques. Ban- derier et Flajoletpour un énoncé précis). De là, une équation algébrique peut être obte-nue à l’aide de l’algorithme Platypus qui calcule un polynôme annulant un pro- duit de racines d’un polynôme donné. À partir d’une équation P(x,E(x)) Æ 0, onêtre utilisé pour calculer une récurrence linéaire à coefficients polynomiaux satis- faite par ses coefficients (voir le théorème 117 de l’annexe A et la proposition 25). La méthode directe exposée ci-dessus permet de calculer assez de conditions ini- tiales pour dérouler la récurrence (il en faut au plus un nombre polynomial en le degré de l’équation algébrique calculée d’après la proposition 34 p. 42). Ainsi, cette approche permet de calculer les N premiers termes de B, E et M en O(N) opéra- tions. Pour que ceci soit une amélioration par rapport à la méthode naïve, il faut que la dépendance en d de la constante dans le O() ne soit pas trop grande et que le pré-calcul ne soit pas trop coûteux.