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

%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