3,2

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

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}C(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 in 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 C(2+3-1, 3), or 4 graphs. The partition 5+4+3 gives C(5,1) * C(2,1) or 10 graphs. Last 6+3*2 corresponds to 13 graphs. Note that f(3) = 1, f(4) = 2, f(5) = 5, and f(6) = 13.

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, C(f(i) + K_i - 1, K_i) = C(1 + K_i - 1, Ki) = 1.

Because of that we take i >= 4 in the formula.

Cf. A001429, A137917, A138386.

Sequence in context: A041715 A042241 A042911 this_sequence A114502 A135308 A114492

Adjacent sequences: A137915 A137916 A137917 this_sequence A137919 A137920 A137921

nonn,tabf

Washington G. Bomfim (webonfim(AT)bol.com.br), Mar 18 2008

Edited by njas, Mar 21 2008