login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

%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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 05:39 EDT 2024. Contains 371235 sequences. (Running on oeis4.)