login
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.
0

%I #49 Mar 12 2024 09:53:12

%S 1,2,9,54,375,2848,22981,193742,1688427,15101778,137930199,1281629088,

%T 12081441411,115288530516,1111783691037,10819906562622,

%U 106147110898419,1048748721598078,10427413491373843,104265186535823798,1047894080773661481

%N 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.

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

%H Juan B. Gil, Emma G. Hoover, and Jessica A. Shearer, <a href="https://arxiv.org/abs/2403.04575">Bijections between colored compositions, Dyck paths, and polygon partitions</a>, arXiv:2403.04575 [math.CO], 2024. See p. 8.

%F a(n) = Sum_{k=1..n} binomial(n+k, k) * binomial(n, k-1) * binomial(n, k)/n for n > 0.

%F a(n) = (n + 1) * hypergeom([1 - n, -n, n + 2], [2, 2], 1). - _Peter Luschny_, Jan 03 2024

%F 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

%e 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.

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

%o (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

%o (SageMath)

%o def a(n): return (n + 1) * hypergeometric([1 - n, -n, n + 2], [2, 2], 1)

%o print([simplify(a(n)) for n in range(12)]) # _Peter Luschny_, Jan 03 2024

%Y Cf. A001003, A001622.

%K nonn

%O 0,2

%A _Juan B. Gil_, Jan 03 2024