

A094149


The 2kth 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 lefttoright (but may return).


0



1, 3, 12, 57, 303, 1747, 10727, 69331, 467963, 3280353, 23785699, 177877932, 1368977132
(list;
graph;
refs;
listen;
history;
text;
internal format)



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 kth 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: A243521 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



