A105784 Number of different forests of unrooted trees, without isolated vertices, on n labeled nodes.

0, 1, 3, 19, 155, 1641, 21427, 334377, 6085683, 126745435, 2975448641, 77779634571, 2241339267037, 70604384569005, 2414086713172695, 89049201691604881, 3525160713653081279, 149075374211881719939, 6707440248292609651513, 319946143503599791200675

Offset

1,3

Comments

Number of labeled acyclic graphs covering n vertices. The unlabeled version is A144958. This is the covering case A001858. The connected case is A000272. - Gus Wiseman, Apr 28 2024

Links

Alois P. Heinz, Table of n, a(n) for n = 1..150

Formula

a(n)= sum N/D over all the partitions of n: 1K1 + 2K2 + ... + nKn, with smallest part greater than 1, where N = n!*Product_{i=1..n}i^((i-2)Ki) and D = Product_{i=1..n}(Ki!(i!)^Ki).

Inverse binomial transform of A001858. E.g.f.: exp(-x-LambertW(-x) -LambertW(-x)^2/2). - Vladeta Jovovic, Apr 22 2005

a(n) ~ exp(-exp(-1)+1/2) * n^(n-2). - Vaclav Kotesovec, Aug 16 2013

Example

a(4) = 19 because there are 19 different such forests on 4 labeled nodes: 4^2 are trees, 3 have two trees and none can have more than two trees.
From Gus Wiseman, Apr 28 2024: (Start)
Edge-sets of the a(2) = 1 through a(4) = 19 forests:
    12    12,13    12,34
          12,23    13,24
          13,23    14,23
                   12,13,14
                   12,13,24
                   12,13,34
                   12,14,23
                   12,14,34
                   12,23,24
                   12,23,34
                   12,24,34
                   13,14,23
                   13,14,24
                   13,23,24
                   13,23,34
                   13,24,34
                   14,23,24
                   14,23,34
                   14,24,34
(End)

Maple

b:= n-> add(add(binomial(m, j) *binomial(n-1, n-m-j)
        *n^(n-m-j) *(m+j)!/ (-2)^j, j=0..m)/m!, m=0..n):
a:= n-> add(b(k) *(-1)^(n-k) *binomial(n, k), k=0..n):
seq(a(n), n=1..17);  # Alois P. Heinz, Sep 10 2008

Mathematica

Unprotect[Power]; 0^0 = 1; b[n_] := Sum[Sum[Binomial[m, j]*Binomial[n-1, n -m-j]*n^(n-m-j)*(m+j)!/(-2)^j, {j, 0, m}]/m!, {m, 0, n}]; a[n_] := Sum[ b[k]*(-1)^(n-k)*Binomial[n, k], {k, 0, n}]; Table[a[n], {n, 1, 17}] (* Jean-François Alcover, Jan 08 2016, after Alois P. Heinz *)

Crossrefs

Cf. A033185, A105599.

The connected case is A000272, rooted A000169.

This is the covering case of A001858, unlabeled A005195.

The unlabeled version is A144958.

For triangles instead of cycles we have A372168, covering case of A213434.

For a unique cycle we have A372195, covering case of A372193.

A002807 counts cycles in a complete graph.

A006125 counts simple graphs, unlabeled A000088.

A006129 counts covering graphs, unlabeled A002494.

A372170 counts simple graphs by triangles, covering A372167.

Cf. A053530, A054548, A137916, A137917, A322661, A367863, A372169, A372171, A372176, A372191.

Sequence in context: A323668 A235134 A235322 * A077046 A232607 A307697

Adjacent sequences: A105781 A105782 A105783 * A105785 A105786 A105787

Keyword

nonn

Author

Washington Bomfim, Apr 21 2005

Status

approved