A300391 The number of paths of length 8*n from the origin to the line y = 3*x/5 with unit east and north steps that stay below the line or touch it.

1, 7, 525, 58040, 7574994, 1084532963, 164734116407, 26070940600055, 4252443527211637, 709846349042619913, 120679177855928146859, 20822762876863605793639, 3637213213067542990001936, 641912742432770594132245835, 114287840570892852593437353124, 20502971288127330644273350110698

Offset

0,2

Comments

Equivalent to nonnegative walks from (0,0) to (8*n,0) with step set [1,3], [1,-5].

Links

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

M. T. L. Bizley, Derivation of a new formula for the number of minimal lattice paths from (0, 0) to (km, kn) having just t contacts with the line my = nx and having no points above this line; and a proof of Grossman's formula for the number of paths which may touch but do not rise above this line, Journal of the Institute of Actuaries, Vol. 80, No. 1 (1954): 55-62. [Cached copy]

Bryan Ek, Lattice Walk Enumeration, arXiv:1803.10920 [math.CO], 2018.

Bryan Ek, Unimodal Polynomials and Lattice Walk Enumeration with Experimental Mathematics, arXiv:1804.05933 [math.CO], 2018.

Formula

G.f. f satisfies f = t^7*f^56 - 2*t^6*f^51 + t^6*f^50 - t^6*f^49 + 7*t^6*f^48 + t^5*f^46 - t^5*f^45 - 3*t^5*f^43 + 5*t^5*f^42 - 6*t^5*f^41 + 21*t^5*f^40 - 3*t^4*f^37 - 3*t^4*f^36 + 8*t^4*f^35 + 10*t^4*f^34 - 15*t^4*f^33 + 35*t^4*f^32 - 2*t^3*f^31 + 2*t^3*f^30 - 9*t^3*f^28 + 22*t^3*f^27 + 10*t^3*f^26 - 20*t^3*f^25 + 35*t^3*f^24 + 3*t^2*f^22 + 5*t^2*f^21 - 9*t^2*f^20 + 18*t^2*f^19 + 5*t^2*f^18 - 15*t^2*f^17 + t*(21*t + 1)*f^16 - t*f^15 + 3*t*f^13 - 3*t*f^12 + 5*t*f^11 + t*f^10 - 6*t*f^9 + 7*t*f^8 + 1.

From Peter Bala, Jan 03 2019: (Start)

O.g.f.: A(x) = exp( Sum_{n >= 1} (1/8)*binomial(8*n, 3*n)*x^n/n ) - Bizley.

Recurrence: a(0) = 1 and a(n) = (1/n) * Sum_{k = 0..n-1} (1/8)*binomial(8*n-8*k, 3*n-3*k)*a(k) for n >= 1. (End)

Example

For n=1, the possible walks are EEEEENNN, EEEENENN, EEEENNEN, EEENEENN, EEENENEN, EENEEENN, EENEENEN.

Crossrefs

Cf. A001764, A060941, A300386, A300387, A300388, A300389, A300390.

Sequence in context: A124899 A056852 A316394 * A126196 A182433 A329368

Adjacent sequences: A300388 A300389 A300390 * A300392 A300393 A300394

Keyword

nonn,walk,easy

Author

Bryan T. Ek, Mar 05 2018

Status

approved