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).

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.

Links

Table of n, a(n) for n=1..13.

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: A369484 A151498 A103370 * A291695 A117107 A159609

Adjacent sequences: A094146 A094147 A094148 * A094150 A094151 A094152

Keyword

nonn

Author

Alexey Spiridonov (aspirido(AT)princeton.edu), May 04 2004

Status

approved