|
|
A137918
|
|
Array read by columns: T(n,m) = number of unlabeled graphs with n vertices and m unicyclic components.
|
|
11
|
|
|
1, 2, 5, 13, 1, 33, 2, 89, 8, 240, 23, 1, 657, 74, 2, 1806, 220, 8, 5026, 674, 27, 1, 13999, 2011, 89, 2, 39260, 6038, 289, 8, 110381, 17980, 938, 27, 1, 311465, 53547, 2985, 94, 2, 880840, 158907, 9456, 309, 8, 2497405, 471225, 29722, 1035, 27, 1, 7093751
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
3,2
|
|
LINKS
|
|
|
FORMULA
|
T(m, n) = sum over the partitions 3K_3 + ... + nK_n of n, whose smallest part is 3, that have exactly m parts of pi{4 <= i <= n}binomial(f(i) + K_i - 1, K_i), where f(i) is A001429(i).
For example, T(3,12) = T(4,15) = 27. The partitions of 12 of the form 3K_3 + ... + nK_n satisfying the restrictions are 4*3, 5+4+3 and 6+3*2. With n = 15 they are 4*3+3, 5+4+3*2 and 6+3*3. The partitions of 12 can be used to count the graphs in both cases, i.e., n = 12 and n = 15.
The partition 4*3 corresponds to binomial(2+3-1, 3), or 4 graphs. The partition 5+4+3 gives binomial(5,1) * binomial(2,1) or 10 graphs. Lastly, 6+3*2 corresponds to 13 graphs. Note that f(3) = 1, f(4) = 2, f(5) = 5 and f(6) = 13.
|
|
EXAMPLE
|
Array begins:
m/n|3.4.5..6..7..8...9..10...11...12....13....14.....15.....16.....17......18
---|-------------------------------------------------------------------------
1..|1.2.5.13.33.89.240.657.1806.5026.13999.39260.110381.311465.880840.2497405
2..|.......1..2..8..23..74..220..674..2011..6038..17980..53547.158907..471225
3..|.................1...2....8...27....89...289....938...2985...9456...29722
4..|...............................1.....2.....8.....27.....94....309....1035
5..|..................................................1......2......8......27
6..|........................................................................1
-----------------------------------------------------------------------------
m/n|.....19.......20.......21........22........23.........24.........25....
---------------------------------------------------------------------------
1..|7093751.20187313.57537552.164235501.469406091.1343268050.3848223585....
2..|1394786..4124929.12185636..35972082.106111713..312835608..921809509....
3..|..92842...288509...892506...2749940...8443504...25845735...78897469....
4..|...3382....11040....35659....114614....365970....1163167....3678680....
5..|.....94......315.....1060......3507.....11570......37853.....123196....
6..|......2........8.......27........94.......315.......1067.......3537....
7..|........................1.........2.........8.........27.........94....
8..|.......................................................1..........2....
9..|.......................................................................
Both the 5th and the 6th rows of table T begin with the same values, 1, 2, 8, 27, 94 and 315.
This happen since the number of graphs with n vertices and m components is equal to the number of graphs with n+3j vertices and m+j components, n >= 3, j >= 1.
So T(5,16) = T(6,19), T(5,17) = T(6,20), T(5,18) = T(6,21) etc.
In the sequence A138386 one can see the first terms of the m-th row of table T as m tends to infinity.
Parts equal to 3 do not change the values taken by the product in the formula since if i = 3, binomial(f(i) + K_i - 1, K_i) = binomial(1 + K_i - 1, Ki) = 1.
Because of that we take i >= 4 in the formula.
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|