|
| |
|
|
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).
|
|
4
| |
|
|
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
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,4
|
|
|
LINKS
| Alois P. Heinz, Table of n, a(n) for n = 0..1000
|
|
|
FORMULA
| G.f.: 2*(4*x^2-2*x-1)*x^3/(2*x-1)^3. - Alois P. Heinz, Sep 20 2011
|
|
|
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-> `if` (n<3, 0, (<<0|1|0>, <0|0|1>, <8|-12|6>>^(n-3). <<2, 16, 64>>)[1, 1]): seq (a(n), n=0..40); # Alois P. Heinz, Sep 20 2011
|
|
|
CROSSREFS
| Lower diagonal of A195581. - Alois P. Heinz, Sep 21 2011
Sequence in context: A183762 A061608 A127276 * A110048 A094505 A035598
Adjacent sequences: A076613 A076614 A076615 * A076617 A076618 A076619
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Jeffrey Shallit (shallit(AT)graceland.uwaterloo.ca), Oct 22 2002
|
|
|
EXTENSIONS
| More terms from Alois P. Heinz (heinz(AT)hs-heilbronn.de), Sep 20 2011
|
| |
|
|
