login
A362167
a(n) = the hypergraph Catalan number C_2(n).
11
1, 1, 6, 57, 678, 9270, 139968, 2285073, 39871926, 739129374, 14521778820, 302421450474, 6687874784484, 157491909678168, 3961138908376692, 106663881061254465, 3078671632202791782, 95213375569840078422, 3149291101933230285924, 111073721303120881912686
OFFSET
0,3
COMMENTS
Let m >= 1. The sequence of hypergraph Catalan numbers {C_m(n): n >= 0} is defined in terms of counting walks on trees, weighted by the orders of their automorphism groups. When m = 1 we get the sequence of Catalan numbers A000108. The present sequence is the case m = 2.
Let T(n) be the set of unlabeled trees on n vertices (see A000055). Let T be a tree in T(n+1), and let v be a vertex of T. Then an a(m,T)-tour beginning at v is a walk that begins and ends at v and traverses each edge of T exactly 2*m times. We denote by a(m,T)(v) the number of a(m,T)-tours beginning at v.
The hypergraph Catalan numbers C_m(n) are defined by C_m(n) = Sum_{trees T in T(n+1)} Sum_{vertices v in T} a(m,T)(v)/|Aut(T)|, where Aut(T) denotes the automorphism group of the tree T.
Gunnells gives several combinatorial interpretations of the hypergraph Catalan numbers, a method to compute their generating functions to arbitrary precision and some conjectural asymptotics.
LINKS
Paul E. Gunnells, Generalized Catalan numbers from hypergraphs, arXiv:2102.05121 [math.CO], 2021.
FORMULA
a(n) ~ e^(3/2) * 2^(n+1) * n!/sqrt(Pi*n) (conjectural).
PROG
(PARI) Vec(HypCatColGf(2, 20)) \\ HypCatColGf defined in A369288. - Andrew Howroyd, Feb 06 2024
CROSSREFS
KEYWORD
nonn,walk
AUTHOR
Peter Bala, Apr 10 2023
EXTENSIONS
a(11) onwards from Andrew Howroyd, Jan 31 2024
STATUS
approved