A138386 - OEIS

%I #14 Aug 27 2022 04:09:26

%S 1,2,8,27,94,315,1067,3545,11767,38747,127061,414551,1347442,4362616,

%T 14078612,45290929,145291501,464864831,1483759703,4725204487,

%U 15016441266,47627848083,150784504858,476543143817,1503631824859

%N The initial values of the m-th row of table T of A137918 as m tends to infinity.

%C It is clear that the first term of the m-th row of table T, a(0) = T(m, 3m) = T(1, 3) = 1.

%C Let us call an x-partition of n a partition of n that has exactly x parts >= 3.

%C Below we show that for j >= 1, a(j) = T(m, 3m + j) = T(j, 4j).

%C 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.

%C 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.

%C 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).

%C 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).

%C 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.

%C 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.

%C 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).

%H D. E. Knuth, <a href="http://www-cs-faculty.stanford.edu/~knuth/fasc3b.ps.gz">The Art of Computer Programming</a>, Vol. 4, Pre-Fascicle 3b, see p. 9.

%F 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).

%F Euler transform of 2, 5, 13, 33, ... (A001429). - _Vladeta Jovovic_, Sep 17 2008

%e 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

%e ...i..|3.4..5...6...7...8

%e ------+------------------

%e f(i)..|1.2..5..13..33..89

%e Using the program GAP, the partitions produced by the command "RestrictedPartitions(20, [3..8], 5);" are:

%e [ [ 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 ] ]

%e Eliminating parts 3 from those partitions, below we give them in the form 4K_4 +...+ nK_n followed by the corresponding number of graphs:

%e 4*5 -> C(2+5-1, 5) = 6

%e 5 + 4*3 -> 5C(2+3-1, 3) = 20

%e 5*2 + 4 -> 2C(5+2-1, 2) = 30

%e 6 + 4*2 -> 13C(2+2-1, 2) = 39

%e 6 + 5 -> 13 * 5 = 65

%e 7 + 4 -> 33 * 2 = 66

%e 8 -> 89

%e So a(5) = 6 + 20 + 30 + 39 + 65 + 66 + 89 = 315.

%e T(333332, 10^6+1) = a(5) = 315. Note that j = 5 and m = 333332 gives 3m+j = 10^6+1.

%Y Cf. A137918, A001429.

%K nonn

%O 0,2

%A _Washington Bomfim_, Mar 18 2008