|
| |
|
|
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
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,2
|
|
|
REFERENCES
| A. Spiridonov, Spectra of sparse graphs and matrices, in preparation, contact submitter for preprints.
|
|
|
LINKS
| A. Khorunzhy, On asymptotic solvability of random graph's laplacians, preprint, 2000
|
|
|
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
| Cf. A000108, A000110.
Sequence in context: A166991 A151498 A103370 * A117107 A159609 A128326
Adjacent sequences: A094146 A094147 A094148 * A094150 A094151 A094152
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Alexey Spiridonov (aspirido(AT)princeton.edu), May 04 2004
|
| |
|
|
