|
| |
|
|
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.
|
|
0
|
|
|
|
1, 2, 9, 54, 375, 2848, 22981, 193742, 1688427, 15101778, 137930199, 1281629088, 12081441411, 115288530516, 1111783691037, 10819906562622, 106147110898419, 1048748721598078, 10427413491373843, 104265186535823798, 1047894080773661481
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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
|
|
|
|
STATUS
|
approved
|
| |
|
|
