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
KEYWORD
nonn
AUTHOR
Alexey Spiridonov (aspirido(AT)princeton.edu), May 04 2004
STATUS
approved