A274244 Number of factor-free Dyck words with slope 7/2 and length 9n.

1, 4, 34, 494, 8615, 165550, 3380923, 71999763, 1580990725, 35537491360, 813691565184, 18911247654404, 444978958424224, 10579389908116344, 253756528273411250, 6133110915783398175, 149219383150626519874, 3651756292682801022384, 89830021324956206790496, 2219945238901447637080235, 55088272581138888326634644

Offset

0,2

Comments

a(n) is the number of lattice paths (allowing only north and east steps) starting at (0,0) and ending at (2n,7n) that stay below the line y=7/2x and also do not contain a proper subpath of smaller size.

Links

Table of n, a(n) for n=0..20.

Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, On rational Dyck paths and the enumeration of factor-free Dyck words, arXiv:1606.02183 [math.CO], 2016.

P. Duchon, On the enumeration and generation of generalized Dyck words, Discrete Mathematics, 225 (2000), 121-135.

Formula

Conjectural o.g.f.: Let E(x) = exp( Sum_{n >= 1} binomial(9*n, 2*n)*x^n/n ). Then A(x) = ( x/series reversion of x*E(x) )^(1/9) = 1 + 4*x + 34*x^2 + 494*x^3 + ... . Equivalently, [x^n]( A(x)^(9*n) ) = binomial(9*n, 2*n) for n = 0,1,2,... . - Peter Bala, Jan 01 2020

Example

a(2) = 34 since there are 34 lattice paths (allowing only north and east steps) starting at (0,0) and ending at (4,14) that stay below the line y=7/2x and also do not contain a proper subpath of small size; e.g., EEENNNNENNNNNNNNNN is a factor-free Dyck word but EEENNENNNNNNNNNNNN contains the factor ENNENNNNN.

Crossrefs

Factor-free Dyck words: A005807 (slope 3/2), A274052 (slope 5/2), A274256 (slope 9/2), A274257 (slope 4/3), A274259 (slope 7/3).

Cf. A060941.

Sequence in context: A248654 A336495 A111169 * A002105 A198717 A198908

Adjacent sequences: A274241 A274242 A274243 * A274245 A274246 A274247

Keyword

nonn

Author

Michael D. Weiner, Jun 15 2016

Status

approved