|
%I #36 May 31 2022 18:58:40
%S 0,0,0,2,16,64,208,608,1664,4352,11008,27136,65536,155648,364544,
%T 843776,1933312,4390912,9895936,22151168,49283072,109051904,240123904,
%U 526385152,1149239296,2499805184,5419040768,11710496768,25232932864,54223962112,116232552448
%N Number of permutations of {1,2,...,n} that result in a binary search tree (when elements of the permutation are inserted in that order) of height n-1 (i.e., the second largest possible height).
%H Alois P. Heinz, <a href="/A076616/b076616.txt">Table of n, a(n) for n = 0..1000</a>
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (6,-12,8).
%F G.f.: 2*(4*x^2-2*x-1)*x^3/(2*x-1)^3. - _Alois P. Heinz_, Sep 20 2011
%F From _Colin Barker_, May 16 2016: (Start)
%F a(n) = 2^(n-3)*(n^2-n-4) for n>2.
%F a(n) = 6*a(n-1)-12*a(n-2)+8*a(n-3) for n>5.
%F (End)
%F From _Alois P. Heinz_, May 31 2022: (Start)
%F a(n) = 2 * A100312(n-3) for n>=3.
%F a(n) = 16 * A049611(n-3) = 16 * A084851(n-4) for n>=4. (End)
%e a(3) = 2 because only the permutations (2,1,3) and (2,3,1) result in a search tree of height 2 (notice we count empty external nodes in determining the height). The largest such trees are of height 3.
%p a:= n-> max(-(<<0|1|0>, <0|0|1>, <8|-12|6>>^n. <<1/2, 1, 1>>)[1$2], 0):
%p seq(a(n), n=0..40); # _Alois P. Heinz_, Sep 20 2011
%o (PARI) concat(vector(3), Vec(2*x^3*(1+2*x-4*x^2)/(1-2*x)^3 + O(x^50))) \\ _Colin Barker_, May 16 2016
%Y Lower diagonal of A195581 or of A244108.
%Y Cf. A049611, A076615, A084851, A100312.
%K nonn,easy
%O 0,4
%A _Jeffrey Shallit_, Oct 22 2002
%E More terms from _Alois P. Heinz_, Sep 20 2011
|
