cp's OEIS Frontend

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

%I A137918 #16 Dec 24 2015 02:42:08
%S A137918 1,2,5,13,1,33,2,89,8,240,23,1,657,74,2,1806,220,8,5026,674,27,1,
%T A137918 13999,2011,89,2,39260,6038,289,8,110381,17980,938,27,1,311465,53547,
%U A137918 2985,94,2,880840,158907,9456,309,8,2497405,471225,29722,1035,27,1,7093751
%N A137918 Array read by columns: T(n,m) = number of unlabeled graphs with n vertices and m unicyclic components.
%H A137918 Alois P. Heinz, <a href="/A137918/b137918.txt">Table of n, a(n) for n = 3..86</a>
%H A137918 Wikimedia commons, <a href="http://commons.wikimedia.org/wiki/Image:Anima1122.gif">The 27 graphs with 12 points and 3 components, plus the 27 graphs with 15 points and 4 components</a>.
%F A137918 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).
%F A137918 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.
%F A137918 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.
%e A137918 Array begins:
%e A137918 m/n|3.4.5..6..7..8...9..10...11...12....13....14.....15.....16.....17......18
%e A137918 ---|-------------------------------------------------------------------------
%e A137918 1..|1.2.5.13.33.89.240.657.1806.5026.13999.39260.110381.311465.880840.2497405
%e A137918 2..|.......1..2..8..23..74..220..674..2011..6038..17980..53547.158907..471225
%e A137918 3..|.................1...2....8...27....89...289....938...2985...9456...29722
%e A137918 4..|...............................1.....2.....8.....27.....94....309....1035
%e A137918 5..|..................................................1......2......8......27
%e A137918 6..|........................................................................1
%e A137918 -----------------------------------------------------------------------------
%e A137918 m/n|.....19.......20.......21........22........23.........24.........25....
%e A137918 ---------------------------------------------------------------------------
%e A137918 1..|7093751.20187313.57537552.164235501.469406091.1343268050.3848223585....
%e A137918 2..|1394786..4124929.12185636..35972082.106111713..312835608..921809509....
%e A137918 3..|..92842...288509...892506...2749940...8443504...25845735...78897469....
%e A137918 4..|...3382....11040....35659....114614....365970....1163167....3678680....
%e A137918 5..|.....94......315.....1060......3507.....11570......37853.....123196....
%e A137918 6..|......2........8.......27........94.......315.......1067.......3537....
%e A137918 7..|........................1.........2.........8.........27.........94....
%e A137918 8..|.......................................................1..........2....
%e A137918 9..|.......................................................................
%e A137918 The first row is A001429. Sums of columns form A137917.
%e A137918 Both the 5th and the 6th rows of table T begin with the same values, 1, 2, 8, 27, 94 and 315.
%e A137918 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.
%e A137918 So T(5,16) = T(6,19), T(5,17) = T(6,20), T(5,18) = T(6,21) etc.
%e A137918 In the sequence A138386 one can see the first terms of the m-th row of table T as m tends to infinity.
%e A137918 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.
%e A137918 Because of that we take i >= 4 in the formula.
%Y A137918 Cf. A001429, A137917, A138386.
%K A137918 nonn,tabf
%O A137918 3,2
%A A137918 _Washington Bomfim_, Mar 18 2008
%E A137918 Edited by _N. J. A. Sloane_, Mar 21 2008
%E A137918 More terms from _Alois P. Heinz_, Jun 25 2014