|
Search: id:A089022
|
|
|
| A089022 |
|
Number of walks of length 2n on the 3-regular tree beginning and ending at some fixed vertex. |
|
+0
6
|
|
| 1, 3, 15, 87, 543, 3543, 23823, 163719, 1143999, 8099511, 57959535, 418441191, 3043608351, 22280372247, 164008329423, 1213166815047, 9012417249663, 67208553680247
(list; graph; listen)
|
|
|
OFFSET
|
0,2
|
|
|
COMMENT
|
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 (kolotoko(AT)wanadoo.fr), 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<=k<=n}A039599(n,k)*2^(n-k). - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Aug 25 2007
|
|
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: A093615 A001931 A075841 this_sequence A132371 A127785 A074541
Adjacent sequences: A089019 A089020 A089021 this_sequence A089023 A089024 A089025
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
Paul Boddington (psb(AT)maths.warwick.ac.uk), Nov 11 2003
|
|
|
Search completed in 0.002 seconds
|
