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

5, 110, 3876, 164450, 7713420, 385300240, 20096692635, 1081790956890, 59647783837425, 3351648108957720, 191230475831922200, 11049110585626417200, 645189590847792998601, 38014810319396501088720, 2257261555792984515847380, 134939208350635886836436490

Offset: 1

Author

Hugo Pfoertner, Dec 21 2018

Keywords

• nonn

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.

Examples

			  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.
		

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.

Crossrefs

Cf. A274052, A322632, A322633.

Programs

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

PARI

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

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)