The lattice path operad

icon

5

pages

icon

English

icon

Documents

Écrit par

Publié par

Lire un extrait
Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris
icon

5

pages

icon

English

icon

Ebook

Lire un extrait
Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

The lattice path operad? Clemens Berger (Nice) Third Arolla Conference on Algebraic Topology August 19th, 2008 ?joint work with Michael Batanin (Sydney)

  • structure induced

  • iterated loop

  • therefore any

  • tensor-product ?ke

  • any closed

  • cn-algebra

  • metric monoidal

  • category


Voir Alternate Text

Publié par

Nombre de lectures

6

Langue

English

Nondirected lattice paths on different lattices
Cyril Banderier
April 10, 2010
Abstract:We study excursions with jumps to nearest neighbors in different lattices (hexagonal, triangular, kagome, Manhattan lattices), paths in a strip, etc. Weshow that some families are algebraic, D-finite, and give some nice closed form formulas.
Keywords: latticepaths, algebraic functions, D-finite functions, kernel method
1 Introduction In a previous work [1], we concentrated on enumeration and asymptotics of directed lattice paths (i.e.walks which goes in only 3 directions, not 4).Recent works [6, 4] showed some nice explicit formula for enumeration of nondirected 2 walks (i.e.walks with many jumps, going to any directions) inN. Enumeration 2 and asymptotics of nondirected walks inZare in one sense solved by holonomy theory (see some examples in [2]).We concentrate in this article, first on walks in a strip, and then on enumeration of nondirected walks to nearest neighbors in different lattices, namely excursions (walks starting and ending at the origine), may it be in the whole plane or in the quarter plane (the number of such walks Z N of lengthnwill bee(n) ande(n)). Thegenerating functionsF(x, y, t) will enumerate walks with length encoded byt, and final position encoded by (x, y).
2 Walksin a strip Theorem 2.1Non directed walks in a strip (may it beZ×[a, b]orN×[a, b]) have an algebraic generating functionF(x, y, t). Proof.It is clear that such walks can be simulated on a nonambiguous push-down automata, (theb+apossible altitudes corresponding to+ 1b+a+ 1 states, and use a letter for each type of jump).Going to the Greibach normal form, such walks are thus generated by a nonambiguous context free grammar, therefore the associated generating function is algebraic.Note that for a strip LaboratoiredInformatiquedeParisNord,UMRCNRS7030,InstitutGalile´e, Universite´Paris13,99avenueJean-BaptisteCle´ment,93430Villetaneuse,France. http://www-lipn.univ-paris13.fr/banderier/
1
Voir Alternate Text
  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • Podcasts Podcasts
  • BD BD
  • Documents Documents
Alternate Text