A296619 The number of nonnegative walks of n steps with step sizes 1 and 2, starting at 0 and ending at 2.

0, 1, 1, 6, 13, 52, 152, 550, 1813, 6453, 22427, 80330, 286895, 1038931, 3772801, 13807294, 50726893, 187332517, 694364517, 2583714636, 9644852364, 36115537269, 135607526865, 510496492338, 1926284451923, 7284476707597, 27602839227883, 104791979218326

Offset: 0

Author

Feng Jishe, Dec 17 2017

Keywords

• nonn
• walk

Comments

a(n) is the number of 2-D walks with n steps of type {(1,-2), (1,-1), (1,1), or (1,2)} starting at (0,0), ending at (n,2), and not dropping below the x-axis.

The sequence corresponds to element (1,3) of the matrix B(n)^n (see Maple script). Furthermore, element (1,1) of the matrix is A187430, the element (1,2) of these matrix is A055113.

Examples

			There are 6 walks of length 3:
        __
       |  |         __
     __|  |_     __|  |_     __    _
    |           |           |  |__|
   _|          _|          _|
    2+2-2=2     2+1-1=2     2-1+1=2
                    __
     __    _       |  |_           _
    |  |  |      __|         __   |
   _|  |__|    _|          _|  |__|
    2-2+2=2     1+2-1=2     1-1+2=2
		

Links

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

Crossrefs

Cf. A055113, A185286, A187430.

Programs

Maple

B := n -> LinearAlgebra:-ToeplitzMatrix([0,1,1, seq(0, k=0..n-2)], symmetric):
seq((B(n)^n)(1, 3), n=0..27);
# alternative:
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:
seq(T(n,2),n=0..40); # Robert Israel, Dec 19 2017

Mathematica

b[n_] := ToeplitzMatrix[Join[{0,1,1}, ConstantArray[0,n-1]]];
Prepend[Table[MatrixPower[b[n],n][[1,3]], {n,20}], 0]
(* Andrey Zabolotskiy, Dec 19 2017 *)

PARI

Next(v)={vector(#v+2, i, if(i<3||i>#v-2, 0, v[i-2]+v[i-1]+v[i+1]+v[i+2]))}
my(v=vector(7,i,i==3)); for(n=1, 50, print1(v[5],", "); v=Next(v)) \\ Andrew Howroyd, Dec 18 2017

Formula

a(n) = A185286(n,2). - Robert Israel, Dec 19 2017