

A138386


The initial values of the mth row of table T of A137918 as m tends to infinity.


1



1, 2, 8, 27, 94, 315, 1067, 3545, 11767, 38747, 127061, 414551, 1347442, 4362616, 14078612, 45290929, 145291501, 464864831, 1483759703, 4725204487, 15016441266, 47627848083, 150784504858, 476543143817, 1503631824859
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

It is clear that the first term of the mth row of table T, a(0) = T(m, 3m) = T(1, 3) = 1.
Let us call an xpartition of n a partition of n that has exactly x parts >= 3.
Below we show that for j >= 1, a(j) = T(m, 3m + j) = T(j, 4j).
An mpartition of n = 3m + j has at least mj parts 3. Suppose that p is an mpartition of n with mj1 parts 3. The sum of the parts of p is at least n+1 since 3(mj1) + 4(m  (mj1)) = 3(mj1) + 4m 4(mj1) = 4m  (mj1) = 4mm+j+1 = (3m + j) + 1.
Because any mpartition of n = 3m + j has at least mj parts 3, we obtain all the mpartitions of 3m + j if we append mj parts 3 to each one of the jpartitions of 4j. Note that n  3(mj) = 4j and m  (mj) = j.
To complete we note that C(f(3) + K_3  1, K_3) = C(K_3, K_3) = 1 and the values taken by the product pi{3 <= i <= n}C(f(i) + K_i  1, K_i) do not change when we add mj to K_3. In fact pi{3 <= i <= n}C(f(i) + K_i  1, K_i) = pi{4 <= i <= n}C(f(i) + K_i  1, K_i).
Using results found in the Knuth reference on pp. 9, ..., it is not difficult to show that the number of jpartitions of 4j is equal to p(j), (where p(n) is the usual partition function).
The largest part that appears in those partitions is j+3, because j+4+3(j1) = 4j+1. So the first 27 values of this sequence are showed. Note that f(k) is known for k <= 29 and we work with 1 <= j <= 26.
With small values of 3m+j, the identity T(m, 3m+j) = T(j, 4j) comes closer to permit us to enumerate all the graphs with M components and N vertices, ie., N >= 3, M >= 1. For example we determine T(M, 100) for M >= 25, T(M, 50) for M >= 8, T(M, 38) for M >= 4, T(M, 35) for M >= 3 and T(M, 32) for M >= 2. All graphs are determined if N <= 29.
It can be shown that the formula computes T(i, 3i+j), i,j >= 1, for the nine values of i: floor((3i+j)/3)  8 <= i <= floor((3i+j)/3).


LINKS

Table of n, a(n) for n=0..24.
D. E. Knuth, The Art of Computer Programming, Vol. 4, PreFascicle 3b, see p. 9.


FORMULA

a(0) = 1; for j >= 1, a(j) = Sum over the partitions 3K_3 + ... + nK_n of n = 4j with exactly j parts of pi{4 <= i <= n}C(f(i) + K_i  1, K_i), where f(i) is A001429(i).
Euler transform of 2, 5, 13, 33, ... (A001429). [From Vladeta Jovovic, Sep 17 2008]


EXAMPLE

Choosing j = 5 we use p(5) or 7 partitions. The largest part appearing in those partitions is 8, so we need the first 6 values of A001429, given by
...i..3.4..5...6...7...8
+
f(i)..1.2..5..13..33..89
Using the program GAP, the partitions produced by the command "RestrictedPartitions(20, [3..8], 5);" are:
[ [ 4, 4, 4, 4, 4 ], [ 5, 4, 4, 4, 3 ], [ 5, 5, 4, 3, 3 ], [ 6, 4, 4, 3, 3 ], [ 6, 5, 3, 3, 3 ], [ 7, 4, 3, 3, 3 ], [ 8, 3, 3, 3, 3 ] ]
Eliminating parts 3 from those partitions, below we give them in the form 4K_4 +...+ nK_n followed by the corresponding number of graphs:
4*5 > C(2+51, 5) = 6
5 + 4*3 > 5C(2+31, 3) = 20
5*2 + 4 > 2C(5+21, 2) = 30
6 + 4*2 > 13C(2+21, 2) = 39
6 + 5 > 13 * 5 = 65
7 + 4 > 33 * 2 = 66
8 > 89
So a(5) = 6 + 20 + 30 + 39 + 65 + 66 + 89 = 315.
T(333332, 10^6+1) = a(5) = 315. Note that j = 5 and m = 333332 gives 3m+j = 10^6+1.


CROSSREFS

Cf. A137918, A001429.
Sequence in context: A295135 A076884 A138388 * A096647 A054109 A305256
Adjacent sequences: A138383 A138384 A138385 * A138387 A138388 A138389


KEYWORD

nonn


AUTHOR

Washington Bomfim, Mar 18 2008


STATUS

approved



