%I #27 Apr 29 2024 09:33:00
%S 0,1,3,19,155,1641,21427,334377,6085683,126745435,2975448641,
%T 77779634571,2241339267037,70604384569005,2414086713172695,
%U 89049201691604881,3525160713653081279,149075374211881719939,6707440248292609651513,319946143503599791200675
%N Number of different forests of unrooted trees, without isolated vertices, on n labeled nodes.
%C 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
%H Alois P. Heinz, <a href="/A105784/b105784.txt">Table of n, a(n) for n = 1..150</a>
%F 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).
%F Inverse binomial transform of A001858. E.g.f.: exp(-x-LambertW(-x) -LambertW(-x)^2/2). - _Vladeta Jovovic_, Apr 22 2005
%F a(n) ~ exp(-exp(-1)+1/2) * n^(n-2). - _Vaclav Kotesovec_, Aug 16 2013
%e 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.
%e From _Gus Wiseman_, Apr 28 2024: (Start)
%e Edge-sets of the a(2) = 1 through a(4) = 19 forests:
%e 12 12,13 12,34
%e 12,23 13,24
%e 13,23 14,23
%e 12,13,14
%e 12,13,24
%e 12,13,34
%e 12,14,23
%e 12,14,34
%e 12,23,24
%e 12,23,34
%e 12,24,34
%e 13,14,23
%e 13,14,24
%e 13,23,24
%e 13,23,34
%e 13,24,34
%e 14,23,24
%e 14,23,34
%e 14,24,34
%e (End)
%p b:= n-> add(add(binomial(m, j) *binomial(n-1, n-m-j)
%p *n^(n-m-j) *(m+j)!/ (-2)^j, j=0..m)/m!, m=0..n):
%p a:= n-> add(b(k) *(-1)^(n-k) *binomial(n, k), k=0..n):
%p seq(a(n), n=1..17); # _Alois P. Heinz_, Sep 10 2008
%t 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_ *)
%Y Cf. A033185, A105599.
%Y The connected case is A000272, rooted A000169.
%Y This is the covering case of A001858, unlabeled A005195.
%Y The unlabeled version is A144958.
%Y For triangles instead of cycles we have A372168, covering case of A213434.
%Y For a unique cycle we have A372195, covering case of A372193.
%Y A002807 counts cycles in a complete graph.
%Y A006125 counts simple graphs, unlabeled A000088.
%Y A006129 counts covering graphs, unlabeled A002494.
%Y A372170 counts simple graphs by triangles, covering A372167.
%Y Cf. A053530, A054548, A137916, A137917, A322661, A367863, A372169, A372171, A372176, A372191.
%K nonn
%O 1,3
%A _Washington Bomfim_, Apr 21 2005