cp's OEIS Frontend

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

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