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

 

Logo

The OEIS is looking to hire part-time people to help edit core sequences, upload scanned documents, process citations, fix broken links, etc. - Neil Sloane, njasloane@gmail.com

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 May 29 03:40 EDT 2017. Contains 287242 sequences.