|
Search: id:A036765
|
|
|
| A036765 |
|
Number of rooted trees with a degree constraint. |
|
+0
6
|
|
| 1, 1, 2, 5, 13, 36, 104, 309, 939, 2905, 9118, 28964, 92940, 300808, 980864, 3219205, 10626023, 35252867, 117485454, 393133485, 1320357501, 4449298136, 15038769672, 50973266380, 173214422068, 589998043276, 2014026871496
(list; graph; listen)
|
|
|
OFFSET
|
0,3
|
|
|
COMMENT
|
a(n) = number of Dyck n-paths that avoid UUUUD. For example, a(4)=13 counts all 14 Dyck 4-paths except UUUUDDDD. - David Callan (callan(AT)stat.wisc.edu), Dec 09 2004
|
|
REFERENCES
|
A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.
L. Takacs, Enumeration of rooted trees and forests, Math. Scientist 18 (1993), 1-10, esp. Eq. (6).
|
|
LINKS
|
T. D. Noe, Table of n, a(n) for n=0..200
Index entries for sequences related to rooted trees
C. Banderier and D. Merlini, Lattice paths with an infinite set of jumps, FPSAC02, Melbourne, 2002.
N. T. Cameron, Random walks, trees and extensions of Riordan group techniques
|
|
FORMULA
|
a(n)=[1/(n+1)]sum(binomial(n+1, n-2j)*binomial(n+1, j), j=0..floor(n/2)). G.f. A(z) satisfies A=1+zA+(zA)^2+(zA)^3. - Emeric Deutsch (deutsch(AT)duke.poly.edu), Nov 29 2003
|
|
MAPLE
|
r := 3; [ seq((1/n)*add( (-1)^j*binomial(n, j)*binomial(2*n-2-j*(r+1), n-1), j=0..floor((n-1)/(r+1))), n=1..30) ]; end;
|
|
MATHEMATICA
|
InverseSeries[Series[y/(1+y+y^2+y^3), {y, 0, 24}], x] (* then A(x)=y(x)/x *) - Len Smiley Apr 11 2000
|
|
CROSSREFS
|
Right hand column of triangle A064580. The sequence of sequences A000007 (0^n), A000012 (constant 1), A001006 (Motzkin), A036765, A036766, ... tends to A000108 (Catalan).
Sequence in context: A116409 A002844 A099164 this_sequence A136751 A154836 A087626
Adjacent sequences: A036762 A036763 A036764 this_sequence A036766 A036767 A036768
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
Search completed in 0.002 seconds
|
