|
| |
|
|
A026641
|
|
Number of nodes of even outdegree (including leaves) in all ordered trees with n edges.
|
|
32
| |
|
|
1, 1, 4, 13, 46, 166, 610, 2269, 8518, 32206, 122464, 467842, 1794196, 6903352, 26635774, 103020253, 399300166, 1550554582, 6031074184, 23493410758, 91638191236, 357874310212, 1399137067684, 5475504511858, 21447950506396
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,3
|
|
|
COMMENTS
| Number of lattice paths from (0,0) to (n,n) using steps (1,0),(0,2),(1,1). [Joerg Arndt, Jun 30 2011]
Comment from Emeric Deutsch, Jan 25 2004: (Start)
Let B = 1/sqrt(1-4*z) = g.f. for central binomial coeffs (A000984); F = (1-sqrt(1-4*z))/(z*(3-sqrt(1-4*z))) = g.f. for (A000957).
B = 1 + 2z + 6z^2 + 20z^3 + ... gives the number of nodes in all ordered trees with 0,1,2,3,... edges. On p. 288 of the Deutsch-Shapiro paper one finds that z*B*F=z + 2z^2 + 7z^3 + 24z^4 + ... gives the number of nodes of odd outdegree in all ordered trees with 1,2,3,... edges (cf. A014300).
Consequently, B - z*B*F = 2/(3*sqrt(1-4*z)-1+4*z) = 1 + z + 4z^2 + 13z^3 + 46z^4 + ... gives the total number of nodes of even degree in all ordered trees with 0,1,2,3,4,... edges. (End)
Main diagonal of the following array: first column is filled with 1's, first row is filled alternatively with 1's or 0's: m(i,j)=m(i-1,j)+m(i,j-1): 1 0 1 0 1 ... / 1 1 2 2 3 ... / 1 2 4 6 9 ... / 1 3 7 13 22 ... / 1 4 11 24 46 ... - Benoit Cloitre (benoit7848c(AT)orange.fr), Aug 05 2002
The Hankel transform of [1,1,4,13,46,166,610,2269,...] is 3^n . - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Mar 08 2007
Second binomial transform of A127361 . - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Mar 14 2007
Contribution from Gary W. Adamson (qntmpkt(AT)yahoo.com), Jan 04 2009: (Start)
Starting with offset 1, generated from iterates of M * [1,1,1,...];
where M = a tridiagonal matrix with (0,2,2,2,...) in the main diagonal and
(1,1,1,...) in the super and subdiagonals. (End)
Equals left border of triangle A158815. [From Gary W. Adamson, Mar 27 2009]
Equals the INVERTi transform of A101850: (1, 2, 7, 26, 100,...). - Gary W. Adamson, Jan 10 2012
|
|
|
REFERENCES
| Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.
E. Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math., 241 (2001), 241-265.
|
|
|
FORMULA
| G.f. is logarithmic derivative of the generating function for the Catalan numbers A000108. So this sequence might be called the "log-Catalan" numbers. - Murray R Bremner (bremner(AT)iastate.edu) Jan 25 2004
Sum('binomial(k+n, n-k)*binomial(n-k, k)', 'k'=0..floor(n/2)) - Detlef Pauly (dettodet(AT)yahoo.de), Nov 15 2001
G.f.: 2/(3*sqrt(1-4*z)-1+4*z) - Emeric Deutsch, Jul 09 2002
a(n) = (-1)^n*sum(k=0, n, (-1)^k*C(n+k, k)) - Benoit Cloitre (benoit7848c(AT)orange.fr), Aug 20 2002
a(n)=sum(binomial(2n-2j-1, n-1), j=0..floor(n/2)). - Emeric Deutsch, Jan 28 2004
A Catalan transform of the Jacobsthal numbers A001045(n+1) under the mapping G(x)-> G(xc(x)), c(x) the g.f. of A001008. The inverse mapping is H(x)->H(x(1-x)). a(n)=sum{k=0..n, (k/(2*n-k))*binomial(2*n-k, n-k)*A001045(k+1)} - Paul Barry, Dec 18 2004
a(n)=sum{k=0..n, binomial(2n-k, k)*binomial(k, n-k)}; - Paul Barry, Jul 25 2005
a(n)=Sum[k, 0<=k<=n-1}A126093(n,k) . - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Mar 08 2007
a(n)=(-1/2)^(n+2)+(2/3)*Sum([(4^n-k)*(binomial(2k,k))*(1/(1-2*k))*(1-(-1/8)^(n-k+1))],k=0..n) and a(n)=(-1/2)^(n+2)+(3/4)*Sum(((-1/2)^(n-k))*(binomial(2k,k)),k=0..n) - Aktar Yalcin (aktaryalcin(AT)msn.com), Jul 06 2007
Recurrence relations: a(n+1)=-0.5*d(n)+1.5*binomial(2*n+1,n) or a(n+1)=a(n)+1.5*sum((1/(2*k-1))*binomial(2*k,k)*a(n+1-k),k=2..n+1). a(n)=(2/3)*binomial(2*n,n)+(2/9)*((-2)^n/n!)sum(prod(k-2*p),p=0..n-1)/3^k,k=0..infinity) a(n)=sum((-1)^p*binomial(2*n-p,n),p=0..n). a(n)=sum((1/2^(n-k+1))*binomial(n+k,k),k=0..n)^-(-0.5)^(n+1). [From Richard Choulet (richardchoulet(AT)yahoo.fr), Jan 22 2010]
a(n) is the upper left term of M^n, M = an infinite square production matrix as follows:
1, 3, 0, 0, 0,...
1, 1, 1, 0, 0,...
1, 1, 1, 1, 0,...
1, 1, 1, 1, 1,...
... Also, a(n+1) is the sum of top row terms of M^n; e.g. top row of M^3 = (13, 21, 9, 3), sum = 46 = a(4), a(3) = 13. - Gary W. Adamson, Nov 22 2011
Conjecture: 2n*a(n) +(4-7n)*a(n-1) +2*(1-2n)*a(n-2)=0. - R. J. Mathar, Dec 17 2011
|
|
|
EXAMPLE
| The triangle of number of lattice paths from (0,0) to (n,k) using steps (1,0),(0,2),(1,1) begins
1;
1, 1;
1, 2, 4;
1, 3, 7, 13;
1, 4, 11, 24, 46;
1, 5, 16, 40, 86, 166;
1, 6, 22, 62, 148, 314, 610;
1, 7, 29, 91, 239, 553, 1163, 2269;
This sequence is the diagonal. [Joerg Arndt, Jul 01, 2011]
|
|
|
MAPLE
| seq(add((binomial(k+n, n-k)*binomial(n-k, k)), k=0..floor(n/2)), n=1..30);
for n from 0 to 40 do d(n):=sum(binomial(2*n-k, k)*binomial(k, n-k), k=floor(n/2)..n):od:seq(b(n), n=0..40); a(0):=1:a(1):=1:for n from 1 to 40 do a(n):=(3/(2))*binomial(2*n-1, n-1)-(1/2)*d(n-1):od:seq(d(n), n=0..40); for n from 0 to 40 do a(n):=(-1/2)^(n+2)+(2/3)*sum(4^(n-k)*(binomial(2*k, k)*(1/(1-2*k))*(1-(-1/8)^(n-k+1))), k=0..n):od:seq(a(n), n=0..40); for n from 0 to 40 do a(n):=(-1/2)^(n+2)+(3/4)*sum(((-1/2)^(n-k))*(binomial(2*k, k)), k=0..n):od:seq(a(n), n=0..40); [From Richard Choulet (richardchoulet(AT)yahoo.fr), Jan 22 2010]
|
|
|
PROG
| (PARI) a(n)=(-1)^n*sum(k=0, n, (-1)^k*binomial(n+k, k))
(PARI) /* same as in A092566 but use */
steps=[[1, 0], [0, 2], [1, 1]];
/* Joerg Arndt, Jun 30 2011 */
|
|
|
CROSSREFS
| A158815 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Mar 27 2009]
Cf. A101850
Sequence in context: A047154 A180144 A149434 * A149435 A149436 A087440
Adjacent sequences: A026638 A026639 A026640 * A026642 A026643 A026644
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Clark Kimberling (ck6(AT)evansville.edu)
|
| |
|
|
