|
| |
|
|
A100526
|
|
Number of local binary search trees (i.e. labeled binary trees such that every left child has a smaller label than its parent and every right child has a larger label than its parent) with n vertices such that the root has only one child.
|
|
0
| |
|
|
1, 2, 6, 28, 180, 1476, 14728, 173216, 2346480, 35981200, 616111056, 11652662880, 241259095168, 5427319729664, 131818482923520, 3437894427590656, 95825936705566464, 2842834581982211328, 89435890422890433280
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,2
|
|
|
REFERENCES
| C. Chauve, S. Dulucq and A. Rechnitzer, Enumerating alternating trees, J. Combin. Theory Ser. A 94 (2001), 142-151.
A. Postnikov, Intransitive Trees, J. Combin. Theory Ser. A 79 (1997), 360-366.
|
|
|
FORMULA
| a(n)=(1/2^(n-1))*sum(k^(n-1)*binomial(n, k), k=1..n). a(n)=n*A007889(n-1).
|
|
|
EXAMPLE
| a(3)=6 because we have 3L2L1, 2L1R3, 3L1R2, 1R2R3, 1R3L2, 2R3L1 (Li means left child labeled i, RI means right child labeled i).
|
|
|
MAPLE
| seq((1/2^(n-1))*sum(k^(n-1)*binomial(n, k), k=1..n), n=1..22);
|
|
|
CROSSREFS
| Cf. A007889.
Sequence in context: A136631 A002435 A104018 * A200560 A196555 A084262
Adjacent sequences: A100523 A100524 A100525 * A100527 A100528 A100529
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Emeric Deutsch (deutsch(AT)duke.poly.edu), Nov 24 2004
|
| |
|
|
