A274258 Number of factor-free Dyck words with slope 5/3 and length 8n.

1, 7, 133, 4140, 154938, 6398717, 281086555, 12882897819, 609038885805, 29481041746958, 1453894927584477, 72789271870852237, 3689808842747726368, 189006099916444293090, 9768094831949586349262, 508712466332195692590121, 26670630123516854616641671, 1406503552584980596900001922, 74559627811441047591493767590

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 (3n,5n) that stay below the line y=5/3x and also do not contain a proper subpath of smaller size.

Links

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

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(8*n, 3*n)*x^n/n ). Then A(x) = ( x/series reversion of x*E(x) )^(1/8) = 1 + 7*x + 133*x^2 + 4140*x^3 + ... . Equivalently, [x^n]( A(x)^(8*n) ) = binomial(8*n, 3*n) for n = 0,1,2,... . - Peter Bala, Jan 01 2020

Example

a(2) = 133 since there are 133 lattice paths (allowing only north and east steps) starting at (0,0) and ending at (6,10) that stay below the line y=5/3x and also do not contain a proper subpath of small size; e.g., ENEEEENNNNENNNNN is a factor-free Dyck word but ENEENNENNNEENNNN contains the factor EENNENNN.

Crossrefs

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

Sequence in context: A245318 A370782 A274788 * A251577 A082164 A229464

Adjacent sequences: A274255 A274256 A274257 * A274259 A274260 A274261

Keyword

nonn

Author

Michael D. Weiner, Jun 16 2016

Status

approved