Take n points and glue triangles onto them, each triangle joining three of the points, until everything is connected. The result is minimal if no triangle is spare: removing any one disconnects something. A000080 counts these up to relabelling the points, and A048781 adds up their triangles.
Until now the counts were known up to n = 25 (Martin Fuller, 2015, about a day of computer search). A structure theorem turns the problem into a formula, which gives every term up to n = 80 in minutes on a desktop PC. Each such graph is a tree of grey lone triangles and coloured blocks. In a block, some pairs of points are joined by several triangles, so those pairs form a loop-free multigraph with no cut point, and every triangle sticks out one free corner.
Rows up to n = 9 show every graph. Larger rows show random examples. They are built from the structure theorem and can reach every graph, but they are not uniform samples.
Draw the incidence graph: one node per point, one node per triangle, and an edge whenever a point lies on a triangle. A system is connected exactly when this graph is. It is minimal exactly when every triangle node is a cut node, so removing it splits the graph.
That pins down the pieces. Every 2-connected piece of the incidence graph is either a single edge or a multigraph block: a loop-free multigraph on the points with no cut point, whose edges are triangles, and each of those triangles has its third corner outside the block. So a minimal triangle graph is a tree of lone triangles and such blocks, glued at points.
Trees and blocks are what Pólya counting (species theory) handles well. The blocks come from the explicit cycle index of all multigraphs by the classical logarithm and block inversion, substituted directly into one-variable power series. Every term up to n is then a sum over the integer partitions of numbers up to n, computed modulo several 62-bit primes and combined with the Chinese remainder theorem. Marking each triangle with a variable y and differentiating at y = 1 gives A048781 too.
Checks: the formula reproduces all 23 known terms of both sequences. For n ≤ 15 the blocks found in the full lists of graphs agree with the block counts the formula predicts. The extra primes agree on every term.
| n | A000080(n) | A048781(n) | status |
|---|
Method, code and checks: oeis-results/A000080. Small-n lists from Martin Fuller's program on the OEIS entry.