login
a(n) = 2*binomial(7*n-1,2*n)/(7*n-1).
4

%I #22 Dec 24 2018 03:37:45

%S 5,110,3876,164450,7713420,385300240,20096692635,1081790956890,

%T 59647783837425,3351648108957720,191230475831922200,

%U 11049110585626417200,645189590847792998601,38014810319396501088720,2257261555792984515847380,134939208350635886836436490

%N a(n) = 2*binomial(7*n-1,2*n)/(7*n-1).

%C 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.

%H Robert Israel, <a href="/A322631/b322631.txt">Table of n, a(n) for n = 1..552</a>

%H Cyril Banderier, Michael Wallner, <a href="https://arxiv.org/abs/1605.02967">Lattice paths of slope 2/5</a>, arXiv:1605.02967 [cs.DM], 10 May 2016.

%H D. E. Knuth, <a href="http://www-cs-faculty.stanford.edu/~uno/flaj2014.pdf">Problems That Philippe Would Have Loved</a>, Paris 2014.

%H Tomoki Nakamigawa, Norihide Tokushige, <a href="http://doi.org/10.1137/100796431">Counting Lattice Paths via a New Cycle Lemma, SIAM J. Discrete Math., 26(2):745-754, 2012.

%F From _Robert Israel_, Dec 23 2018: (Start)

%F 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.

%F 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)

%F a(n) ~ sqrt(35/Pi)*(823543/12500)^n/(49*n^(3/2)). (End)

%e A[i,0] = B[i,0] = 1.

%e A[i,j] = if 5*j < 2*i + 2 then A[i-1,j] + A[i,j-1] , else 0.

%e \i 1 2 3 4 5 6 7 8 9 10 11 12 13 14

%e j --------------------------------------------------------

%e 0| 1 1 1 1 1 1 1 1 1 1 1 1 1 1

%e 1| 0 1 2 3 4 5 6 7 8 9 10 11 12 13

%e 2| 0 0 0 0 4 9 15 22 30 39 49 60 72 85

%e 3| 0 0 0 0 0 0 15 37 67 106 155 215 287 372

%e 4| 0 0 0 0 0 0 0 0 0 106 261 476 763 1135

%e 5| 0 0 0 0 0 0 0 0 0 0 0 476 1239 2374

%e .

%e B[i,j] = if 5*j < 2*i + 1 then B[i-1,j] + B[i,j-1], else 0.

%e \i 1 2 3 4 5 6 7 8 9 10 11 12 13 14

%e j --------------------------------------------------------

%e 0| 1 1 1 1 1 1 1 1 1 1 1 1 1 1

%e 1| 0 0 1 2 3 4 5 6 7 8 9 10 11 12

%e 2| 0 0 0 0 3 7 12 18 25 33 42 52 63 75

%e 3| 0 0 0 0 0 0 0 18 43 76 118 170 233 308

%e 4| 0 0 0 0 0 0 0 0 0 76 194 364 597 905

%e 5| 0 0 0 0 0 0 0 0 0 0 0 0 597 1502

%e .

%e A+B:

%e \i 1 2 3 4 5 6 7 8 9 10 11 12 13 14

%e j --------------------------------------------------------

%e 0| 2 2 2 2 2 2 2 2 2 2 2 2 2 2

%e 1| 0 1 3 5 7 9 11 13 15 17 19 21 23 25

%e 2| 0 0 0 0 7 16 27 40 55 72 91 112 135 160

%e 3| 0 0 0 0 0 0 15 55 110 182 273 385 520 680

%e 4| 0 0 0 0 0 0 0 0 0 182 455 840 1360 2040

%e 5| 0 0 0 0 0 0 0 0 0 0 0 476 1836 3876

%e .

%e t = 1: a(1) = 5 because

%e A[5*1-1,2*1-1] = A[4,1] = 3, B[4,1] = 2, A[4,1]+B[4,1] = 5;

%e t = 2: a(2) = 110 because

%e A[5*2-1,2*2-1] = A[9,3] = 67, B[9,3] = 43, A[9,3]+B[9,3] = 110;

%e t = 3: a(3) = 3876 because

%e A[5*3-1,2*3-1] = A[14,5] = 2374, B[14,5] = 1502, A[14,5]+B[14,5] = 3876.

%p a:=n->2*binomial(7*n-1,2*n)/(7*n-1): seq(a(n),n=1..20); # _Muniru A Asiru_, Dec 21 2018

%o (PARI) for(t=1,16,print1(binomial(7*t-1,2*t)*(2/(7*t-1)),", "))

%Y Cf. A274052, A322632, A322633.

%K nonn

%O 1,1

%A _Hugo Pfoertner_, Dec 21 2018