The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A138386 The initial values of the m-th 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 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, 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 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). [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+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 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified May 8 11:51 EDT 2021. Contains 343666 sequences. (Running on oeis4.)