cp's OEIS Frontend

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

%I A296619 #57 Apr 29 2018 21:38:09
%S A296619 0,1,1,6,13,52,152,550,1813,6453,22427,80330,286895,1038931,3772801,
%T A296619 13807294,50726893,187332517,694364517,2583714636,9644852364,
%U A296619 36115537269,135607526865,510496492338,1926284451923,7284476707597,27602839227883,104791979218326
%N A296619 The number of nonnegative walks of n steps with step sizes 1 and 2, starting at 0 and ending at 2.
%C A296619 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.
%C A296619 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.
%H A296619 Robert Israel, <a href="/A296619/b296619.txt">Table of n, a(n) for n = 0..1667</a>
%F A296619 a(n) = A185286(n,2). - _Robert Israel_, Dec 19 2017
%e A296619 There are 6 walks of length 3:
%e A296619         __
%e A296619        |  |         __
%e A296619      __|  |_     __|  |_     __    _
%e A296619     |           |           |  |__|
%e A296619    _|          _|          _|
%e A296619     2+2-2=2     2+1-1=2     2-1+1=2
%e A296619                     __
%e A296619      __    _       |  |_           _
%e A296619     |  |  |      __|         __   |
%e A296619    _|  |__|    _|          _|  |__|
%e A296619     2-2+2=2     1+2-1=2     1-1+2=2
%p A296619 B := n -> LinearAlgebra:-ToeplitzMatrix([0,1,1, seq(0, k=0..n-2)], symmetric):
%p A296619 seq((B(n)^n)(1, 3), n=0..27);
%p A296619 # alternative:
%p A296619 T:= proc(n,k) option remember;
%p A296619   if k < 0 or k > 2*n then return 0 fi;
%p A296619   procname(n-1,k-2)+procname(n-1,k-1)+procname(n-1,k+1)+procname(n-1,k+2)
%p A296619 end proc:
%p A296619 T(0,0):= 1:
%p A296619 seq(T(n,2),n=0..40); # _Robert Israel_, Dec 19 2017
%t A296619 b[n_] := ToeplitzMatrix[Join[{0,1,1}, ConstantArray[0,n-1]]];
%t A296619 Prepend[Table[MatrixPower[b[n],n][[1,3]], {n,20}], 0]
%t A296619 (* _Andrey Zabolotskiy_, Dec 19 2017 *)
%o A296619 (PARI)
%o A296619 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]))}
%o A296619 my(v=vector(7,i,i==3)); for(n=1, 50, print1(v[5],", "); v=Next(v)) \\ _Andrew Howroyd_, Dec 18 2017
%Y A296619 Cf. A055113, A185286, A187430.
%K A296619 nonn,walk
%O A296619 0,4
%A A296619 _Feng Jishe_, Dec 17 2017