login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 3
2, 3, 9, 4, 48, 64, 5, 175, 750, 625, 6, 540, 5400, 12960, 7776, 7, 1519, 30870, 156065, 252105, 117649, 8, 4032, 154112, 1433600, 4587520, 5505024, 2097152, 9, 10287, 704214, 11160261, 62001450, 141363306, 133923132, 43046721, 10, 25500, 3025000, 77700000, 695100000, 2646000000, 4620000000, 3600000000, 1000000000 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

2,1

COMMENTS

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.

LINKS

Table of n, a(n) for n=2..46.

R. Bacher, On the enumeration of labelled hypertrees and of labelled bipartite trees, arXiv:1102.2708 [math.CO], 2011.

J. McCammond and J. Meier, The hypertree poset and the l^2-Betti numbers of the motion group of the trivial link, Mathematische Annalen 328 (2004), no. 4, 633-652.

FORMULA

T(n,k) = n^k*Stirling2(n-1,k). T(n,k) = n*A210587(n,k).

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)).

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!.

Row sums A035051.

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

EXAMPLE

Triangle begins

.n\k.|....1.....2......3.......4.......5.......6

= = = = = = = = = = = = = = = = = = = = = = = = =

..2..|....2

..3..|....3.....9

..4..|....4....48.....64

..5..|....5...175....750.....625

..6..|....6...540...5400...12960....7776

..7..|....7..1519..30870..156065..252105..117649

...

Example of a hypertree with two hyperedges, one a 2-edge {3,4) and one a 3-edge{1,2,3}.

........__________........................

......./..........\.______................

......|....1...../.\......\...............

......|.........|.3.|....4.|..............

......|....2.....\./______/...............

.......\__________/.......................

..........................................

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:

{1,2,3} and {3,4); {1,2,3} and {2,4); {1,2,3} and {1,4);

{1,2,4} and {1,3); {1,2,4} and {2,3); {1,2,4} and {3,4);

{1,3,4} and {1,2); {1,3,4} and {2,3); {1,3,4} and {2,4);

{2,3,4} and {1,2); {2,3,4} and {1,3); {2,3,4} and {1,4).

Choosing one of the four vertices as the root gives a total of 4x12 = 48 rooted hypertrees on 4 vertices.

MAPLE

with(combinat):

A210586 := (n, k) -> n^k*stirling2(n-1, k):

for n from 2 to 10 do seq(A210586(n, k), k = 1..n-1) end do;

# Peter Bala, Oct 28 2015

CROSSREFS

  A035051 (row sums). Cf. A210587, A048993.

Sequence in context: A249824 A227912 A229212 * A202017 A127198 A065631

Adjacent sequences:  A210583 A210584 A210585 * A210587 A210588 A210589

KEYWORD

nonn,easy,tabl

AUTHOR

Peter Bala, Mar 26 2012

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified November 24 00:27 EST 2017. Contains 295164 sequences.