login
A094149
The 2k-th moments of the random graph G(n, 1/n) (odd moments are zero). The number of walks of length 2k on _all_ bushes (rooted plane trees) that start and end at the root and visit new vertices from left-to-right (but may return).
0
1, 3, 12, 57, 303, 1747, 10727, 69331, 467963, 3280353, 23785699, 177877932, 1368977132
OFFSET
1,2
REFERENCES
A. Spiridonov, Spectra of sparse graphs and matrices, in preparation, contact submitter for preprints.
FORMULA
See [link:1] for a complex recurrence relationship. Asymptotically between A_k (the k-th Bell number, A000110) and choose(2k, k)*A_k. (see [ref:1]).
EXAMPLE
The bushes with 1..3 edges (counted by the Catalan numbers, A000108):
*...*...*...*....*....*....*...*
|../.\..|../|\../.\../.\...|...|
........|.......|......|../.\..|
...............................|
1 + 0 + 0 + 0 +. 0 +. 0 +. 0 + 0 + ... = 1 = number of walks of length 1
1 + 1 + 1 + 0 +. 0 +. 0 +. 0 + 0 + ... = 3 = number of walks of length 2
1 + 3 + 3 + 1 +. 1 +. 1 +. 1 + 1 + ... = 12 = number of walks of length 3
CROSSREFS
Sequence in context: A369484 A151498 A103370 * A291695 A117107 A159609
KEYWORD
nonn
AUTHOR
Alexey Spiridonov (aspirido(AT)princeton.edu), May 04 2004
STATUS
approved