login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A105633 Row sums of triangle A105632. 12
1, 2, 4, 9, 22, 57, 154, 429, 1223, 3550, 10455, 31160, 93802, 284789, 871008, 2681019, 8298933, 25817396, 80674902, 253106837, 796968056, 2517706037, 7977573203, 25347126630, 80738862085, 257778971504, 824798533933 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

Binomial transform of A007477. INVERT transform of A082582. First differences give A086581 and A025242 (offset 1). Is this sequence equal to A057580?

a(n) = the number of Dyck paths of semilength n+1 avoiding UUDU. a(n) = the number of Dyck paths of semilength n+1 avoiding UDUU = the number of binary trees without zigzag (i.e., with no node with a father, with a right son and with no left son). This sequence is the first column of the triangle A116424. E.g., a(2) = 4 because there exist four Dyck paths of semilength 3 that avoid UUDU: UDUDUD, UDUUDD, UUDDUD, UUUDDD, as well as four Dyck paths of semilength 3 that avoid UDUU: UDUDUD, UUDUDD, UUDDUD, UUUDDD. - I. Tasoulas (jtas(AT)unipi.gr), Feb 15 2006

The sequence beginning 1,1,2,4,9,... gives the diagonal sums of A130749, and has g.f. 1/(1-x-x^2/(1-x/(1-x-x^2/(1-x/(1-x-x^2/(1-... (continued fraction); and general term sum{k=0..floor(n/2),sum{j=0..n-k, C(n-k,j)*A090181(j,k)}}. Its Hankel transform is A099443(n+1). - Paul Barry, Jun 30 2009

The number of plain lambda terms presented by de Bruijn indices, see Bendkowski et al. - Kellen Myers, Jun 15 2015

REFERENCES

K. Grygiel, P. Lescanne, A natural counting of lambda terms, Preprint 2015; http://perso.ens-lyon.fr/pierre.lescanne/PUBLICATIONS/natural_counting.pdf

LINKS

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

Maciej Bendkowski, Katarzyna Grygiel, Pierre Lescanne, Marek Zaionc, A Natural Counting of Lambda Terms, arXiv preprint arXiv:1506.02367 [cs.LO], 2015.

Nancy S. S. Gu, Nelson Y. Li, and Toufik Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.

Toufik Mansour, Statistics on Dyck Paths, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.5.

A. Sapounakis et al., Ordered trees and the inorder transversal, Disc. Math., 306 (2006), 1732-1741.

FORMULA

G.f.: A(x) = (1-x - sqrt((1-x)^2 - 4*x^2/(1-x)))/(2*x^2).

a(n) = 2*a(n-1) + Sum(a(i)*(a(n-1-i)-a(n-2-i)),i=1..n-2). a(n) = Sum((-1)^i * binomial(n+1-i,i) * binomial(2*(n+1)-3*i,n-2*i) /(n+1-i), i=0..[n/2]). - I. Tasoulas (jtas(AT)unipi.gr), Feb 15 2006

G.f.: (1/(1-x)^2)c(x^2/(1-x)^3), where c(x) is the g.f. of A000108. - Paul Barry, May 22 2009

1/(1-x-x/(1-x^2/(1-x-x/(1-x^2/(1-x-x/(1-x^2/(1-... (continued fraction). - Paul Barry, Jun 30 2009

a(n) = sum{k=0..floor(n/2), sum{j=0..n-k, C(n-k,j)(0^(j+k)+(1/(j+0^j))*C(j,k)*C(j,k+1))}}. - Paul Barry, Jun 30 2009

G.f. satisfies: A(x) = (1 + x*A(x)) * (1 + x*(1-x)*A(x)). - Paul D. Hanna, Sep 12 2012

G.f.: exp( Sum_{n>=1} x^n/n * Sum_{k=0..n} binomial(n,k)^2 * (1-x)^k ). - Paul D. Hanna, Sep 12 2012

Conjecture: (n+2)*a(n) +(-4*n-3)*a(n-1) +(2*n+1)*a(n-2) +a(n-3) +(n-3)*a(n-4)=0. - R. J. Mathar, Nov 26 2012

The conjecture is true, since by holonomic transformation, it can be computed formally using GFUN, associated with the equation: x^3 + x^2 - 2x + (x^3 + 3 x^2 -3x +1) A(x) + (x^5 + 2x^3 -4 x^2 + x) A'(x) = 0. - Pierre Lescanne, Jun 30 2015

G.f.: (1 - 1/(G(0)-x))/x^2 where G(k) =  1 + x/(1 + x/(x^2 - 1/G(k+1) )); (recursively defined continued fraction). - Sergei N. Gladkovskii, Dec 16 2012

a(n) ~ 2^(n/3-1/6) * 3^(n+2) * (13+3*sqrt(33))^((n+1)/3) * sqrt(4*(2879 + 561*sqrt(33))^(1/3) + 8*(7822 + 1362*sqrt(33))^(1/3) - 91 - 21*sqrt(33)) / (((26+6*sqrt(33))^(2/3) - (26+6*sqrt(33))^(1/3) - 8)^(n+3/2) * (4*(26+6*sqrt(33))^(1/3) - (26+6*sqrt(33))^(2/3) + 8) * n^(3/2) * sqrt(Pi)). - Vaclav Kotesovec, Mar 13 2014

EXAMPLE

G.f.: A(x) = 1 + 2*x + 4*x^2 + 9*x^3 + 22*x^4 + 57*x^5 + 154*x^6 + 429*x^7 + ...

with A(x)^2 = 1 + 4*x + 12*x^2 + 34*x^3 + 96*x^4 + 274*x^5 + 793*x^6 + ...

where A(x) = 1 + x*(2-x)*A(x) + x^2*(1-x)*A(x)^2.

The logarithm of the g.f. begins:

log(A(x)) = (1 + (1-x))*x + (1 + 2^2*(1-x) + (1-x)^2)*x^2/2 +

(1 + 3^2*(1-x) + 3^2*(1-x)^2 + (1-x)^3)*x^3/3 +

(1 + 4^2*(1-x) + 6^2*(1-x)^2 + 4^2*(1-x)^3 + (1-x)^4)*x^4/4 +

(1 + 5^2*(1-x) + 10^2*(1-x)^2 + 10^2*(1-x)^3 + 5^2*(1-x)^4 + (1-x)^5)*x^5/5 + ...

Explicitly,

log(A(x)) = 2*x + 4*x^2/2 + 11*x^3/3 + 32*x^4/4 + 97*x^5/5 + 301*x^6/6 + 947*x^7/7 + 3008*x^8/8 + 9623*x^9/9 + 30959*x^10/10 + ...

MATHEMATICA

CoefficientList[Series[(1 - x - Sqrt[(1 - x)^2 - 4 x^2/(1 - x)])/(2 x^2), {x, 0, 40}], x] (* Vincenzo Librandi, Mar 15 2014 *)

PROG

(PARI) {a(n)=local(X=x+x*O(x^n)); polcoeff(2/(1-X)/(1-X+sqrt((1-X)^2-4*X^2/(1-X))), n, x)}

(PARI) {a(n)=polcoeff(exp(sum(m=1, n+1, x^m/m*sum(k=0, m, binomial(m, k)^2*(1-x)^(m-k) + x*O(x^n)))), n)} \\ Paul D. Hanna, Sep 12 2012

CROSSREFS

Cf. A105632, A057580, A116424, A216604. See also A258973.

Sequence in context: A143017 A130018 A099754 * A196161 A249561 A099241

Adjacent sequences:  A105630 A105631 A105632 * A105634 A105635 A105636

KEYWORD

nonn

AUTHOR

Paul D. Hanna, Apr 17 2005

EXTENSIONS

More terms from I. Tasoulas (jtas(AT)unipi.gr), Feb 15 2006

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified March 25 01:30 EDT 2017. Contains 284036 sequences.