OFFSET
1,1
COMMENTS
In 2012, Nakamigawa and Tokushige stated: Let A[x,y] = number of lattice paths starting at (0,0) that stay in y < 2*x/5 + 2/5 and B[x,y] = number of lattice paths starting at (0,0) that stay in y < 2*x/5 + 1/5, then a(t) = A[5*t-1,2*t-1] + B[5*t-1,2*t-1]. Their theorem was mentioned by D. Knuth in Problem 4 "Lattice Paths of Slope 2/5" in his lecture "Problems That Philippe (Flajolet) Would Have Loved". Knuth reported the empirical observation that A[5*t-1,2*t-1]/B[5*t-1,2*t-1] = a - b/t + O(t^-2), with constants a~=1.63026 and b~=0.159. Knuth's conjecture was proved by C. Banderier and M. Wallner, who also found the exact values of a and b. Numerical values of a and b are provided in A322632 and A322633.
LINKS
Robert Israel, Table of n, a(n) for n = 1..552
Cyril Banderier, Michael Wallner, Lattice paths of slope 2/5, arXiv:1605.02967 [cs.DM], 10 May 2016.
D. E. Knuth, Problems That Philippe Would Have Loved, Paris 2014.
Tomoki Nakamigawa, Norihide Tokushige, Counting Lattice Paths via a New Cycle Lemma, SIAM J. Discrete Math., 26(2):745-754, 2012.
FORMULA
From Robert Israel, Dec 23 2018: (Start)
7*(7*n + 4)*(7*n + 1)*(7*n + 5)*(7*n + 2)*(7*n - 1)*(7*n + 3)*a(n) - 10*(5*n + 1)*(5*n + 2)*(2*n + 1)*(5*n + 3)*(5*n + 4)*(n + 1)*a(n + 1) = 0.
G.f.: 5*x*hypergeom([6/7, 1, 8/7, 9/7, 10/7, 11/7, 12/7], [6/5, 7/5, 3/2, 8/5, 9/5, 2], (823543*x)*1/12500)
a(n) ~ sqrt(35/Pi)*(823543/12500)^n/(49*n^(3/2)). (End)
EXAMPLE
A[i,0] = B[i,0] = 1.
A[i,j] = if 5*j < 2*i + 2 then A[i-1,j] + A[i,j-1] , else 0.
\i 1 2 3 4 5 6 7 8 9 10 11 12 13 14
j --------------------------------------------------------
0| 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1| 0 1 2 3 4 5 6 7 8 9 10 11 12 13
2| 0 0 0 0 4 9 15 22 30 39 49 60 72 85
3| 0 0 0 0 0 0 15 37 67 106 155 215 287 372
4| 0 0 0 0 0 0 0 0 0 106 261 476 763 1135
5| 0 0 0 0 0 0 0 0 0 0 0 476 1239 2374
.
B[i,j] = if 5*j < 2*i + 1 then B[i-1,j] + B[i,j-1], else 0.
\i 1 2 3 4 5 6 7 8 9 10 11 12 13 14
j --------------------------------------------------------
0| 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1| 0 0 1 2 3 4 5 6 7 8 9 10 11 12
2| 0 0 0 0 3 7 12 18 25 33 42 52 63 75
3| 0 0 0 0 0 0 0 18 43 76 118 170 233 308
4| 0 0 0 0 0 0 0 0 0 76 194 364 597 905
5| 0 0 0 0 0 0 0 0 0 0 0 0 597 1502
.
A+B:
\i 1 2 3 4 5 6 7 8 9 10 11 12 13 14
j --------------------------------------------------------
0| 2 2 2 2 2 2 2 2 2 2 2 2 2 2
1| 0 1 3 5 7 9 11 13 15 17 19 21 23 25
2| 0 0 0 0 7 16 27 40 55 72 91 112 135 160
3| 0 0 0 0 0 0 15 55 110 182 273 385 520 680
4| 0 0 0 0 0 0 0 0 0 182 455 840 1360 2040
5| 0 0 0 0 0 0 0 0 0 0 0 476 1836 3876
.
t = 1: a(1) = 5 because
A[5*1-1,2*1-1] = A[4,1] = 3, B[4,1] = 2, A[4,1]+B[4,1] = 5;
t = 2: a(2) = 110 because
A[5*2-1,2*2-1] = A[9,3] = 67, B[9,3] = 43, A[9,3]+B[9,3] = 110;
t = 3: a(3) = 3876 because
A[5*3-1,2*3-1] = A[14,5] = 2374, B[14,5] = 1502, A[14,5]+B[14,5] = 3876.
MAPLE
a:=n->2*binomial(7*n-1, 2*n)/(7*n-1): seq(a(n), n=1..20); # Muniru A Asiru, Dec 21 2018
PROG
(PARI) for(t=1, 16, print1(binomial(7*t-1, 2*t)*(2/(7*t-1)), ", "))
CROSSREFS
KEYWORD
nonn,changed
AUTHOR
Hugo Pfoertner, Dec 21 2018
STATUS
approved