A185286 Triangle T(n,k) is the number of nonnegative walks of n steps with step sizes 1 and 2, starting at 0 and ending at k.

1, 0, 1, 1, 2, 1, 1, 2, 1, 2, 5, 6, 3, 3, 3, 1, 11, 11, 13, 17, 13, 7, 6, 4, 1, 24, 41, 52, 44, 43, 40, 25, 14, 10, 5, 1, 93, 120, 152, 176, 161, 126, 107, 80, 45, 25, 15, 6, 1, 272, 421, 550, 559, 561, 524, 412, 303, 227, 146, 77, 41, 21, 7, 1, 971, 1381, 1813, 2056, 2045, 1835, 1615, 1309, 938, 648, 435, 251, 126, 63, 28, 8, 1

Offset: 0

Author

Franklin T. Adams-Watters, Mar 10 2011

Keywords

• nonn
• walk
• tabf

Comments

Equivalently, the number of paths from (0,0) to (n,k) using steps of the form (1,2),(1,1),(1,-1) or (1,-2) and staying on or above the x-axis.

It appears that A047002 gives the row sums of this triangle.

Examples

			The table starts:
1
0,1,1
2,1,1,2,1
2,5,6,3,3,3,1
		

Links

• Robert Israel, Table of n, a(n) for n = 0..10200

Crossrefs

Columns k=0..2 are A187430, A055113, A296619.

Cf. A005408(row lengths), A047002(apparently row sums).

Programs

Maple

T:= proc(n,k) option remember;
  if k < 0 or k > 2*n then return 0 fi;
  procname(n-1,k-2)+procname(n-1,k-1)+procname(n-1,k+1)+procname(n-1,k+2)
end proc:
T(0,0):= 1:
for nn from 0 to 10 do
  seq(T(nn,k),k=0..2*nn)
od; # Robert Israel, Dec 19 2017

Mathematica

T[n_, k_] := T[n, k] = If[k < 0 || k > 2n, 0, T[n-1, k-2] + T[n-1, k-1] + T[n-1, k+1] + T[n-1, k+2]];
T[0, 0] = 1;
Table[T[n, k], {n, 0, 10}, {k, 0, 2n}] // Flatten (* Jean-François Alcover, Aug 19 2022, after Robert Israel *)

PARI

flip(v)=vector(#v,i,v[#v+1-i])
ar(n)={local(p);p=1;
for(k=1,n,p*=1+x+x^3+x^4;p=(p-polcoeff(p,0)-polcoeff(p,1)*x)/x^2);
flip(Vec(p))}