|
| |
|
|
A036765
|
|
Number of rooted trees with a degree constraint.
|
|
24
| |
|
|
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; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,3
|
|
|
COMMENTS
| 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(j=0..floor(n/2), binomial(n+1, n-2j)*binomial(n+1, j) ). G.f. A(z) satisfies A=1+z*A+(z*A)^2+(z*A)^3. - Emeric Deutsch (deutsch(AT)duke.poly.edu), Nov 29 2003
Let F(x) be the reversion of x/(1+x+x^2+x^3), then g.f. A(x)=F(x)/x. [Joerg Arndt, Jun 10 2011]
O.g.f.: A(x) = exp( Sum_{n>=1} [Sum_{k=0..n} C(n,k)^2*x^k*A(x)^k] * x^n/n ).
O.g.f.: A(x) = exp( Sum_{n>=1} [Sum_{k>=0} C(n+k,k)^2*x^k*A(x)^k]*(1-x*A(x))^(2*n+1)* x^n/n ). [Paul D. Hanna, Feb 13 2011]
O.g.f.: A(x) = 1/(1-x)*exp( Sum_{n>=1} A(x)^n*Sum_{k=0..n-1} C(n-1,k)*C(n,k)*x^k)/(1-x)^(2n) * x^(2*n)/n ).
O.g.f.: A(x) = 1/(1-x)*exp( Sum_{n>=1} A(x)^n*Sum_{k>=0} C(n+k-1,k)*C(n+k,k)*x^k) * x^(2n)/n ). [Paul D. Hanna, Feb 24 2011]
Let M = an infinite quadradiagonal matrix with all 1's in every diagonal: (sub, main, super, and super-super), and the rest zeros. V = vector [1,0,0,0,...]. The sequence = left column terms of M*V iterates. [From Gary W. Adamson, (qntmpkt(AT)yahoo.com), Jun 06 2011]
|
|
|
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
|
|
|
PROG
| (PARI) {a(n)=sum(j=0, n\2, binomial(n+1, n-2*j)*binomial(n+1, j))/(n+1)}
(PARI) {a(n)=local(A=1+x+x*O(x^n)); for(i=1, n, A=1+x*A+(x*A)^2+(x*A)^3); polcoeff(A, n)}
(PARI) {a(n)=local(A=1+x); for(i=1, n, A=exp(sum(m=1, n, sum(j=0, m, binomial(m, j)^2*(x*A+x*O(x^n))^j)*x^m/m))); polcoeff(A, n, x)}
(PARI) {a(n)=local(A=1+x); for(i=1, n, A=exp(sum(m=1, n, sum(j=0, n, binomial(m+j, j)^2*(x*A+x*O(x^n))^j)*(1-x*A)^(2*m+1)*x^m/m))); polcoeff(A, n, x)}
(PARI) {a(n)=local(A=1+x); for(i=1, n, A=1/(1-x+x*O(x^n))*exp(sum(m=1, n, A^m*sum(k=0, m-1, binomial(m-1, k)*binomial(m, k)*x^k)/(1-x)^(2*m)*x^(2*m)/m) +x*O(x^n))); polcoeff(A, n)} [Hanna]
(PARI) {a(n)=local(A=1+x); for(i=1, n, A=1/(1-x+x*O(x^n))*exp(sum(m=1, n, A^m*sum(k=0, n, binomial(m+k-1, k)*binomial(m+k, k)*x^k)*x^(2*m)/m) +x*O(x^n))); polcoeff(A, n)} [Paul Hanna]
(PARI) x='x+O('x^66); /* that many terms */
Vec(serreverse(x/(1+x+x^2+x^3))/x) /* show terms */ /* Joerg Arndt, Jun 10 2011 */
|
|
|
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 * A136751 A154836 A087626
Adjacent sequences: A036762 A036763 A036764 * A036766 A036767 A036768
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
| |
|
|
