|
| |
|
|
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
|
Everett, C. J.; Stein, P. R.; The combinatorics of random walk with absorbing barriers. Discrete Math. 17 (1977), no. 1, 27-45.
W. Feller, An Introduction to Probability Theory and its Applications, 3rd ed, Wiley, New York, 1968, p. 96.
Flajolet, P.; Raoult, J.-C.; Vuillemin, J.; The number of registers required for evaluating arithmetic expressions. Theoret. Comput. Sci. 9 (1979), no. 1, 99-125.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Viennot, Xavier Gérard. 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)
|
|
|
LINKS
|
Table of n, a(n) for n=1..25.
_Simon Plouffe_, Approximations de S\'{e}ries G\'{e}n\'{e}ratrices et Quelques Conjectures, Dissertation, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
_Simon Plouffe_, 1031 Generating Functions and Conjectures, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
|
|
|
FORMULA
|
G.f.: 1/(1-6x+10x^2-4x^3)-1.
a(n)=6a(n-1)-10a(n-2)+4a(n-3). - Emeric Deutsch, Apr 02 2004
a(k)=sum(binomial(6+2k, 8j+k-2)-binomial(6+2k, 8j+k-1), j=-infinity..infinity) (a finite sum).
The g.f. x^3/(1-6x+10x^2-4x^3) occurs on page 320 of Viennot, 2002.
|
|
|
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] (* From Vladimir Joseph Stephan Orlovsky, Jun 27 2011 *)
|
|
|
CROSSREFS
|
See A094811 for another version.
Sequence in context: A055420 A137746 A094811 * A125107 A034560 A143955
Adjacent sequences: A005019 A005020 A005021 * A005023 A005024 A005025
|
|
|
KEYWORD
|
nonn,walk
|
|
|
AUTHOR
|
N. J. A. Sloane, Simon Plouffe
|
|
|
EXTENSIONS
|
Edited by Emeric Deutsch, Apr 28 2004
|
|
|
STATUS
|
approved
|
| |
|
|
