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

Author

Paul D. Hanna, Apr 17 2005

Keywords

• nonn

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

Examples

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

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. See pp. 3, 8.
• Jean Luc Baril, Rigoberto Flórez, and José L. Ramirez, Generalized Narayana arrays, restricted Dyck paths, and related bijections, Univ. Bourgogne (France, 2025). See p. 10.
• Paul Barry, Riordan Pseudo-Involutions, Continued Fractions and Somos 4 Sequences, arXiv:1807.05794 [math.CO], 2018. See p. 8.
• 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. See p. 12.
• Sergi Elizalde, Symmetric peaks and symmetric valleys in Dyck paths, arXiv:2008.05669 [math.CO], 2020. See p. 5.
• Juan B. Gil and Michael D. Weiner, On pattern-avoiding Fishburn permutations, arXiv:1812.01682 [math.CO], 2018. See pp. 4, 6.
• Katarzyna Grygiel and Pierre 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.
• Robin D. P. Zhou, Pattern avoidance in revised ascent sequences, arXiv:2505.05171 [math.CO], 2025. See pp. 4, 20.

Crossrefs

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

Programs

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 *)

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

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) )); (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

Extensions

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