

A055779


Number of fat trees on n labeled vertices.


2



1, 2, 10, 89, 1156, 19897, 428002, 11067457, 334667368, 11593751921, 452892057454, 19699549177585, 944416040000044, 49480473036710185, 2812998429218735986, 172475808692526176513, 11345688093224067380176
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

A fat tree on vertex set V is a partition of V together with edges (between vertices, not parts) that link the parts of the partition in a treelike pattern: that is, when the parts are collapsed to points, the edges are a (free) tree. A fat tree is in a (multi)graph G when the edges are edges of G. The fat forests in a graph form a geometric lattice.
If a(n) is the number of fat trees when each edge is replaced by M distinguishable copies of itself, then a(1) = 1, a(2) = M + 1, a(3) = 3 M^2 + 6 M + 1, a(4) = 16 M^3 + 48 M^2 + 24 M + 1, a(5) = 125 M^4 + 500 M^3 + 450 M^2 + 80 M + 1, a(6) = 1296 M^5 + 6480 M^4 + 8640 M^3 + 3240 M^2 + 240 M + 1.


REFERENCES

Thomas Zaslavsky, "Perpendicular dissections of space". Discrete Comput. Geom., 27 (2002), 303351. MR 2003i:52026. Zbl. 1001.52011.


LINKS

T. D. Noe, Table of n, a(n) for n=1..100
Vaclav Kotesovec, Asymptotic formula for number of fat trees on n labeled vertices, Aug 25 2012, in Czech, main results in English.


FORMULA

a(n) = Sum_{k=1..n} binomial(n, k)*k^(nk)*n^(k2).  Vladeta Jovovic, Jun 16 2006
a(n) = n!/n^2 sum_{mu a partition of n} product_j n^{mu_j}/(mu_j! (j1)!^{mu_j}), where mu_j is the number of parts of size j in the partition mu.  Vladeta Jovovic, Jun 15 2006
limit n>infinity (a(n)^(1/n))/n = (1p)^(p1)*p^(12*p) ~ 1.6554879129915343..., where p ~ 0.6924583254616546... is the root of the equation exp(11/p)=(1p)/p^2. [From Vaclav Kotesovec, Aug 25 2012]


EXAMPLE

For n=3, there is one fat tree with a single node, three with three nodes (choose which vertex to have in the middle) and six with two nodes (3 choices for which vertex to have by itself and 2 choices for which of the others to join it to).


MATHEMATICA

Table[Sum[Binomial[n, k]k^(nk) n^(k2), {k, n}], {n, 20}] (* Harvey P. Dale, Aug 24 2016 *)


PROG

(PARI) A055779(n) = sum(k=1, n, binomial(n, k)*k^(nk)*n^(k2)).  Franklin T. AdamsWatters, Jun 16 2006


CROSSREFS

Sequence in context: A270923 A096658 A186184 * A198434 A277403 A179423
Adjacent sequences: A055776 A055777 A055778 * A055780 A055781 A055782


KEYWORD

nonn,nice,easy


AUTHOR

Thomas Zaslavsky, Jul 12 2000


EXTENSIONS

Edited with more terms by Franklin T. AdamsWatters, Jun 13 2006
More terms from Vladeta Jovovic and Franklin T. AdamsWatters, Jun 15 2006


STATUS

approved



