|
| |
|
|
A120989
|
|
Level of the first leaf (in preorder traversal) of a binary tree, summed over all binary trees with n edges. A binary tree is a rooted tree in which each vertex has at most two children and each child of a vertex is designated as its left or right child.
|
|
4
|
|
|
|
2, 9, 34, 123, 440, 1573, 5642, 20332, 73644, 268090, 980628, 3603065, 13293540, 49234605, 182991450, 682341000, 2551955340, 9570762990, 35985909180, 135628219350, 512302356384, 1939078493154, 7353556121924, 27936898370248, 106313496846200
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
COMMENTS
|
a(n) is the number of lattice paths from (0,0) to (n+2,n+2) using E(1,0) and N(0,1) as steps that have exactly two E steps below subdiagonal y = x-1. - Ran Pan, Feb 01 2016
a(n) is the number of permutations pi of [n+3] such that s(pi)=p456...(n+3), where s is West's stack-sorting map and p=132. The same statement is true if p=231 or p=312. - Colin Defant, Jan 14 2019
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = Sum_{k=1..n} k*A120988(n,k).
a(n) = 2*n*(7n+13)*binomial(2n+1,n)/((n+2)(n+3)(n+4)).
G.f.: z*(1+C)*C^4, where C = (1-sqrt(1-4*z))/(2z) is the Catalan function.
G.f.: 2*(1+2*z-sqrt(1-4*z))/(1-2*z+sqrt(1-4*z))^2.
D-finite with recurrence -(n-1)*(7*n+6)*(n+4)*a(n) +2*n*(7*n+13)*(2*n+1)*a(n-1)=0. - R. J. Mathar, Aug 22 2016
a(n) ~ c*4^n*n^(-3/2), with c = 28/sqrt(Pi). - Stefano Spezia, Oct 19 2023
|
|
|
EXAMPLE
|
a(1)=2 because for each of the trees / and \ the level of the first leaf is 1.
|
|
|
MAPLE
|
a:=n->2*n*(7*n+13)*binomial(2*n+1, n)/(n+2)/(n+3)/(n+4): seq(a(n), n=1..27);
|
|
|
MATHEMATICA
|
Table[2 n (7 n + 13) Binomial[2 n + 1, n] / ((n + 2) (n + 3) (n + 4)), {n, 30}] (* Vincenzo Librandi, Feb 01 2016 *)
|
|
|
PROG
|
(Magma) [2*n*(7*n+13)*Binomial(2*n+1, n)/((n+2)*(n+3)*(n+4)): n in [1..30]]; // Vincenzo Librandi, Feb 01 2016
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
