A086581 -id:A086581 - cp's OEIS frontend

A082582 Expansion of (1 + x^2 - sqrt( 1 - 4x + 2x^2 + x^4)) / (2*x) in powers of x.

1, 1, 1, 2, 5, 13, 35, 97, 275, 794, 2327, 6905, 20705, 62642, 190987, 586219, 1810011, 5617914, 17518463, 54857506, 172431935, 543861219, 1720737981, 5459867166, 17369553427, 55391735455, 177040109419, 567019562429, 1819536774089

Offset: 0

Emanuele Munarini, May 07 2003

a(n) is the number of Dyck paths of semilength n with no UUDD. See A025242 for a bijection between paths avoiding DDUU versus UUDD.
Also number of lattice paths from (0,0) to (n,n) which do not go above the diagonal x=y using steps (1,k), (k,1) with k>=1. - Alois P. Heinz, Oct 07 2015
a(n) is the number of bargraphs of semiperimeter n (n>=2). Example: a(4) = 5; the 5 bargraphs correspond to the compositions [1,1,1], [1,2], [2,1], [2,2], [3]. - Emeric Deutsch, May 20 2016 [a(n) are the row sums of A271942 for n >= 2. Peter Luschny, Oct 18 2020]
a(n) is the number of skew Motzkin paths of length n. A skew Motzkin path is a path in the first quadrant which begins at the origin, ends on the x-axis, consists of steps U=(1,1) (up), D=(1,-1) (down), F=(1,0) (flat) and A=(-1,1) (anti-down) so that down and anti-down steps do not overlap. - Sergey Kirgizov, Oct 03 2018
From Gus Wiseman, Jul 04 2019: (Start)
Conjecture: Also the number of maximal simple graphs with vertices {1..n} and no weakly nesting edges. Two edges {a,b}, {c,d} are weakly nesting if a <= c < d <= b or c <= a < b <= d. For example, the a(1) = 1 through a(5) = 13 edge-sets are:
  {}  {12}  {13}     {14}        {15}
            {12,23}  {12,24}     {12,25}
                     {13,24}     {13,25}
                     {13,34}     {14,25}
                     {12,23,34}  {14,35}
                                 {14,45}
                                 {12,23,35}
                                 {12,24,35}
                                 {12,24,45}
                                 {13,24,35}
                                 {13,24,45}
                                 {13,34,45}
                                 {12,23,34,45}
Cf. A006125, A054726, A117662, A326244, A326257, A326289, A326293, A326329, A326337, A326338, A326340.
(End)
a(n) is the number of Dyck n-paths in which no nonterminal descent has the same length as the preceding ascent. Example: a(3) = 2 counts UUDUDD and UUUDDD where the latter path qualifies because DDD is the terminal descent. - David Callan, Dec 14 2021

			1 + x + x^2 + 2*x^3 + 5*x^4 + 13*x^5 + 35*x^6 + 97*x^7 + 275*x^8 + ...
a(3)=2 because the only Dyck paths of semilength 3 with no UUDD in them are UDUDUD and UUDUDD (the nonqualifying ones being UDUUDD, UUDDUD and UUUDDD). - _Emeric Deutsch_, Jan 27 2003

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
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. 11.
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, 13.
Aubrey Blecher, Charlotte Brennan, and Arnold Knopfmacher, Peaks in bargraphs, Trans. Royal Soc. South Africa, 71, No. 1, 2016, 97-103.
Miklos Bona and Elijah DeJonge, Pattern avoiding permutations and involutions with a unique longest increasing subsequence, arXiv:2003.10640 [math.CO], 2020.
Mireille Bousquet-Mélou and Andrew Rechnitzer, The site-perimeter of bargraphs, Adv. in Appl. Math. 31 (2003), 86-112.
Ralph L. Childress, Recursive Prime Factorizations: Dyck Words as Numbers, arXiv:2102.02777 [cs.FL], 2021.
Emeric Deutsch and Sergi Elizalde, Statistics on bargraphs viewed as cornerless Motzkin paths, arXiv:1609.00088 [math.CO], September 2016.
Chris Dyer, Gábor Melis, and Phil Blunsom, A Critical Analysis of Biased Parsers in Unsupervised Parsing, arXiv:1909.09428 [cs.CL], 2019.
Juan B. Gil and Michael D. Weiner, On pattern-avoiding Fishburn permutations, arXiv:1812.01682 [math.CO], 2018-2019.
Qing Lin Lu, Skew Motzkin paths, Acta Mathematica Sinica, English Series, 33(5) (2017), 657-667.
Toufik Mansour and Mark Shattuck, On ascent sequences avoiding 021 and a pattern of length four, arXiv:2507.17947 [math.CO], 2025. See p. 19.
Helmut Prodinger, Cornerless, peakless, valleyless Motzkin paths (regular and skew) and applications to bargraphs, arXiv:2501.13645 [math.CO], 2025. See p. 11.
Robin D. P. Zhou, Pattern avoidance in revised ascent sequences, arXiv:2505.05171 [math.CO], 2025. See pp. 4, 22.

Apart from initial term, same as A025242.
See A086581 for Dyck paths avoiding DDUU.
Cf. A000108, A218321, A263316, A271942 (refinement).
Column k=0 of A098978.

a082582 n = a082582_list !! n
a082582_list = 1 : 1 : f [1,1] where
   f xs'@(x:_:xs) = y : f (y : xs') where
     y = x + sum (zipWith (*) xs' $ reverse xs)
-- Reinhard Zumkeller, Nov 13 2012

f:= gfun:-rectoproc({(n-1)*a(n)+(2*n+4)*a(n+2)+(-14-4*n)*a(n+3)+(5+n)*a(n+4), a(0) = 1, a(1) = 1, a(2) = 1, a(3) = 2},a(n),remember):
map(f,[$0..100]); # Robert Israel, May 20 2016

a[0]=1;a[n_Integer]:=a[n]=a[n-1]+Sum[a[k]*a[n-1-k],{k,2,n-1}];Table[a[n],{n,0,40}] (* Vladimir Joseph Stephan Orlovsky, Mar 30 2011 *)
a[ n_] := SeriesCoefficient[ 2 / (1 + x^2 + Sqrt[1 - 4 x + 2 x^2 + x^4]), {x, 0, n}] (* Michael Somos, Jul 01 2011 *)
a[n_] := Sum[HypergeometricPFQ[{-k, 3 + k, k - n}, {1, 2}, 1], {k, 0, n}];
Join[{1, 1}, Table[a[n], {n, 0, 26}]] (* Peter Luschny, Oct 18 2020 *)

a(n):=sum(sum((binomial(n-k-2,j)*binomial(k,j)*binomial(k+j+2,j))/(j+1),j,0,n-k-1),k,0,n-2); /* Vladimir Kruchinin, Oct 18 2020 */

{a(n) = polcoeff( (1 + x^2 - sqrt( 1 - 4*x + 2*x^2 + x^4 + x^2 * O(x^n))) / 2, n+1)} /* Michael Somos, Jul 22 2003 */

{a(n) = if( n<0, 0, polcoeff( 2 /(1 + x^2 + sqrt( 1 - 4*x + 2*x^2 + x^4 + x * O(x^n))),n))} /* Michael Somos, Jul 01 2011 */

{a(n) = local(A); if( n<0, 0, A = O(x); for( k = 0, n, A = 1 / (1 + x^2 - x * A)); polcoeff( A, n))} /* Michael Somos, Mar 28 2011 */

G.f.: (1 + x^2 - sqrt( 1 - 4*x + 2*x^2 + x^4)) / (2*x) = 2 /(1 + x^2 + sqrt( 1 - 4*x + 2*x^2 + x^4)).
G.f. A(x) satisfies the equation 0 = 1 - (1 + x^2) * A(x) + x * A(x)^2. - Michael Somos, Jul 22 2003
G.f. A(x) satisfies A(x) = 1 / (1 + x^2 - x * A(x)). - Michael Somos, Mar 28 2011
G.f. A(x) = 1 / (1 + x^2 - x / (1 + x^2 - x / (1 + x^2 - ... ))) continued fraction. - Michael Somos, Jul 01 2011
Series reversion of x * A(x) is x * A007477(-x). - Michael Somos, Jul 22 2003
a(n+1) = a(n) + Sum(a(k)*a(n-k): k=2..n), a(0) = a(1) = 1. - Reinhard Zumkeller, Nov 13 2012
G.f.: 1 + x - x*G(0), where G(k)= 1 - 1/(1 - x/(1 - x/(1 - x/(1 - x/(x - 1/G(k+1) ))))); (continued fraction). - Sergei N. Gladkovskii, Jul 12 2013
D-finite with recurrence: (n-1)*a(n)+(2*n+4)*a(n+2)+(-14-4*n)*a(n+3)+(5+n)*a(n+4) = 0. - Robert Israel, May 20 2016
a(n) = Sum_{k=0..n-2} Sum_{j=0..n-k-1} C(n-k-2,j)*C(k,j)*C(k+j+2,j)/(j+1), n>1, a(0)=1, a(1)=1. - Vladimir Kruchinin, Oct 18 2020
a(n) = Sum_{k=0..n-2} HypergeometricPFQ[{-k, 3 +k, k - n + 2}, {1, 2}, 1] for n >= 2. - Peter Luschny, Oct 18 2020
a(n) ~ sqrt(2+r) / (2 * sqrt(Pi) * n^(3/2) * r^n), where r = 0.295597742522084... is the real root of the equation r^3 + r^2 + 3*r - 1 = 0. - Vaclav Kotesovec, Jun 05 2022
G.f.: 1/G(x), with G(x) = 1 - (x-x^2)/(1-x/G(x)) (continued fraction). - Nikolaos Pantelidis, Jan 11 2023

A105633 Row sums of triangle A105632.

Original entry on oeis.org

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

Paul D. Hanna, Apr 17 2005

nonn

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

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

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.

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

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

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

{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)}

{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

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

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

A108626 Antidiagonal sums of square array A108625, in which row n equals the crystal ball sequence for A_n lattice.

Original entry on oeis.org

1, 2, 5, 14, 41, 124, 383, 1200, 3799, 12122, 38919, 125578, 406865, 1322772, 4313155, 14099524, 46192483, 151628090, 498578411, 1641921014, 5414619739, 17878144968, 59097039545, 195548471268, 647665451911, 2146947613286

Offset: 0

Paul D. Hanna, Jun 12 2005

nonn

Limit a(n+1)/a(n) = 3.3829757679... = 1/r = 3 + r + r^2, where r is radius of convergence of A(x), which diverges at x=r.

Infinitely many recurrence relations of even order 2d can be built for this sequence; first define the following polynomial: P(d) = (1/2^d) * Sum_{i=0..floor(d/2)} binomial(d, 2*i) * (x^4 + 2*x^2 - 4*x + 1)^i * (x^2 + 2*x - 1)^(d - 2*i) then call c(d,k) the coefficient of term with power k in the polynomial P(d); then we have the relation: Sum_{k=0..2*d} c(d, 2*d-k)*a(n+k) = (-1)^d * Sum_{k=0..n} Sum_{i=0..k} binomial(n-k, d+i)*binomial(n-k, i)*binomial(n-i, k-i). - Thomas Baruchel, Jan 26 2015

			Log(A(x)) = 2*x + 6*x^2/2 + 20*x^3/3 + ... + A108627(n)*x^n/n + ...

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Thomas Baruchel and C. Elsner, On error sums formed by rational approximations with split denominators, arXiv preprint arXiv:1602.06445 [math.NT], 2016.
Sergi Elizalde, Symmetric peaks and symmetric valleys in Dyck paths, arXiv:2008.05669 [math.CO], 2020, p. 16.

Cf. A108625, A108627, A180091.

R:=PowerSeriesRing(Rationals(), 40); Coefficients(R!( 1/Sqrt(1-4*x+2*x^2+x^4) )); // G. C. Greubel, Oct 06 2023

a := n -> add(binomial(n,k)*hypergeom([-k,k-n,k-n], [1,-n], 1), k=0..n):
seq(simplify(a(n)), n=0..25); # Peter Luschny, Feb 13 2018

CoefficientList[Series[1/Sqrt[x^4+2*x^2-4*x+1], {x, 0, 50}], x] (* Vincenzo Librandi, Nov 08 2014 *)

a(n)=sum(k=0,n,sum(i=0,k,binomial(n-k,i)^2*binomial(n-i,k-i)))

{a(n)=polcoeff( sum(m=0, n, x^m * sum(k=0, m, binomial(m, k)^2 * x^k) / (1-x +x*O(x^n))^(m+1)) , n)}
for(n=0, 30, print1(a(n), ", ")) \\ Paul D. Hanna, Nov 08 2014

def A108626_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( 1/sqrt(1-4*x+2*x^2+x^4) ).list()
A108626_list(40) # G. C. Greubel, Oct 06 2023

a(n) = Sum_{k=0..n} Sum_{i=0..k} C(n, i)^2 * C(n+k-i, k-i).
G.f.: 1 / sqrt(x^4 + 2*x^2 - 4*x + 1). - Thomas Baruchel, Nov 08 2014
G.f.: A(x) = exp( Sum_{n>=1} A108627(n)*x^n/n ), where A108627 has g.f.: 2*x*(1 - x - x^3)/((1-x)*(1 - 3*x - x^2 - x^3)).
a(n) = ( (5*n-3)*a(n-1) - (6*n-8)*a(n-2) + (2*n-4)*a(n-3) - (n-2)*a(n-4) + (n-3)*a(n-5) ) / n. - Thomas Baruchel, Nov 08 2014
a(n+2) - 2*a(n+1) - a(n) = 2*Sum_{k=0..n} Sum_{i=0..k} binomial(n-k+1,i-1)*binomial(n-k+1,i)*binomial(n-i+1,k-i) = Sum_{k=0..n} a(k)*A086581(n-k+1). - Thomas Baruchel, Nov 08 2014
G.f.: Sum_{n>=0} (2*n)!/n!^2 * x^(2*n) / ((1-x)*(1-2*x)^(3*n+1)). - Paul D. Hanna, Nov 08 2014
G.f.: Sum_{n>=0} x^n/(1-x)^(n+1) * Sum_{k=0..n} C(n,k)^2 * x^k. - Paul D. Hanna, Nov 08 2014
Partial sums of A171155: a(n) = Sum_{i=0..n} A171155(n). - Thomas Baruchel, Nov 08 2014
Recurrence: n*a(n) = 2*(2*n-1)*a(n-1) - 2*(n-1)*a(n-2) - (n-2)*a(n-4). - Vaclav Kotesovec, Dec 20 2015
a(n) = Sum_{k=0..n} binomial(n,k)*hypergeometric3F2([-k,k-n,k-n], [1,-n], 1). - Peter Luschny, Feb 13 2018

A025242 Generalized Catalan numbers A(x)^2 -(1+x)^2A(x) +x(2+x+x^2) =0.

Original entry on oeis.org

2, 1, 1, 2, 5, 13, 35, 97, 275, 794, 2327, 6905, 20705, 62642, 190987, 586219, 1810011, 5617914, 17518463, 54857506, 172431935, 543861219, 1720737981, 5459867166, 17369553427, 55391735455, 177040109419, 567019562429, 1819536774089

Offset: 1

Clark Kimberling, Olivier Gérard

Number of Dyck paths of semilength n-1 with no UUDD (n>1). Example: a(4)=2 because the only Dyck paths of semilength 3 with no UUDD in them are UDUDUD and UUDUDD (the nonqualifying ones being UDUUDD, UUDDUD and UUUDDD). - Emeric Deutsch, Jan 27 2003
a(n) is the number of Dyck (n-2)-paths with no DDUU (n>2). Example: a(6)=13 counts all 14 Dyck 4-paths except UUDDUUDD which contains a DDUU. There is a simple bijective proof: given a Dyck path that avoids DDUU, for every occurrence of UUDD except the first, the ascent containing this UU must be immediately preceded by a UD (else a DDUU would be present). Transfer the latter UD to the middle of the DD in the UUDD. Then insert a new UD in the middle of the first DD if any; if not, the path is a sawtooth UDUD...UD, in which case insert a UD at the end. This is a bijection from DDUU-avoiding Dyck n-paths to UUDD-avoiding Dyck (n+1)-paths. - David Callan, Sep 25 2006
For n>1, a(n) is the number of cyclic permutations of [n-1] that avoid the vincular pattern 13-4-2, i.e., the pattern 1342 where the 1 and 3 must be adjacent. By the trivial Wilf equivalence, the same applies for 24-3-1, 31-2-4, and 42-1-3. - Rupert Li, Jul 27 2021

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Sela Fried, Even-up words and their variants, arXiv:2505.14196 [math.CO], 2025. See p. 10.
Petr Gregor, Torsten Mütze, and Namrata, Combinatorial generation via permutation languages. VI. Binary trees, arXiv:2306.08420 [cs.DM], 2023.
Petr Gregor, Torsten Mütze, and Namrata, Pattern-Avoiding Binary Trees-Generation, Counting, and Bijections, Leibniz Int'l Proc. Informatics (LIPIcs), 34th Int'l Symp. Algor. Comp. (ISAAC 2023). See p. 33.13.
Nancy S. S. Gu, Nelson Y. Li, and Toufik Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.
Jia Huang and Erkko Lehtonen, Associative-commutative spectra for some varieties of groupoids, arXiv:2401.15786 [math.CO], 2024. See p. 18.
Vít Jelínek, Toufik Mansour and Mark Shattuck, On multiple pattern avoiding set partitions, Adv. Appl. Math. 50 (2) (2013) 292-326, Theorem 4.1, without the leading 2.
Yvan Le Borgne, Counting Upper Interactions in Dyck Paths, Séminaire Lotharingien de Combinatoire, Vol. 54, B54f (2006), 16 pp.
Rupert Li, Vincular Pattern Avoidance on Cyclic Permutations, arXiv:2107.12353 [math.CO], 2021.
Toufik Mansour, Restricted 1-3-2 permutations and generalized patterns, arXiv:math/0110039 [math.CO], 2001.
Toufik Mansour, Restricted 1-3-2 permutations and generalized patterns, Annals of Combin., 6 (2002), 65-76. (Example 2.10.)
Toufik Mansour and Mark Shattuck, Restricted partitions and generalized Catalan numbers, PU. M. A., Vol. (2011), No. 2, pp. 239-251. - From _N. J. A. Sloane_, Oct 13 2012
Lara Pudwell, Pattern-avoiding ascent sequences, Slides from a talk, 2015.
Lara Pudwell and Andrew Baxter, Ascent sequences avoiding pairs of patterns, Slides, Permutation Patterns 2014, East Tennessee State University Jul 07 2014.
A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.

Cf. A000108, A001006, A006318, A004148, A007477, A082582, A086581.

a[ 0 ]=1; a[ n_Integer ] := a[ n ]=a[ n-1 ]+Sum[ a[ k ]*a[ n-1-k ], {k, 2, n-1} ];

a(n)=polcoeff((1+2*x+x^2-sqrt(1-4*x+2*x^2+x^4+x*O(x^n)))/2,n)

a(n) = a(1)*a(n-1) + a(2)*a(n-2) + ... + a(n-3)*a(3) for n >= 4.
G.f.: (1+2*x+x^2-sqrt(1-4*x+2*x^2+x^4))/2. - Michael Somos, Jun 08 2000
Conjecture: n*(n+1)*a(n) +(n^2+n+2)*a(n-1) +2*(-9*n^2+15*n+17)*a(n-2) +2*(5*n+4)*(n-4)*a(n-3) +(n+1)*(n-6)*a(n-4) +(5*n+4)*(n-7)*a(n-5)=0. - R. J. Mathar, Jan 12 2013
G.f.: 2 + x - x*G(0), where G(k) = 1 - 1/(1 - x/(1 - x/(1 - x/(1 - x/(x - 1/G(k+1) ))))); (continued fraction). - Sergei N. Gladkovskii, Jul 12 2013

A114492 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n and having k DDUU's, where U=(1,1), D=(1,-1) (0<=k<=floor(n/2)-1 for n>=2).

Original entry on oeis.org

1, 1, 2, 5, 13, 1, 35, 7, 97, 34, 1, 275, 143, 11, 794, 558, 77, 1, 2327, 2083, 436, 16, 6905, 7559, 2180, 151, 1, 20705, 26913, 10051, 1095, 22, 62642, 94547, 43796, 6758, 268, 1, 190987, 328943, 183130, 37402, 2409, 29, 586219, 1136218, 742253, 191408

Offset: 0

Emeric Deutsch, Dec 01 2005

Rows 0 and 1 contain one term each; row n contains floor(n/2) terms (n>=2).
Row sums are the Catalan numbers (A000108). Column 0 yields A086581.
Sum(k*T(n,k),k=0..floor(n/2)-1) = binomial(2n-3,n-4) (A003516).

			T(5,1) = 7 because we have UU(DDUU)DUDD, UU(DDUU)UDDD, UDUU(DDUU)DD, their mirror images and UUU(DDUU)DDD (the DDUU's are shown between parentheses).
Triangle starts:
   1;
   1;
   2;
   5;
  13,  1;
  35,  7;
  97, 34, 1;
  ...

Alois P. Heinz, Rows n = 0..200, flattened
Jean-Luc Baril, Pamela E. Harris, Kimberly J. Harry, Matt McClinton, and José L. Ramírez, Enumerating runs, valleys, and peaks in Catalan words, arXiv:2404.05672 [math.CO], 2024. See p. 12.
FindStat - Combinatorial Statistic Finder, The number of occurrences of the contiguous pattern [.,[.,[[.,.],.]]].
Toufik Mansour and Mark Shattuck, Counting occurrences of subword patterns in non-crossing partitions, Art Disc. Appl. Math. (2022).
A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.

Cf. A000108, A086581, A003516.

G:=1/2/(-t*z-z^2+z^2*t)*(-1+2*z-2*t*z-z^2+z^2*t+sqrt(1+z^4-2*z^4*t+z^4*t^2-4*z+2*z^2-2*z^2*t)): Gser:=simplify(series(G,z=0,17)): P[0]:=1: for n from 1 to 14 do P[n]:=coeff(Gser,z^n) od: 1; 1; for n from 0 to 14 do seq(coeff(t*P[n],t^j),j=1..floor(n/2)) od; # yields sequence in triangular form

m = 15; G[, ] = 0;
Do[G[t_, z_] = (-1 + z - t z - t z G[t, z]^2 - z^2 G[t, z]^2 + t z^2 G[t, z]^2)/(-1 + 2z - 2t z - z^2 + t z^2) + O[t]^Floor[m/2] + O[z]^m, {m}];
CoefficientList[#, t]& /@ Take[CoefficientList[G[t, z], z], m] // Flatten (* Jean-François Alcover, Oct 05 2019 *)

G.f.: G=G(t, z) satisfies z(t+z-tz)G^2-(1-2(1-t)z+(1-t)z^2)G+1-z+tz=0.

A120059 Triangle read by rows: T(n,k) is the number of Dyck n-paths (A000108) whose longest pyramid has size k.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 2, 2, 1, 0, 5, 6, 2, 1, 0, 13, 19, 7, 2, 1, 0, 35, 63, 24, 7, 2, 1, 0, 97, 212, 85, 25, 7, 2, 1, 0, 275, 723, 307, 90, 25, 7, 2, 1, 0, 794, 2491, 1121, 330, 91, 25, 7, 2, 1, 0, 2327, 8654, 4129, 1225, 335, 91, 25, 7, 2, 1

Offset: 0

David Callan, Jun 06 2006

A pyramid in a Dyck path is a subpath of the form U^k D^k with k>=1 (U=upstep, D=downstep). The longest pyramid is indicated by lowercase letters in the Dyck path UUDuuudddDUD and it has size 3.

			Table begins
\ k..0....1....2....3....4....5....6....7
n
0 |..1
1 |..0....1
2 |..0....1....1
3 |..0....2....2....1
4 |..0....5....6....2....1
5 |..0...13...19....7....2....1
6 |..0...35...63...24....7....2....1
7 |..0...97..212...85...25....7....2....1
a(3,2)=2 because the Dyck 3-paths whose longest pyramid has size 2 are
UUDDUD, UDUUDD.

Cf. A120060. Column k=1 is A086581. Row sums are the Catalan numbers A000108.

Clear[a] (* a[n,k] is the number of Dyck n-paths whose longest pyramid has size <=k *) a[0,k_]/;k>=0 := 1 a[1,k_]/;k>=1 := 1 a[n_,k_]/;k>=n := 1/(n+1)Binomial[2n,n] a[n_,0]/;n>=1 := 0 a[n_,k_]/;k<0:= 0 a[n_,k_]/; 1<=k && k=2 := a[n,k] = Sum[a[j-1,k] a[n-j,k],{j,n}] - a[n-k-1,k] Table[a[n,k]-a[n,k-1],{n,0,8},{k,0,n}]

Generating function for column k>=1 is F[k]-F[k-1] where F[k]:=(1 + x^(k+1) - ((1 + x^(k+1))^2 - 4*x)^(1/2))/(2*x).

A238438 Expansion of 1/G(0) where G(k) = 1 - q/(1 - q - q^3 / G(k+1) ).

Original entry on oeis.org

1, 1, 2, 4, 9, 21, 50, 121, 297, 738, 1853, 4694, 11982, 30790, 79586, 206786, 539784, 1414905, 3722776, 9828501, 26028969, 69129150, 184076913, 491340306, 1314412198, 3523519135, 9463563168, 25462981484, 68626114915, 185246103584, 500779373140, 1355636896041, 3674558399538, 9972405246294, 27095580261125

Offset: 0

Joerg Arndt, Feb 27 2014

nonn

What does this sequence count?

G. C. Greubel, Table of n, a(n) for n = 0..1000

Cf. A086581: 1/G(0) where G(k) = 1 - q/(1 - q - q^2 / G(k+1) ).

Cf. A119370: 1/G(0) where G(k) = 1 - q/(1 - (q + q^2) / G(k+1) ).

CoefficientList[Series[2*(1-x)/(1 - 2*x + x^3 + Sqrt[1 - 4*x + 4*x^2 - 2*x^3 + x^6]), {x, 0, 20}], x] (* Vaclav Kotesovec, Mar 01 2014 *)

N = 66;  q = 'q + O('q^N);
G(k) = if(k>N, 1,  1 - q/(1 - q - q^3 / G(k+1) ) );
Vec( 1/G(0) )

From Vaclav Kotesovec, Mar 01 2014: (Start)
G.f.: 2*(1-x)/(1 - 2*x + x^3 + sqrt(1 - 4*x + 4*x^2 - 2*x^3 + x^6)).
D-finite with Recurrence: (n+3)*a(n) = 2*(2*n+3)*a(n-1) - 4*n*a(n-2) + (2*n-3)*a(n-3) - (n-6)*a(n-6).
a(n) ~ (6*r^2+14*r+17) * sqrt(7*r-2) / (2 * sqrt(Pi) * n^(3/2) * r^(n-1/2)), where r = 1/3*(-2 - 2*(2/(47 + 3*sqrt(249)))^(1/3) + (1/2*(47 + 3*sqrt(249)))^(1/3)) = 0.3532099641993244294831... is the root of the equation r^3 + 2*r^2 + 2*r = 1.
(End)
G.f. A(q) satisfies 0 = -q^3*A(q)^2 + (q^3 - 2*q + 1)*A(q) + (q - 1).

A259845 a(0)=1, a(1)=3, and the INVERT transform of the sequence deletes the 3.

Original entry on oeis.org

1, 3, 4, 11, 38, 136, 512, 1993, 7958, 32420, 134216, 563030, 2388092, 10224320, 44127328, 191783029, 838623654, 3686965308, 16287624440, 72262899994, 321852273332, 1438540956048, 6450223722816, 29006443606746, 130790584554748, 591191800834696

Offset: 0

Gary W. Adamson, Jul 06 2015

The sequence is N = 3 in an infinite set, with the first few being:
A086581, N = 0: (1, 0, 1, 2, 5, 13, 35, 97, ...)
A000108, N = 1: (1, 1, 2, 5, 14, 42, 132, ...)
A171199, N = 2: (1, 2, 3, 8, 25, 83, 289, ...)
... The INVERT transforms of the sequences delete the second terms in the sequences.
The g.f. was contributed by Paul D. Hanna: From the definition of the INVERT transform, 1/(1 - x*A) = A - (N-1)*x. Thus, (1 + (N-1)*x - (1 + (N-1)*x^2)*A) + x*A^2 = 0.  The g.f. follows, below.

			The INVERT transform of (1, 3, 4, 11, 38, 136, ...) is (1, 4, 11, 38, 136, ...).

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Amya Luo, Pattern Avoidance in Nonnesting Permutations, Undergraduate Thesis, Dartmouth College (2024). See p. 16.

Cf. A086581, A000108, A171199.

CoefficientList[Series[1/(2*x) + x - Sqrt[1 - 4*x - 4*x^2 + 4*x^4]/(2*x), {x, 0, 25}], x] (* Michael De Vlieger, Jun 12 2024 *)

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

More terms from Alois P. Heinz, Jul 07 2015

cp's OEIS Frontend

A082582 Expansion of (1 + x^2 - sqrt( 1 - 4*x + 2*x^2 + x^4)) / (2*x) in powers of x.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Maxima

PARI

PARI

PARI

Formula

A105633 Row sums of triangle A105632.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A108626 Antidiagonal sums of square array A108625, in which row n equals the crystal ball sequence for A_n lattice.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

SageMath

Formula

A025242 Generalized Catalan numbers A(x)^2 -(1+x)^2*A(x) +x*(2+x+x^2) =0.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A114492 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n and having k DDUU's, where U=(1,1), D=(1,-1) (0<=k<=floor(n/2)-1 for n>=2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A120059 Triangle read by rows: T(n,k) is the number of Dyck n-paths (A000108) whose longest pyramid has size k.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

A082582 Expansion of (1 + x^2 - sqrt( 1 - 4x + 2x^2 + x^4)) / (2*x) in powers of x.

A025242 Generalized Catalan numbers A(x)^2 -(1+x)^2A(x) +x(2+x+x^2) =0.