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
Examples
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.
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.
Extensions
Edited by N. J. A. Sloane, Mar 21 2008
More terms from Alois P. Heinz, Jun 25 2014