A291662 Number of ordered rooted trees with 2n non-root nodes such that the maximal outdegree equals n.

1, 1, 8, 53, 326, 1997, 12370, 77513, 490306, 3124541, 20030000, 129024469, 834451788, 5414950283, 35240152706, 229911617041, 1503232609082, 9847379391133, 64617565719052, 424655979547781, 2794563003870310, 18412956934908669, 121455445321173578

Offset: 0

Author

Alois P. Heinz, Aug 28 2017

Keywords

• nonn

Comments

a(n) is also the number of permutations p of [2n] such that in 0p the largest up-jump equals n and no down-jump is larger than 1. An up-jump j occurs at position i in p if p_{i} > p_{i-1} and j is the index of p_i in the increasingly sorted list of those elements in {p_{i}, ..., p_{n}} that are larger than p_{i-1}. A down-jump j occurs at position i in p if p_{i} < p_{i-1} and j is the index of p_i in the decreasingly sorted list of those elements in {p_{i}, ..., p_{n}} that are smaller than p_{i-1}. First index in the lists is 1 here. a(2) = 8: 1243, 1324, 1342, 2134, 2143, 2314, 2341, 2431.

Examples

			a(2) = 8:
.
.    o      o      o      o      o       o      o       o
.    |      |      |     / \    / \     / \    / \     / \
.    o      o      o    o   o  o   o   o   o  o   o   o   o
.    |     / \    / \   |          |  ( )        ( )  |   |
.    o    o   o  o   o  o          o  o o        o o  o   o
.   / \   |          |  |          |
.  o   o  o          o  o          o
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1208

Crossrefs

Cf. A203717.

Bisection (even part) of A303259.

Programs

Mathematica

b[n_, t_, k_] := b[n, t, k] = If[n == 0, 1, If[t > 0, Sum[b[j - 1, k, k]* b[n - j, t - 1, k], {j, 1, n}], b[n - 1, k, k]]];
T[n_, k_] := b[n, k - 1, k - 1] - If[k == 1, 0, b[n, k - 2, k - 2]];
a[n_] := T[2n, n];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, May 29 2019, after Alois P. Heinz in A203717 *)

Python

from sympy.core.cache import cacheit
@cacheit
def b(u, o, k): return 1 if u + o==0 else sum([b(u - j, o + j - 1, k) for j in range(1, min(1, u) + 1)]) + sum([b(u + j - 1, o - j, k) for j in range(1, min(k, o) + 1)])
def a(n): return b(0, 2*n, n) - (0 if n==0 else b(0, 2*n, n - 1))
print([a(n) for n in range(31)]) # Indranil Ghosh, Aug 30 2017

Formula

a(n) = A203717(2n,n).

a(n) ~ (27/4)^n / sqrt(3*Pi*n). - Vaclav Kotesovec, May 02 2018