|
Search: id:A100526
|
|
|
| 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
|
|
| 1, 2, 6, 28, 180, 1476, 14728, 173216, 2346480, 35981200, 616111056, 11652662880, 241259095168, 5427319729664, 131818482923520, 3437894427590656, 95825936705566464, 2842834581982211328, 89435890422890433280
(list; graph; listen)
|
|
|
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.
Adjacent sequences: A100523 A100524 A100525 this_sequence A100527 A100528 A100529
Sequence in context: A136631 A002435 A104018 this_sequence A084262 A084870 A111342
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), Nov 24 2004
|
|
|
Search completed in 0.002 seconds
|
