login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


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

Table of n, a(n) for n=0..24.

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.

License Agreements, Terms of Use, Privacy Policy. .

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