OFFSET
0,2
COMMENTS
It is clear that the first term of the m-th row of table T, a(0) = T(m, 3m) = T(1, 3) = 1.
Let us call an x-partition 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 m-partition of n = 3m + j has at least m-j parts 3. Suppose that p is an m-partition of n with m-j-1 parts 3. The sum of the parts of p is at least n+1 since 3(m-j-1) + 4(m - (m-j-1)) = 3(m-j-1) + 4m -4(m-j-1) = 4m - (m-j-1) = 4m-m+j+1 = (3m + j) + 1.
Because any m-partition of n = 3m + j has at least m-j parts 3, we obtain all the m-partitions of 3m + j if we append m-j parts 3 to each one of the j-partitions of 4j. Note that n - 3(m-j) = 4j and m - (m-j) = 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 m-j 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 j-partitions 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(j-1) = 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, i.e., 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
D. E. Knuth, The Art of Computer Programming, Vol. 4, Pre-Fascicle 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). - 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+5-1, 5) = 6
5 + 4*3 -> 5C(2+3-1, 3) = 20
5*2 + 4 -> 2C(5+2-1, 2) = 30
6 + 4*2 -> 13C(2+2-1, 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
KEYWORD
nonn
AUTHOR
Washington Bomfim, Mar 18 2008
STATUS
approved