login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A296619 The number of nonnegative walks of n steps with step sizes 1 and 2, starting at 0 and ending at 2. 3
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 (list; graph; refs; listen; history; text; internal format)
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 A262238 A111366

Adjacent sequences:  A296616 A296617 A296618 * A296620 A296621 A296622

KEYWORD

nonn,walk

AUTHOR

Feng Jishe, Dec 17 2017

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 11 22:31 EST 2019. Contains 329046 sequences. (Running on oeis4.)