A NOTE ON THE ENUMERATION OF DIRECTED ANIMALS VIA GAS CONSIDERATIONS

被引:9
作者
Albenque, Marie [1 ]
机构
[1] Univ Paris Diderot Paris 7, F-75205 Paris 13, France
关键词
Gas model; cyclic Markov chains; directed animals; graphs convergence; DIMENSIONS;
D O I
10.1214/08-AAP580
中图分类号
O21 [概率论与数理统计]; C8 [统计学];
学科分类号
020208 ; 070103 ; 0714 ;
摘要
In the literature, most of the results about the enumeration of directed animals on lattices via gas considerations are obtained by a formal passage to the limit of enumeration of directed animals on cyclical versions of the lattice. Here we provide a new point of view on this phenomenon. Using the gas construction given in [Electron. J. Combin. (2007) 14 R71], we describe the gas process on the cyclical versions of the lattices as a cyclical Markov chain (roughly speaking, Markov chains conditioned to come back to their starting point). Then we introduce a notion of convergence of graphs, such that if (G(n)) -> G then the gas process built on G(n) converges in distribution to the gas process on G. That gives a general tool to show that gas processes related to animals enumeration are often Markovian on lines extracted from lattices. We provide examples and computations of new generating functions for directed animals with various sources on the triangular lattice, on the 7,, lattices introduced in [Ann. Comb. 4 (2000) 269-284] and on a generalization of the G,, lattices introduced in [J. Phys. A 29 (1996) 3357-3365].
引用
收藏
页码:1860 / 1879
页数:20
相关论文
共 13 条
[1]   Directed animals, forests and permutations [J].
Barcucci, E ;
Del Lungo, A ;
Pergola, E ;
Pinzani, R .
DISCRETE MATHEMATICS, 1999, 204 (1-3) :41-71
[2]   ANIMALS AND LOP-SIDED TREES [J].
BETREMA, J ;
PENAUD, JG .
THEORETICAL COMPUTER SCIENCE, 1993, 117 (1-2) :67-89
[3]  
BETREMA J, 1993, ARXIVMATHCO0106210
[4]   New enumerative results on two-dimensional directed animals [J].
Bousquet-Melou, M .
DISCRETE MATHEMATICS, 1998, 180 (1-3) :73-106
[5]   Enumeration of directed animals on an infinite family of lattices [J].
BousquetMelou, M ;
Conway, AR .
JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL, 1996, 29 (13) :3357-3365
[6]  
Corteel S., 2000, Ann. Comb., V4, P269
[8]   EQUIVALENCE OF THE TWO-DIMENSIONAL DIRECTED ANIMAL PROBLEM TO A ONE-DIMENSIONAL PATH PROBLEM [J].
GOUYOUBEAUCHAMPS, D ;
VIENNOT, G .
ADVANCES IN APPLIED MATHEMATICS, 1988, 9 (03) :334-357
[9]   EXACT RESULTS FOR 2D DIRECTED ANIMALS ON A STRIP OF FINITE WIDTH [J].
HAKIM, V ;
NADAL, JP .
JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL, 1983, 16 (07) :L213-L218
[10]  
Le Borgne Y, 2007, ELECTRON J COMB, V14