|
Search: id:A134964
|
|
|
| A134964 |
|
Number of different unlabeled n-node graphs with at most one cycle in each connected component. |
|
+0
4
|
|
| 1, 1, 2, 4, 9, 19, 46, 108, 273, 696, 1836, 4896, 13323, 36541, 101323, 282693, 793697, 2237982, 6335978, 17992622, 51235887, 146228734, 418181860, 1197972026, 3437159492, 9875198568, 28407202891, 81807809714, 235831978115
(list; graph; listen)
|
|
|
OFFSET
|
0,3
|
|
|
LINKS
|
Wikipedia, Pseudoforest.
|
|
FORMULA
|
a(0) = 1. For n>=1 a(n) = Sum of prod_{j=1}^n\C(A005703(j)+c_j-1, c_j) over all the partitions of n, c_1+2c_2+...+nc_n; c_1,c_2,...,c_n >= 0.
|
|
EXAMPLE
|
E.g. a(5)=19 because the 7 partitions of 5 in the form c_1 + 2c_2 + ... + nc_n are 1*5, 2*1 + 1*3, 2*2 + 1*1, 3*1 + 1*2, 3*1 + 2*1, 4*1 + 1*1, and 5*1. Below we see those partitions followed by the corresponding number of graphs. Note the table with the values of A005703(j) for 1<=j<=5. Note also that if c_j = 0,
C(A005703(j)+c_j-1, c_j) = 1.
j|1|2|3|4|5|
----+-+-+-+-+-+
a(j)|1|1|2|4|8|
1*5 -> C(1+5-1, 5) = 1,
2*1 + 1*3 -> C(1+1-1, 1)C(1+3-1, 3) = 1*1 = 1,
2*2 + 1*1 -> C(1+2-1, 2)C(1+1-1, 1) = 1*1 = 1,
3*1 + 1*2 -> C(2+1-1, 1)C(1+2-1, 2) = 2*1 = 2,
3*1 + 2*1 -> C(2+1-1, 1)C(1+1-1, 1) = 2*1 = 2,
4*1 + 1*1 -> C(4+1-1, 1)C(1+1-1, 1) = 4*1 = 4,
5*1 -> C(8+1-1, 1) = 8.
Total 19.
|
|
CROSSREFS
|
Cf. A005703, A137917.
Adjacent sequences: A134961 A134962 A134963 this_sequence A134965 A134966 A134967
Sequence in context: A036613 A036614 A036718 this_sequence A052328 A133228 A036717
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Washington Bomfim (webonfim(AT)bol.com.br), May 14 2008
|
|
|
Search completed in 0.002 seconds
|
