A025242 -id:A025242 - 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

A086581 Number of Dyck paths of semilength n with no DDUU.

Original entry on oeis.org

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

Michael Somos, Jul 22 2003

nonn

See A025242 for a bijection between paths avoiding UUDD versus DDUU.
Number of lattice paths, never going below the x-axis, from (0,0) to (n,0) consisting of up steps U(k) = (k,1) for every positive integer k, down steps D = (1,-1) and horizontal steps H. - José Luis Ramírez Ramírez, Apr 19 2015
Given a sequence variant with 0 inserted between the two 1's, the INVERT transform of the modified sequence is this sequence. - Gary W. Adamson, Jun 28 2015

			a(4) = 13 because of the 14 Dyck 4-paths only UUDDUUDD contains DDUU.

Robert Israel, Table of n, a(n) for n = 0..1709
Paul Barry, Continued fractions and transformations of integer sequences, JIS 12 (2009) 09.7.6.
Paul Barry, Generalized Catalan recurrences, Riordan arrays, elliptic curves, and orthogonal polynomials, arXiv:1910.00875 [math.CO], 2019.
Lu, Qing Lin Skew Motzkin paths Acta Math. Sin., Engl. Ser. 33, No. 5, 657-667 (2017) sequence s_n
T. Mansour, Restricted 1-3-2 permutations and generalized patterns, arXiv:math/0110039 [math.CO], 2001.
T. Mansour, Restricted 1-3-2 permutations and generalized patterns, Annals of Combin., 6 (2002), 65-76. (Example 2.10.)
L. Pudwell, Pattern avoidance in trees (slides from a talk, mentions many sequences), 2012. - From _N. J. A. Sloane_, Jan 03 2013
A. Sapounakis, I. Tasoulas and P. Tsikouras, On the Dominance Partial Ordering of Dyck Paths, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.5.
A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.
Murray Tannock, Equivalence classes of mesh patterns with a dominating pattern, MSc Thesis, Reykjavik Univ., May 2016.

Cf. A025242, A082582.

Column k=0 of A114492.

F:= gfun:-rectoproc({(n+2)*a(n) +(n+3)*a(n-1) +2*(-9*n+4)*a(n-2) +10*(n-2)*a(n-3) +(n-4)*a(n-4) +5*(n-5)*a(n-5)=0, seq(a(n)=[1,1,2,5,13][n+1],n=0..4)},a(n),remember):
map(F, [$0..30]); # Robert Israel, Jun 29 2015

CoefficientList[ Series[(1 - 2 x + x^2 - Sqrt[1 - 4 x + 2 x^2 + x^4])/(2 x^2), {x, 0, 27}], x] (* Robert G. Wilson v, Mar 25 2011 *)

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

a(n)=1+sum(k=0,n,sum(i=0,k,binomial(n-1,k)*binomial(2*i+2,i)*binomial(i+2,k-2*i-1)/(i+1))) \\ Thomas Baruchel, Jan 19 2015

G.f. A(x) satisfies the equation 0 = 1 - x - (1 - x)^2 * A(x) + (x * A(x))^2.
a(n) = A025242(n+1) = A082582(n+1).
G.f.: (1 - 2*x + x^2 - sqrt(1 - 4*x + 2*x^2 + x^4))  /(2 * x^2).
a(n+2) - 2*a(n+1) + a(n) = a(0)*a(n) + a(1)*a(n-1) + ... + a(n)*a(0).
G.f.: (1/(1-x))*c(x^2/(1-x)^3), c(x) the g.f. of A000108; a(n)=sum{k=0..floor(n/2), C(n+k,3k)*A000108(k)}. - Paul Barry, May 31 2006
Conjecture: (n+2)*a(n) +(n+3)*a(n-1) +2*(-9*n+4)*a(n-2) +10*(n-2)*a(n-3) +(n-4)*a(n-4) +5*(n-5)*a(n-5)=0. - R. J. Mathar, Nov 26 2012
G.f. satisfies (10*x^3-28*x^2+4*x+2)*A(x) + (5*x^6+x^5+10*x^4-18*x^3+x^2+x)*A'(x) = 5*x^4+x^3-15*x^2+7*x+2. This confirms R. J. Mathar's recurrence equation. - Robert Israel, Jun 29 2015
G.f.: 1 - 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
G.f.: 1/G(0) where G(k) = 1 - q/(1 - q - q^2 / G(k+1) ); (continued fraction). - Joerg Arndt, Feb 27 2014
From Thomas Baruchel, Jan 19 2015: (Start)
a(n) = 1+Sum_{k=0..n} Sum_{i=0..k} C(n-1,k)*C(2i+2,i)*C(i+2,k-2i-1)/(i+1).
a(n) = Sum_{k=0..n} C(2k,k)*C(n+k,3k)/(k+1).
Sum_{k=0..n} a(k+1)*A108626(n-k) = 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). (End)

Name corrected by David Scambler, Mar 28 2011

A098978 Triangle read by rows: T(n,k) is number of Dyck n-paths with k UUDDs, 0 <= k <= n/2.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 5, 8, 1, 13, 23, 6, 35, 69, 27, 1, 97, 212, 110, 10, 275, 662, 426, 66, 1, 794, 2091, 1602, 360, 15, 2327, 6661, 5912, 1760, 135, 1, 6905, 21359, 21534, 8022, 945, 21, 20705, 68850, 77685, 34840, 5685, 246, 1, 62642, 222892, 278192, 146092

Offset: 0

David Callan, Oct 24 2004

T(n,k) is the number of Łukasiewicz paths of length n having k peaks. A Łukasiewicz path of length n is a path in the first quadrant from (0,0) to (n,0) using rise steps (1,k) for any positive integer k, level steps (1,0) and fall steps (1,-1). Example: T(3,1)=3 because we have HUD, UDH and U(2)DD, where H=(1,0), U(1,1), U(2)=(1,2) and D=(1,-1). (see R. P. Stanley reference). - Emeric Deutsch, Jan 06 2005

			Table begins
\ k  0,   1,   2, ...
n
0 |  1;
1 |  1;
2 |  1,   1;
3 |  2,   3;
4 |  5,   8,   1;
5 | 13,  23,   6;
6 | 35,  69,  27,  1;
7 | 97, 212, 110, 10;
8 |275, 662, 426, 66, 1;
T(3,1) = 3 because each of UUUDDD, UDUUDD, UUDDUD has one UUDD.

R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge Univ. Press, Cambridge, 1999, p. 223, Exercise 6.19w; the integers are the slopes of the steps. - Emeric Deutsch, Jan 06 2005

Alois P. Heinz, Rows n = 0..200, flattened
Marilena Barnabei, Flavio Bonetti, and Niccolò Castronuovo, Motzkin and Catalan Tunnel Polynomials, J. Int. Seq., Vol. 21 (2018), Article 18.8.8.
A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924. - From _N. J. A. Sloane_, May 05 2012
Index entries for sequences related to Łukasiewicz

Column k=0 is A025242 (apart from first term).

Cf. A243752.

b:= proc(x, y, t) option remember; `if`(y<0 or y>x, 0,
     `if`(x=0, 1, expand(b(x-1, y+1, [2, 3, 3, 2][t])
      +b(x-1, y-1, [1, 1, 4, 1][t])*`if`(t=4, z, 1))))
    end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(2*n, 0, 1)):
seq(T(n), n=0..15);  # Alois P. Heinz, Jun 10 2014

T[n_, k_] := Binomial[n-k, k] Binomial[2n-3k, n-k-1] HypergeometricPFQ[{k -n/2-1/2, k-n/2, k-n/2, k-n/2+1/2}, {k-2n/3, k-2n/3+1/3, k-2n/3+2/3}, 16/27]/(n-k); T[0, 0] = 1; Flatten[Table[T[n, k], {n, 0, 15}, {k, 0, n/2}]] (* Jean-François Alcover, Dec 21 2016, after 2nd formula *)

G.f.: (1 + z^2 - t*z^2 - (-4*z + (-1 - z^2 + t*z^2)^2)^(1/2))/(2*z) = Sum_{n>=0, 0<=k<=n/2} T(n, k)z^n*t^k and it satisfies G = 1 + G^2*z + G*(-z^2 + t*z^2).

T(n,k) = Sum_{j=0..floor(n/2)-k} (-1)^j * binomial(n-(j+k), j+k) * binomial(2n-3(j+k), n-(j+k)-1) * binomial(j+k, k)/(n-(j+k)). - I. Tasoulas (jtas(AT)unipi.gr), Feb 19 2006

The vincular pattern 23-1-4 requires the 2 and the 3 to be adjacent.

By the trivial Wilf equivalence obtained by reversing the permutations, a(n) is also the number of cyclic patterns of length n that avoid the vincular pattern 32-4-1.

The vincular pattern 23-4-1 requires the 2 and the 3 to be adjacent.

By the trivial Wilf equivalence obtained by reversing the permutations, a(n) is also the number of cyclic patterns of length n that avoid the vincular pattern 32-1-4.

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

A086581 Number of Dyck paths of semilength n with no DDUU.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A098978 Triangle read by rows: T(n,k) is number of Dyck n-paths with k UUDDs, 0 <= k <= n/2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A346660 Number of cyclic patterns of length n that avoid the vincular pattern 23-1-4.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A346661 Number of cyclic patterns of length n that avoid the vincular pattern 23-4-1.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

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