cp's OEIS Frontend

A076616 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).

%I A076616 #39 Jan 09 2025 08:36:34
%S A076616 0,0,0,2,16,64,208,608,1664,4352,11008,27136,65536,155648,364544,
%T A076616 843776,1933312,4390912,9895936,22151168,49283072,109051904,240123904,
%U A076616 526385152,1149239296,2499805184,5419040768,11710496768,25232932864,54223962112,116232552448
%N A076616 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 A076616 Alois P. Heinz, <a href="/A076616/b076616.txt">Table of n, a(n) for n = 0..1000</a>
%H A076616 <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (6,-12,8).
%F A076616 G.f.: 2*(4*x^2-2*x-1)*x^3/(2*x-1)^3. - _Alois P. Heinz_, Sep 20 2011
%F A076616 From _Colin Barker_, May 16 2016: (Start)
%F A076616 a(n) = 2^(n-3)*(n^2-n-4) for n>2.
%F A076616 a(n) = 6*a(n-1)-12*a(n-2)+8*a(n-3) for n>5.
%F A076616 (End)
%F A076616 From _Alois P. Heinz_, May 31 2022: (Start)
%F A076616 a(n) = 2 * A100312(n-3) for n>=3.
%F A076616 a(n) = 16 * A049611(n-3) = 16 * A084851(n-4) for n>=4. (End)
%e A076616 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 A076616 a:= n-> max(-(<<0|1|0>, <0|0|1>, <8|-12|6>>^n. <<1/2, 1, 1>>)[1$2], 0):
%p A076616 seq(a(n), n=0..40);  # _Alois P. Heinz_, Sep 20 2011
%t A076616 Join[{0, 0, 0}, LinearRecurrence[{6, -12, 8}, {2, 16, 64}, 40]] (* _Jean-François Alcover_, Jan 09 2025 *)
%o A076616 (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 A076616 Lower diagonal of A195581 or of A244108.
%Y A076616 Cf. A049611, A076615, A084851, A100312.
%K A076616 nonn,easy
%O A076616 0,4
%A A076616 _Jeffrey Shallit_, Oct 22 2002
%E A076616 More terms from _Alois P. Heinz_, Sep 20 2011