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

0, 0, 0, 2, 16, 64, 208, 608, 1664, 4352, 11008, 27136, 65536, 155648, 364544, 843776, 1933312, 4390912, 9895936, 22151168, 49283072, 109051904, 240123904, 526385152, 1149239296, 2499805184, 5419040768, 11710496768, 25232932864, 54223962112, 116232552448

Offset

0,4

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Index entries for linear recurrences with constant coefficients, signature (6,-12,8).

Formula

G.f.: 2*(4*x^2-2*x-1)*x^3/(2*x-1)^3. - Alois P. Heinz, Sep 20 2011

From Colin Barker, May 16 2016: (Start)

a(n) = 2^(n-3)*(n^2-n-4) for n>2.

a(n) = 6*a(n-1)-12*a(n-2)+8*a(n-3) for n>5.

(End)

From Alois P. Heinz, May 31 2022: (Start)

a(n) = 2 * A100312(n-3) for n>=3.

a(n) = 16 * A049611(n-3) = 16 * A084851(n-4) for n>=4. (End)

Example

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.

Maple

a:= n-> max(-(<<0|1|0>, <0|0|1>, <8|-12|6>>^n. <<1/2, 1, 1>>)[1$2], 0):
seq(a(n), n=0..40);  # Alois P. Heinz, Sep 20 2011

Prog

(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

Crossrefs

Lower diagonal of A195581 or of A244108.

Cf. A049611, A076615, A084851, A100312.

Sequence in context: A061608 A212899 A127276 * A222381 A110048 A094505

Adjacent sequences: A076613 A076614 A076615 * A076617 A076618 A076619

Keyword

nonn,easy

Author

Jeffrey Shallit, Oct 22 2002

Extensions

More terms from Alois P. Heinz, Sep 20 2011

Status

approved