cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-1 of 1 results.

A138388 Numbers of unlabeled graphs with n vertices and 3 unicyclic components.

Original entry on oeis.org

1, 2, 8, 27, 89, 289, 938, 2985, 9456, 29722, 92842, 288509, 892506, 2749940, 8443504, 25845735, 78897469, 240259510, 730040882, 2213910727, 6701939407, 20255424836, 61128717826, 184233427305, 554574518396, 1667491889239
Offset: 9

Views

Author

Washington Bomfim, Mar 18 2008

Keywords

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.

Examples

			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.

Links

Crossrefs

Cf. A001429, A137918.

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).
Showing 1-1 of 1 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.