A368178 Number of ordered trees with n+1 leaves, no node of outdegree 1, and having as many leaves marked as the number of nodes of outdegree greater than 1.

1, 2, 9, 54, 375, 2848, 22981, 193742, 1688427, 15101778, 137930199, 1281629088, 12081441411, 115288530516, 1111783691037, 10819906562622, 106147110898419, 1048748721598078, 10427413491373843, 104265186535823798, 1047894080773661481

Offset: 0

Author

Juan B. Gil, Jan 03 2024

Keywords

• nonn

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

Examples

			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.
		

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.

Crossrefs

Cf. A001003, A001622.

Programs

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

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

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