

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 = x1.  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 stacksorting map and p=132. The same statement is true if p=231 or p=312.  Colin Defant, Jan 14 2019


LINKS

Table of n, a(n) for n=1..25.
Ran Pan and Jeffrey B. Remmel, Paired patterns in lattice paths, arXiv:1601.07988 [math.CO], 20162017.


FORMULA

a(n) = Sum_{k=1..n} k*A120988(n,k).
a(n) = 2n(7n+13)binomial(2n+1,n)/[(n+2)(n+3)(n+4)].
G.f.: z(1+C)C^4, where C=[1sqrt(14z)]/(2z) is the Catalan function.
G.f.: 2[1+2zsqrt(14z)]/[12z+sqrt(14z)]^2.
(n1)*(7*n+6)*(n+4)*a(n) +2*n*(7*n+13)*(2*n+1)*a(n1)=0.  R. J. Mathar, Aug 22 2016


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
(PARI) a(n)=2*n*(7*n+13)*binomial(2*n+1, n)/prod(i=2, 4, n+i) \\ Charles R Greathouse IV, Feb 01 2016


CROSSREFS

Cf. A120988, A002057.
Sequence in context: A212348 A000524 A289614 * A280309 A010763 A077234
Adjacent sequences: A120986 A120987 A120988 * A120990 A120991 A120992


KEYWORD

nonn,easy


AUTHOR

Emeric Deutsch, Jul 30 2006


STATUS

approved



