A247630 Number of paths from (0,0) to the line x = n, each segment given by a vector (1,1), (1,-1), or (2,0), not crossing the x-axis, and including no horizontal segment on the x-axis.

1, 1, 2, 4, 10, 20, 50, 104, 258, 552, 1362, 2972, 7306, 16172, 39650, 88720, 217090, 489872, 1196834, 2719028, 6634890, 15157188, 36949266, 84799992, 206549250, 475894200, 1158337650, 2677788492, 6513914634, 15102309468, 36718533570, 85347160608

Offset: 0

Author

Clark Kimberling, Sep 21 2014

Keywords

• nonn
• easy

Comments

a(n) = sum of the numbers in row n of the triangle at A247629.

Examples

			First 9 rows:
1
0 ... 1
1 ... 0 ... 1
0 ... 3 ... 0 ... 1
4 ... 0 ... 5 ... 0 ... 1
0 ... 12 .. 0 ... 7 ... 0 ...1
16 .. 0 ... 24 .. 0 ... 9 ... 0 ... 1
0 ... 52 .. 0 ... 40 .. 0 ... 11 .. 0 ... 1
68 .. 0 ... 116 . 0 ... 60 .. 0 ... 13 .. 0 ... 1
T(4,2) counts these 5 paths given as vector sums applied to (0,0):
(1,1) + (1,1) + (1,1) + (1,-1)
(1,1) + (1,1) + (2,0)
(1,1) + (1,1) + (1,-1) + (1,1)
(1,1) + (2,0) + (1,1)
(1,1) + (1,-1) + (1,1) + (1,-1)
a(4) = 4 + 0 + 5 + 0 + 1 = 10.
		

Links

• Clark Kimberling, Table of n, a(n) for n = 0..1000

Crossrefs

Cf. A247629, A247623.

Programs

Mathematica

t[0, 0] = 1; t[1, 1] = 1; t[2, 0] = 1; t[2, 2] = 1; t[n_, k_] := t[n, k] = If[n >= 2 && k >= 1,    t[n - 1, k - 1] + t[n - 1, k + 1] + t[n - 2, k], 0]; t[n_, 0] := t[n, 0] = If[n >= 2, t[n - 2, 0] + t[n - 1, 1], 0]; u = Table[t[n, k], {n, 0, 16}, {k, 0, n}]; TableForm[u] (* A247629 array *)
v = Flatten[u] (* A247629 sequence *)
Map[Total, u] (* A247630 *)

Formula

Conjecture: -(n+1)*(n-2)*a(n) -(n-1)*(n-4)*a(n-1) +2*(3*n-2)*(n-2)*a(n-2) +2*(3*n-5)*(n-3)*a(n-3) +(-n^2+7*n-2)*a(n-4) -(n-1)*(n-6)*a(n-5)=0. - R. J. Mathar, Sep 23 2014