OFFSET
0,2
COMMENTS
If T(n, k) denotes the number of ordered trees with n + 1 leaves, no node of outdegree 1, and k nodes of outdegree greater than 1, where k of the leaves are marked, then a(n) = Sum_{k=1..n} T(n, k).
LINKS
Juan B. Gil, Emma G. Hoover, and Jessica A. Shearer, Bijections between colored compositions, Dyck paths, and polygon partitions, arXiv:2403.04575 [math.CO], 2024. See p. 8.
FORMULA
a(n) = Sum_{k=1..n} binomial(n+k, k) * binomial(n, k-1) * binomial(n, k)/n for n > 0.
a(n) = (n + 1) * hypergeom([1 - n, -n, n + 2], [2, 2], 1). - Peter Luschny, Jan 03 2024
a(n) ~ phi^(5*n + 7/2) / (2*Pi*5^(1/4)*n^2), where phi = A001622 is the golden ratio. - Vaclav Kotesovec, Jan 04 2024
EXAMPLE
For n = 2 there are 9 such marked trees: There is one tree [ [][][] ] with only one node of outdegree > 1 (the root). This tree leads to 3 marked trees. The tree [ [] [[][]] ] has 2 nodes of outdegree > 1, so it gives binomial(3,2) = 3 marked trees. Similarly, the tree [ [[][]] [] ] gives 3 more marked trees for a total of 9.
MATHEMATICA
Join[{1}, Table[Sum[Binomial[n + k, k]*Binomial[n, k - 1]*Binomial[n, k]/n, {k, 1, n}], {n, 1, 25}]] (* Vaclav Kotesovec, Jan 04 2024 *)
PROG
(PARI) a(n) = if(n==0, 1, sum(k=1, n, binomial(n+k, k)*binomial(n, k-1)* binomial(n, k)/n)) \\ Andrew Howroyd, Jan 03 2024
(SageMath)
def a(n): return (n + 1) * hypergeometric([1 - n, -n, n + 2], [2, 2], 1)
print([simplify(a(n)) for n in range(12)]) # Peter Luschny, Jan 03 2024
CROSSREFS
KEYWORD
nonn
AUTHOR
Juan B. Gil, Jan 03 2024
STATUS
approved