OFFSET
9,2
COMMENTS
This sequence is the third row of table T of A137918.
Let us refer to a partition of n that has exactly x parts as an x-partition of n.
A138387(n-3) counts the graphs corresponding to the 3-partitions of n whose smallest part is 3, so we consider only the 3-partitions of n whose smallest part is 4.
To determine those partitions, we start with k = 4, 5, ..., floor(n/3), and append to each one of these values of k the 2-partitions of n-k whose smallest part is >= k.
For example, if n = 18, we have 4 <= k <= 6. For k = 4, the 3-partitions are 4+(4+10), 4+(5+9), 4+(6+8) and 4+(7+7). To k = 5 correspond 5+(5+8) and 5+(6+7). Finally we have 6+(6+6).
To determine the formula, one must consider that there are partitions having distinct parts, partitions having 2 equal parts and if n mod 3 = 0, there is a unique partition with equal parts. See example.
LINKS
D. E. Knuth, The Art of Computer Programming, Vol. 4, Fascicle 4b, p. 20.
FORMULA
If n <= 11, a(n) = A138387(n-3).
If n > 11, a(n) = A138387(n-3) + nU + sI + sD + sF, where nU = (f(n/3) + 2) * (f(n/3) + 1) * f(n/3)/6, (n mod 3 = 0), 0, (otherwise),
sI = (1/2) * Sum_{4 <= k < n/3}(f(k) + 1) * f(k) * f(n - 2k),
sD = Sum_{4 <= k < (n-2)/3} f(k) * Sum_{k+1 <= i < (n-k)/2} f(i) * f(n-k-i),
sF = (1/2) * Sum_{4 <= k < n/3}f(k) * (f((n-k)/2) + 1) * f((n-k)/2), (even n, k), or (1/2) * Sum_{5 <= k < n/3}f(k) * (f((n-k)/2) + 1) * f((n-k)/2), (odd n, k),
where f(j) is A001429(j).
EXAMPLE
a(18) = 29722, since A138387(15) = 17980; nU = 455. The partitions considered by sI are 4+(4+10) and 5+(5+8). Those partitions correspond to 3306 graphs. To sD correspond 4+(5+9), 4+(6+8) and 5+(6+7). This gives 6859 graphs. To sF correspond 4+(7+7), or 1122 graphs.
Note that f(4)= 2, f(5) = 5, f(6) = 13, f(7) = 33, f(8) = 89, f(9) = 240 and f(10) = 657.
CROSSREFS
KEYWORD
nonn
AUTHOR
Washington Bomfim, Mar 18 2008
STATUS
approved