|
Search: id:A005554
|
|
|
| A005554 |
|
Sum of successive Motzkin numbers.
(Formerly M0801)
|
|
+0
8
|
|
| 1, 2, 3, 6, 13, 30, 72, 178, 450, 1158, 3023, 7986, 21309, 57346, 155469, 424206, 1164039, 3210246, 8893161, 24735666, 69051303, 193399578, 543310782, 1530523638, 4322488212, 12236130298, 34713220977, 98677591278
(list; graph; listen)
|
|
|
OFFSET
|
1,2
|
|
|
COMMENT
|
The Donaghey reference shows that a(n) is the number of n-vertex binary trees such that for each non-root vertex that is incident to exactly two edges, these two edges have opposite slope. It also notes that these trees correspond to Dyck n-paths (A000108) containing no DUDUs and no subpaths of the form UUPDD with P a nonempty Dyck path. For example, a(3)=3 counts UUDUDD, UDUUDD, UUDDUD. - David Callan (callan(AT)stat.wisc.edu), Sep 25 2006
|
|
REFERENCES
|
R. Donaghey, Automorphisms on Catalan trees and bracketing, J. Combin. Theory, Series B, 29 (1980), 75-90.
|
|
FORMULA
|
Inverse binomial transform of A014138: (1, 3, 8, 22, 64, 196,...). - Gary W. Adamson (qntmpkt(AT)yahoo.com), Nov 23 2007
(n + 1) a(n) = 2 n a(n - 1) + (3n - 9) a(n - 2).
G.f.: (x+x^2)M(x) where M(x)=(1 - x - (1 - 2*x - 3*x^2)^(1/2))/(2*x^2) is the GF for the Motzkin numbers A001006. - David Callan (callan(AT)stat.wisc.edu), Sep 25 2006
|
|
CROSSREFS
|
Enumerates the branch-reduced trees encoded by A080981. Cf. A001006.
First differences are in A102071.
Cf. A014138.
Sequence in context: A124682 A079512 A052937 this_sequence A077212 A076836 A117403
Adjacent sequences: A005551 A005552 A005553 this_sequence A005555 A005556 A005557
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
njas
|
|
EXTENSIONS
|
More terms from James A. Sellers (sellersj(AT)math.psu.edu), Jul 10 2000
|
|
|
Search completed in 0.002 seconds
|
