A300386 The number of paths of length 7*n from the origin to the line y = 2*x/5 with unit East and North steps that stay below the line or touch it.

1, 3, 76, 2803, 121637, 5782513, 291437249, 15297882929, 827402061954, 45790180469312, 2580588279994441, 147592910517101281, 8544927937132306600, 499811636639428519226, 29491983283370728013309, 1753398440591481772556798, 104933899400256659634374549, 6316334518803437568442071134

Offset

0,2

Comments

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

Links

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

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. satisfies: f=f^21*t^3+2*f^16*t^2-f^15*t^2+3*f^14*t^2+f^11*t-f^10*t+2*f^9*t-2*f^8*t+3*f^7*t+1.

From Peter Bala, Jan 02 2019: (Start)

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

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

The sequence defined by b(n) := [x^n] A(x)^n begins [1, 3, 161, 9804, 630401, 41789278, 2824792568, 193553976353, ...] and conjecturally satisfies the congruence b(p) == b(1) (mod p^3) for prime p >= 11 (checked up to p = 101). - Peter Bala, Sep 14 2021

a(n) ~ c * 7^(7*n) / (n^(3/2) * 2^(2*n) * 5^(5*n)), where c = 0.0538519123304380623474844037127876191519207214308040151922885271364215631... = s*sqrt((3 - 2*s + 2*s^2 - s^3 + s^4 + 6*r*s^7 - 2*r*s^8 + 4*r*s^9 + 3*r^2*s^14) / (63 - 56*s + 72*s^2 - 45*s^3 + 55*s^4 + 273*r*s^7 - 105*r*s^8 + 240*r*s^9 + 210*r^2*s^14)) / (2*sqrt(Pi)), where r = 12500/823543 and s = 1.129379978325... is the root of the equation -16807 + 24010*s - 13720*s^2 + 7350*s^3 - 3500*s^4 + 1250*s^5 = 0. - Vaclav Kotesovec, Sep 16 2021

Example

For n=1, the possible walks are EEEEENN, EEEENEN, EEENEEN.

Mathematica

terms = 18; f[_] = 0;
Do[f[t_] = f[t]^21 t^3 + 2 f[t]^16 t^2 - f[t]^15 t^2 + 3 f[t]^14 t^2 + f[t]^11 t - f[t]^10 t + 2 f[t]^9 t - 2 f[t]^8 t + 3 f[t]^7 t + 1 + O[t]^terms, {terms}];
CoefficientList[f[t], t] (* Jean-François Alcover, Dec 04 2018 *)
nmax = 20; CoefficientList[Series[Exp[Sum[Binomial[7*k, 2*k]*x^k/(7*k), {k, 1, nmax}]], {x, 0, nmax}], x] (* Vaclav Kotesovec, Sep 16 2021 *)

Crossrefs

Cf. A001764, A060941, A300387, A300388, A300389, A274052.

Sequence in context: A042267 A201428 A141103 * A054747 A302375 A232030

Adjacent sequences: A300383 A300384 A300385 * A300387 A300388 A300389

Keyword

nonn,walk

Author

Bryan T. Ek, Mar 04 2018

Status

approved