|
| |
|
|
A089022
|
|
Number of walks of length 2n on the 3-regular tree beginning and ending at some fixed vertex.
|
|
8
| |
|
|
1, 3, 15, 87, 543, 3543, 23823, 163719, 1143999, 8099511, 57959535, 418441191, 3043608351, 22280372247, 164008329423, 1213166815047, 9012417249663, 67208553680247, 502920171632943, 3775020828459687, 28415858155984863, 214444848602732247, 1622146752543427983
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,2
|
|
|
COMMENTS
| The generating function for the corresponding sequence for the m-regular tree is 2*(m-1)/(m-2+m*sqrt(1-4*(m-1)*x)). When m=2 this reduces to the usual generating function for the central binomial coefficients.
Hankel transform is A133460 . - Philippe DELEHAM, Dec 01 2007
|
|
|
LINKS
| Ed Pegg Jr., K-Cayley Trees
|
|
|
FORMULA
| G.f. = 4/(1+3*sqrt(1-8*x)).
a(n) = 2^x * binomial(2*x,x) - 3^(x-1) * sum( (2/3)^j*binomial(x+j,x), j=0..x-1) - Tobias Friedrich (tfried(AT)mpi-inf.mpg.de), Jun 12 2007
a(n) = Sum_{k=0..n} A039599(n,k)*2^(n-k). - Philippe DELEHAM, Aug 25 2007
Contribution from Paul Barry, Sep 04 2009: (Start)
G.f.: 1/(1-3x/(1-2x/(1-2x/(1-2x/(1-2x/(1-... (continued fraction);
G.f.: (1-2xc(x))/(1-3x-2xc(x)), c(x) the g.f. of A000108. (End)
a(n)=A126087(2n). - From DELEHAM Philippe, Nov 02 2011
Conjecture: n*a(n) +(12-17*n)*a(n-1) +36*(2n-3)*a(n-2)=0. - R. J. Mathar, Nov 14 2011
|
|
|
EXAMPLE
| a(2) = 15 because there are 3*3=9 walks whose second step is to return to the starting vertex and 3*2=6 walks whose second step is to move away from the starting vertex.
|
|
|
MAPLE
| A000602 := x -> 2^x*binomial(2*x, x)-9^x+1/3*2^x*binomial(2*x, x) * hypergeom([1, 2*x+1], [x+1], 2/3); # Tobias Friedrich (tfried(AT)mpi-inf.mpg.de), Jun 12 2007
|
|
|
CROSSREFS
| Sequence in context: A075841 A152596 A168503 * A132371 A192989 A192253
Adjacent sequences: A089019 A089020 A089021 * A089023 A089024 A089025
|
|
|
KEYWORD
| easy,nonn
|
|
|
AUTHOR
| Paul Boddington (psb(AT)maths.warwick.ac.uk), Nov 11 2003
|
| |
|
|
