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.

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

Offset: 1

Author

Emeric Deutsch, Jul 30 2006

Keywords

• nonn
• easy

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

Examples

			a(1)=2 because for each of the trees / and \ the level of the first leaf is 1.
		

Links

• Ran Pan and Jeffrey B. Remmel, Paired patterns in lattice paths, arXiv:1601.07988 [math.CO], 2016-2017.

Crossrefs

Cf. A120988, A002057.

Programs

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

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

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

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