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,4

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.

Links

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

Formula

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

Example

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

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 *)

Prog

(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

Crossrefs

Cf. A055113, A185286, A187430.

Sequence in context: A003757 A187985 A320043 * A064521 A367663 A330283

Adjacent sequences: A296616 A296617 A296618 * A296620 A296621 A296622

Keyword

nonn,walk

Author

Feng Jishe, Dec 17 2017

Status

approved