%I #28 Oct 19 2023 16:59:46
%S 2,9,34,123,440,1573,5642,20332,73644,268090,980628,3603065,13293540,
%T 49234605,182991450,682341000,2551955340,9570762990,35985909180,
%U 135628219350,512302356384,1939078493154,7353556121924,27936898370248,106313496846200
%N 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.
%C 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
%C 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
%H Ran Pan and Jeffrey B. Remmel, <a href="http://arxiv.org/abs/1601.07988">Paired patterns in lattice paths</a>, arXiv:1601.07988 [math.CO], 2016-2017.
%F a(n) = Sum_{k=1..n} k*A120988(n,k).
%F a(n) = 2*n*(7n+13)*binomial(2n+1,n)/((n+2)(n+3)(n+4)).
%F G.f.: z*(1+C)*C^4, where C = (1-sqrt(1-4*z))/(2z) is the Catalan function.
%F G.f.: 2*(1+2*z-sqrt(1-4*z))/(1-2*z+sqrt(1-4*z))^2.
%F 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
%F a(n) ~ c*4^n*n^(-3/2), with c = 28/sqrt(Pi). - _Stefano Spezia_, Oct 19 2023
%e a(1)=2 because for each of the trees / and \ the level of the first leaf is 1.
%p a:=n->2*n*(7*n+13)*binomial(2*n+1,n)/(n+2)/(n+3)/(n+4): seq(a(n),n=1..27);
%t Table[2 n (7 n + 13) Binomial[2 n + 1, n] / ((n + 2) (n + 3) (n + 4)), {n, 30}] (* _Vincenzo Librandi_, Feb 01 2016 *)
%o (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
%o (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
%Y Cf. A120988, A002057.
%K nonn,easy
%O 1,1
%A _Emeric Deutsch_, Jul 30 2006
|