|
Search: id:A129271
|
|
|
| A129271 |
|
Number of labeled n-node connected graphs with at most one cycle. |
|
+0
4
|
|
| 1, 1, 1, 4, 31, 347, 4956, 85102, 1698712, 38562309, 980107840, 27559801736, 849285938304, 28459975589311, 1030366840792576, 40079074477640850, 1666985134587145216
(list; graph; listen)
|
|
|
OFFSET
|
0,4
|
|
|
COMMENT
|
The majority of those graphs of order 4 are trees since we have 16 trees and only 9 unicycles. See example.
|
|
REFERENCES
|
J. Riordan, An Introduction to Combinatorial Analysis, Dover, 2002, p. 2.
|
|
LINKS
|
Wikipedia, PseudoForest.
|
|
FORMULA
|
a(0) = 1, for n >=1, a(n) = A000272(n) + A057500(n) = n^{n-2} + (n-1)(n-2)/2Sum_{r=1..n-2}( (n-3)!/(n-2-r)! )n^(n-2-r)
|
|
EXAMPLE
|
a(4) = 16 + 3*3 = 31.
|
|
CROSSREFS
|
Cf. A129137, A005703, A000272, A057500.
Sequence in context: A122400 A107725 A145160 this_sequence A136728 A102757 A145561
Adjacent sequences: A129268 A129269 A129270 this_sequence A129272 A129273 A129274
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
Washington Bomfim (webonfim(AT)bol.com.br), May 10 2008
|
|
|
Search completed in 0.002 seconds
|
