cp's OEIS Frontend

A005022 Number of walks of length 2n+6 in the path graph P_7 from one end to the other.

%I A005022 M4171 #56 Sep 08 2022 08:44:33
%S A005022 6,26,100,364,1288,4488,15504,53296,182688,625184,2137408,7303360,
%T A005022 24946816,85196928,290926848,993379072,3391793664,11580678656,
%U A005022 39539651584,134998297600,460915984384,1573671536640,5372862566400,18344123969536,62630804299776
%N A005022 Number of walks of length 2n+6 in the path graph P_7 from one end to the other.
%D A005022 W. Feller, An Introduction to Probability Theory and its Applications, 3rd ed, Wiley, New York, 1968, p. 96.
%D A005022 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A005022 Vincenzo Librandi, <a href="/A005022/b005022.txt">Table of n, a(n) for n = 1..1000</a>
%H A005022 C. J. Everett, P. R. Stein, <a href="http://dx.doi.org/10.1016/0012-365X(77)90019-X">The combinatorics of random walk with absorbing barriers</a>, Discrete Math. 17 (1977), no. 1, 27-45.
%H A005022 C. J. Everett, P. R. Stein, <a href="/A005021/a005021.pdf">The combinatorics of random walk with absorbing barriers</a>, Discrete Math. 17 (1977), no. 1, 27-45. [Annotated scanned copy]
%H A005022 P. Flajolet, J.-C. Raoult, and J. Vuillemin, <a href="http://dx.doi.org/10.1016/0304-3975(79)90009-4">The number of registers required for evaluating arithmetic expressions</a>, Theoret. Comput. Sci. 9 (1979), no. 1, 99-125.
%H A005022 Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H A005022 Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992
%H A005022 Xavier Gérard Viennot, <a href="http://dx.doi.org/10.1016/S0012-365X(01)00265-5">A Strahler bijection between Dyck paths and planar trees</a>. Formal power series and algebraic combinatorics (Barcelona, 1999). Discrete Math. 246 (2002), no. 1-3, 317--329. MR1887493 (2003b:05013).
%H A005022 <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (6,-10,4).
%F A005022 G.f.: 1/(1-6x+10x^2-4x^3)-1.
%F A005022 a(n) = 6*a(n-1)-10*a(n-2)+4*a(n-3). - _Emeric Deutsch_, Apr 02 2004
%F A005022 a(k) = sum(binomial(6+2*k, 8*j+k-2)-binomial(6+2*k, 8*j+k-1), j=-infinity..infinity) (a finite sum).
%F A005022 The g.f. x^3/(1-6*x+10*x^2-4*x^3) occurs on page 320 of Viennot, 2002.
%F A005022 a(n) = -2^(1+n)+(3/2-sqrt(2))*(2-sqrt(2))^n+(3/2+sqrt(2))*(2+sqrt(2))^n - _Colin Barker_, Apr 27 2016
%F A005022 E.g.f.: (-2 + 3*cosh(sqrt(2)*x) + 2*sqrt(2)*sinh(sqrt(2)*x))*exp(2*x) - 1. - _Ilya Gutkovskiy_, Apr 27 2016
%e A005022 Example: a(1)=6 because in the path ABCDEFG we have ABABCDEFG, ABCBCDEFG, ABCDCDEFG, ABCDEDEFG, ABCDEFEFG and ABCDEFGFG. - _Emeric Deutsch_, Apr 02 2004
%p A005022 a:=k->sum(binomial(6+2*k,8*j+k-2),j=ceil((2-k)/8)..floor((8+k)/8))-sum(binomial(6+2*k,8*j+k-1),j=ceil((1-k)/8)..floor((7+k)/8)): seq(a(k),k=1..28);
%p A005022 A005022:=-1/((2*z-1)*(2*z**2-4*z+1)) -1; # [Conjectured (correctly) by _Simon Plouffe_ in his 1992 dissertation. Gives sequence with an additional leading term of 1.]
%t A005022 CoefficientList[Series[-(2 (2 z^2 - 5 z + 3))/(4 z^3 - 10 z^2 + 6 z - 1), {z, 0, 100}], z] (* _Vladimir Joseph Stephan Orlovsky_, Jun 27 2011 *)
%t A005022 CoefficientList[Series[(1 / x) (1 / (1 - 6 x + 10 x^2 - 4 x^3) - 1), {x, 0, 50}], x] (* _Vincenzo Librandi_, Jun 08 2013 *)
%o A005022 (Magma)  I:=[6, 26, 100]; [n le 3 select I[n] else 6*Self(n-1)-10*Self(n-2)+4*Self(n-3): n in [1..30]]; // _Vincenzo Librandi_, Jun 08 2013
%o A005022 (PARI) Vec(2*(1-x)*(3-2*x) / ((1-2*x)*(1-4*x+2*x^2)) + O(x^50)) \\ _Colin Barker_, Apr 27 2016
%Y A005022 See A094811 for another version.
%K A005022 nonn,walk,easy
%O A005022 1,1
%A A005022 _N. J. A. Sloane_, _Simon Plouffe_
%E A005022 Edited by _Emeric Deutsch_, Apr 28 2004