cp's OEIS Frontend

A210586 Triangle T(n,k) read by rows: T(n,k) is the number of rooted hypertrees on n labeled vertices with k hyperedges, n >= 2, k >= 1.

%I A210586 #31 Feb 03 2025 09:48:07
%S A210586 2,3,9,4,48,64,5,175,750,625,6,540,5400,12960,7776,7,1519,30870,
%T A210586 156065,252105,117649,8,4032,154112,1433600,4587520,5505024,2097152,9,
%U A210586 10287,704214,11160261,62001450,141363306,133923132,43046721,10,25500,3025000,77700000,695100000,2646000000,4620000000,3600000000,1000000000
%N A210586 Triangle T(n,k) read by rows: T(n,k) is the number of rooted hypertrees on n labeled vertices with k hyperedges, n >= 2, k >= 1.
%C A210586 A hypergraph H is a pair (V,E) consisting of a finite set V of vertices and a set E of hyperedges given by subsets of V containing at least two elements. A walk in a hypergraph H connecting vertices v0 and vn is a sequence v0, e1, v1, e2, ... , v(n-1), en, vn, where each vi is in V and each ei is in E and for each ei the set {v(i-1),vi} is contained in ei. If for every pair of vertices v and v0 there is a walk in H starting at v and ending at v0 then H is called connected. A walk is a cycle if it contains at least two edges, all of the ei are distinct and all of the vi are distinct except v0 = vn. A connected hypergraph with no cycles is called a hypertree. A rooted hypertree is a hypertree in which one particular vertex is selected as being the root. For the enumeration of unrooted hypertrees see A210587.
%H A210586 Andrew Howroyd, <a href="/A210586/b210586.txt">Table of n, a(n) for n = 2..1276</a>
%H A210586 Roland Bacher, <a href="https://arxiv.org/abs/1102.2708">On the enumeration of labelled hypertrees and of labelled bipartite trees</a>, arXiv:1102.2708 [math.CO], 2011.
%H A210586 J. McCammond and J. Meier, <a href="http://www.math.ucsb.edu/~mccammon/papers/htpandelltwo.pdf">The hypertree poset and the l^2-Betti numbers of the motion group of the trivial link</a>, Mathematische Annalen 328 (2004), no. 4, 633-652.
%F A210586 T(n,k) = n^k*Stirling2(n-1,k). T(n,k) = n*A210587(n,k).
%F A210586 E.g.f. A(x,t) = t + 2*x*t^2/2! + (3*x + 9*x^2)*t^3/3! + ... satisfies A(x,t) = t*exp(x*(exp(A(x,t)) - 1)).
%F A210586 Dobinski-type formula for the row polynomials: R(n,x) = exp(-n*x)*Sum_{k = 0..inf} n^k*k^(n-1)x^k/k!.
%F A210586 Row sums A035051.
%F A210586 The e.g.f. is essentially the series reversion of t/F(x,t) w.r.t. t, where F(x,t) = exp(x*(exp(t) - 1)) is the e.g.f. of the Stirling numbers of the second kind A048993. - _Peter Bala_, Oct 28 2015
%e A210586 Triangle begins
%e A210586 .n\k.|....1.....2......3.......4.......5.......6
%e A210586 = = = = = = = = = = = = = = = = = = = = = = = = =
%e A210586 ..2..|....2
%e A210586 ..3..|....3.....9
%e A210586 ..4..|....4....48.....64
%e A210586 ..5..|....5...175....750.....625
%e A210586 ..6..|....6...540...5400...12960....7776
%e A210586 ..7..|....7..1519..30870..156065..252105..117649
%e A210586 ...
%e A210586 Example of a hypertree with two hyperedges, one a 2-edge {3,4} and one a 3-edge {1,2,3}.
%e A210586 ........__________........................
%e A210586 ......./..........\.______................
%e A210586 ......|....1...../.\......\...............
%e A210586 ......|.........|.3.|....4.|..............
%e A210586 ......|....2.....\./______/...............
%e A210586 .......\__________/.......................
%e A210586 ..........................................
%e A210586 T(4,2) = 48. The twelve unrooted hypertrees on 4 vertices {1,2,3,4} with 2 hyperedges (one a 2-edge and one a 3-edge) have hyperedges:
%e A210586 {1,2,3} and {3,4}; {1,2,3} and {2,4}; {1,2,3} and {1,4};
%e A210586 {1,2,4} and {1,3}; {1,2,4} and {2,3}; {1,2,4} and {3,4};
%e A210586 {1,3,4} and {1,2}; {1,3,4} and {2,3}; {1,3,4} and {2,4};
%e A210586 {2,3,4} and {1,2}; {2,3,4} and {1,3}; {2,3,4} and {1,4}.
%e A210586 Choosing one of the four vertices as the root gives a total of 4x12 = 48 rooted hypertrees on 4 vertices.
%p A210586 with(combinat):
%p A210586 A210586 := (n, k) -> n^k*stirling2(n-1, k):
%p A210586 for n from 2 to 10 do seq(A210586(n, k), k = 1..n-1) end do;
%p A210586 # _Peter Bala_, Oct 28 2015
%o A210586 (PARI) T(n,k) = {n^k*stirling(n-1,k,2)}
%o A210586 for(n=2, 10, for(k=1, n-1, print1(T(n, k), ", ")); print); \\ _Andrew Howroyd_, Aug 28 2018
%Y A210586 Cf. A035051 (row sums). Cf. A210587, A048993.
%K A210586 nonn,easy,tabl
%O A210586 2,1
%A A210586 _Peter Bala_, Mar 26 2012