|
Search: id:A137917
|
|
|
| A137917 |
|
Number of distinct unlabeled graphs with n vertices where all components are unicyclic. |
|
+0
3
|
|
| 1, 2, 5, 14, 35, 97, 264, 733, 2034, 5728, 16101, 45595, 129327, 368093, 1049520, 2999415, 8584857, 24612114, 70652441, 203075740, 584339171, 1683151508, 4852736072, 14003298194, 40441136815, 116880901512, 338040071375
(list; graph; listen)
|
|
|
OFFSET
|
3,2
|
|
|
LINKS
|
Wikipedia, Pseudoforest.
|
|
FORMULA
|
Sum over the partitions 3K_3+4K_4+ ... +nK_n of the integer n with parts >= 3 of product_{3=<i<=n}C(A001429(i)+K_i-1, K_i).
|
|
EXAMPLE
|
For n = 6, a(n) = 14 because of the 13 distinct unicycles of 6 vertices, and the disconnected graph formed by two triangles.
Note that A008483(6) = 2, and the two partitions of 6 into parts >= 3 are [ 6 ]
and [ 3 3 ]. The partition [ 6 ] corresponds to the combinations of A001429(6)
objects repeated zero times, one by one, which number is C(A001429(6)+1-1, 1) =
A001429(6) = 13. The partition [ 3, 3 ], corresponds to the combinations of
A001429(3) objects repeated once, which number is C(A001429(3)+2-1, 2) =
C(2, 2) = 1. It is easy to see that if Ki = 0, and i >= 3,
C(A001429(i)+Ki-1, Ki) = 1, so in the product_{3=<i<=n}C(A001429(i)+Ki-1, Ki)
only the values of Ki greater than 0 are considered.
|
|
CROSSREFS
|
Cf. A001429, A008483, A106238, A137918.
Sequence in context: A018015 A080039 A131408 this_sequence A102714 A087223 A005955
Adjacent sequences: A137914 A137915 A137916 this_sequence A137918 A137919 A137920
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Washington G. Bomfim (webonfim(AT)bol.com.br), Feb 24 2008
|
|
|
Search completed in 0.002 seconds
|
