A137918 Array read by columns: T(n,m) = number of unlabeled graphs with n vertices and m unicyclic components.

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

Offset

3,2

Links

Alois P. Heinz, Table of n, a(n) for n = 3..86

Wikimedia commons, The 27 graphs with 12 points and 3 components, plus the 27 graphs with 15 points and 4 components.

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..|.......................................................................
The first row is A001429. Sums of columns form A137917.
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

Cf. A001429, A137917, A138386.

Sequence in context: A041715 A042241 A042911 * A114502 A135308 A114492

Adjacent sequences: A137915 A137916 A137917 * A137919 A137920 A137921

Keyword

nonn,tabf

Author

Washington Bomfim, Mar 18 2008

Extensions

Edited by N. J. A. Sloane, Mar 21 2008

More terms from Alois P. Heinz, Jun 25 2014

Status

approved