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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005022 Number of walks of length 2n+6 in the path graph P_7 from one end to the other.
(Formerly M4171)
3
6, 26, 100, 364, 1288, 4488, 15504, 53296, 182688, 625184, 2137408, 7303360, 24946816, 85196928, 290926848, 993379072, 3391793664, 11580678656, 39539651584, 134998297600, 460915984384, 1573671536640, 5372862566400, 18344123969536, 62630804299776 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

REFERENCES

W. Feller, An Introduction to Probability Theory and its Applications, 3rd ed, Wiley, New York, 1968, p. 96.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

LINKS

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

C. J. Everett, P. R. Stein, The combinatorics of random walk with absorbing barriers, Discrete Math. 17 (1977), no. 1, 27-45.

C. J. Everett, P. R. Stein, The combinatorics of random walk with absorbing barriers, Discrete Math. 17 (1977), no. 1, 27-45. [Annotated scanned copy]

P. Flajolet, J.-C. Raoult, and J. Vuillemin, The number of registers required for evaluating arithmetic expressions, Theoret. Comput. Sci. 9 (1979), no. 1, 99-125.

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992.

Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 1992.

Xavier Gérard Viennot, A Strahler bijection between Dyck paths and planar trees. Formal power series and algebraic combinatorics (Barcelona, 1999). Discrete Math. 246 (2002), no. 1-3, 317--329. MR1887493 (2003b:05013).

Index entries for linear recurrences with constant coefficients, signature (6,-10,4).

FORMULA

G.f.: 1/(1-6x+10x^2-4x^3)-1.

a(n) = 6*a(n-1)-10*a(n-2)+4*a(n-3). - Emeric Deutsch, Apr 02 2004

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

The g.f. x^3/(1-6*x+10*x^2-4*x^3) occurs on page 320 of Viennot, 2002.

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

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

EXAMPLE

Example: a(1)=6 because in the path ABCDEFG we have ABABCDEFG, ABCBCDEFG, ABCDCDEFG, ABCDEDEFG, ABCDEFEFG and ABCDEFGFG. - Emeric Deutsch, Apr 02 2004

MAPLE

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

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.]

MATHEMATICA

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

CoefficientList[Series[(1 / x) (1 / (1 - 6 x + 10 x^2 - 4 x^3) - 1), {x, 0, 50}], x] (* Vincenzo Librandi, Jun 08 2013 *)

PROG

(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

(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

CROSSREFS

See A094811 for another version.

Sequence in context: A137746 A261064 A094811 * A125107 A301476 A290347

Adjacent sequences:  A005019 A005020 A005021 * A005023 A005024 A005025

KEYWORD

nonn,walk,easy

AUTHOR

N. J. A. Sloane, Simon Plouffe

EXTENSIONS

Edited by Emeric Deutsch, Apr 28 2004

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 13 17:34 EST 2019. Contains 329106 sequences. (Running on oeis4.)