A082582 Expansion of (1 + x^2 - sqrt( 1 - 4*x + 2*x^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

Author

Emanuele Munarini, May 07 2003

Keywords

• easy
• nonn

Comments

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

Examples

			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
		

Links

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

Crossrefs

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.

Programs

Haskell

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

Maple

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

Mathematica

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

Maxima

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

PARI

{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 */

PARI

{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 */

PARI

{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 */

Formula

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