A105633 Row sums of triangle A105632.

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

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} binomial(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

a(n) = the number of Dyck paths of semilength n+1 with no pairs of

consecutive valleys at the same height. Sergi Elizalde, Feb 25 2021

Links

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

Andrei Asinowski, Axel Bacher, Cyril Banderier, and Bernhard Gittenberger, Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata, Laboratoire d'Informatique de Paris Nord (LIPN 2019).

Marilena Barnabei, Flavio Bonetti, Niccolò Castronuovo, and Matteo Silimbani, Permutations avoiding a simsun pattern, The Electronic Journal of Combinatorics (2020) Vol. 27, Issue 3, P3.45. (See a_n in Theorem 4.)

Jean-Luc Baril, Daniela Colmenares, José L. Ramírez, Emmanuel D. Silva, Lina M. Simbaqueba, and Diana A. Toquica, Consecutive pattern-avoidance in Catalan words according to the last symbol, Univ. Bourgogne (France 2023).

Jean-Luc Baril and José Luis Ramírez, Descent distribution on Catalan words avoiding ordered pairs of Relations, arXiv:2302.12741 [math.CO], 2023.

Paul Barry, Riordan Pseudo-Involutions, Continued Fractions and Somos 4 Sequences, arXiv:1807.05794 [math.CO], 2018.

Maciej Bendkowski, Quantitative aspects and generation of random lambda and combinatory logic terms, Ph.D. Thesis, Jagiellonian University, Kraków, 2017.

Maciej Bendkowski, Katarzyna Grygiel, Pierre Lescanne, and Marek Zaionc, Combinatorics of λ-terms: a natural approach, arXiv:1609.08106 [cs.LO], 2016.

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

Maciej Bendkowski, K. Grygiel, and P. Tarau, Random generation of closed simply-typed lambda-terms: a synergy between logic programming and Boltzmann samplers, arXiv preprint arXiv:1612.07682 [cs.LO], 2016-2017.

David Callan, On Ascent, Repetition and Descent Sequences, arXiv:1911.02209 [math.CO], 2019.

Sergi Elizalde, Symmetric peaks and symmetric valleys in Dyck paths, arXiv:2008.05669 [math.CO], 2020.

Juan B. Gil and Michael D. Weiner, On pattern-avoiding Fishburn permutations, arXiv:1812.01682 [math.CO], 2018.

K. Grygiel and P. Lescanne, A natural counting of lambda terms, Preprint 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_{i=1..n-2} a(i)*(a(n-1-i) - a(n-2-i)). a(n) = Sum_{i=0..floor(n/2)} (-1)^i * binomial(n+1-i,i) * binomial(2*(n+1)-3*i, n-2*i) /(n+1-i). - 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} binomial(n-k,j)(0^(j+k)+(1/(j+0^j))*binomial(j,k)*binomial(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

D-finite with recurrence: (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 recurrence 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

a(n) = Sum_{i=0..n+1} (-1)^i*hypergeom([(i+1)/2, i/2+1, i-n-1], [1, 2], -4). - Peter Luschny, May 03 2018

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 + ...

Maple

a := n -> add((-1)^i*hypergeom([(i+1)/2, i/2+1, i-n-1], [1, 2], -4), i=0..n+1):
seq(simplify(a(n)), n=0..26); # Peter Luschny, May 03 2018

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: A352176 A322504 A099754 * A287709 A348202 A196161

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