A137918 - OEIS

%I #16 Dec 24 2015 02:42:08

%S 1,2,5,13,1,33,2,89,8,240,23,1,657,74,2,1806,220,8,5026,674,27,1,

%T 13999,2011,89,2,39260,6038,289,8,110381,17980,938,27,1,311465,53547,

%U 2985,94,2,880840,158907,9456,309,8,2497405,471225,29722,1035,27,1,7093751

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

%H Alois P. Heinz, <a href="/A137918/b137918.txt">Table of n, a(n) for n = 3..86</a>

%H 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 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 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 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 Array begins:

%e m/n|3.4.5..6..7..8...9..10...11...12....13....14.....15.....16.....17......18

%e ---|-------------------------------------------------------------------------

%e 1..|1.2.5.13.33.89.240.657.1806.5026.13999.39260.110381.311465.880840.2497405

%e 2..|.......1..2..8..23..74..220..674..2011..6038..17980..53547.158907..471225

%e 3..|.................1...2....8...27....89...289....938...2985...9456...29722

%e 4..|...............................1.....2.....8.....27.....94....309....1035

%e 5..|..................................................1......2......8......27

%e 6..|........................................................................1

%e -----------------------------------------------------------------------------

%e m/n|.....19.......20.......21........22........23.........24.........25....

%e ---------------------------------------------------------------------------

%e 1..|7093751.20187313.57537552.164235501.469406091.1343268050.3848223585....

%e 2..|1394786..4124929.12185636..35972082.106111713..312835608..921809509....

%e 3..|..92842...288509...892506...2749940...8443504...25845735...78897469....

%e 4..|...3382....11040....35659....114614....365970....1163167....3678680....

%e 5..|.....94......315.....1060......3507.....11570......37853.....123196....

%e 6..|......2........8.......27........94.......315.......1067.......3537....

%e 7..|........................1.........2.........8.........27.........94....

%e 8..|.......................................................1..........2....

%e 9..|.......................................................................

%e The first row is A001429. Sums of columns form A137917.

%e Both the 5th and the 6th rows of table T begin with the same values, 1, 2, 8, 27, 94 and 315.

%e 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 So T(5,16) = T(6,19), T(5,17) = T(6,20), T(5,18) = T(6,21) etc.

%e In the sequence A138386 one can see the first terms of the m-th row of table T as m tends to infinity.

%e 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 Because of that we take i >= 4 in the formula.

%Y Cf. A001429, A137917, A138386.

%K nonn,tabf

%O 3,2

%A _Washington Bomfim_, Mar 18 2008

%E Edited by _N. J. A. Sloane_, Mar 21 2008

%E More terms from _Alois P. Heinz_, Jun 25 2014