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

A326339 Number of connected simple graphs with vertices {1..n} and no crossing or nesting edges.

Original entry on oeis.org

1, 0, 1, 4, 12, 36, 108, 324

Offset: 0

Gus Wiseman, Jun 29 2019

Two edges {a,b}, {c,d} are crossing if a < c < b < d or c < a < d < b, and nesting if a < c < d < b or c < a < b < d.

Appears to be essentially the same as A003946.

			The a(2) = 1 through a(4) = 36 edge-sets:
  {12}  {12,13}     {12,13,14}
        {12,23}     {12,13,34}
        {13,23}     {12,14,34}
        {12,13,23}  {12,23,24}
                    {12,23,34}
                    {12,24,34}
                    {13,23,34}
                    {14,24,34}
                    {12,13,14,34}
                    {12,13,23,34}
                    {12,14,24,34}
                    {12,23,24,34}

Gus Wiseman, The a(5) = 36 connected graphs with no crossing or nesting edges.
Gus Wiseman, The a(6) = 108 connected graphs with no crossing or nesting edges.

Covering graphs with no crossing or nesting edges are A326329.
Connected simple graphs are A001349.
The case with only crossing edges forbidden is A007297.
Graphs without crossing or nesting edges are A326244.
Cf. A006125, A054726, A117662, A136653.
Cf. A324169, A326210, A326293, A326340.

csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&Length[csm[#]]<=1&&!MatchQ[#,{_,{x_,y_},_,{z_,t_},_}/;x

A326294 Number of connected simple graphs on a subset of {1..n} with no crossing or nesting edges.

Original entry on oeis.org

1, 1, 2, 8, 35, 147, 600, 2418

Offset: 0

Gus Wiseman, Jun 29 2019

Two edges {a,b}, {c,d} are crossing if a < c < b < d or c < a < d < b, and nesting if a < c < d < b or c < a < b < d.

			The a(4) = 35 edge-sets:
  {}  {12}  {12,13}  {12,13,14}  {12,13,14,34}
      {13}  {12,14}  {12,13,23}  {12,13,23,34}
      {14}  {12,23}  {12,13,34}  {12,14,24,34}
      {23}  {12,24}  {12,14,24}  {12,23,24,34}
      {24}  {13,14}  {12,14,34}
      {34}  {13,23}  {12,23,24}
            {13,34}  {12,23,34}
            {14,24}  {12,24,34}
            {14,34}  {13,14,34}
            {23,24}  {13,23,34}
            {23,34}  {14,24,34}
            {24,34}  {23,24,34}

Eric Marberg, Crossings and nestings in colored set partitions, arXiv preprint arXiv:1203.5738 [math.CO], 2012.

The inverse binomial transform is the covering case A326339.
Covering graphs with no crossing or nesting edges are A326329.
Connected simple graphs are A001349.
Graphs without crossing or nesting edges are A326244.
Cf. A006125, A054726, A117662, A136653.
Cf. A324169, A326210, A326293, A326340.

csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Length[csm[#]]<=1&&!MatchQ[#,{_,{x_,y_},_,{z_,t_},_}/;x

Conjecture: a(n) = A052161(n - 2) + 1.

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

A326339 Number of connected simple graphs with vertices {1..n} and no crossing or nesting edges.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A326294 Number of connected simple graphs on a subset of {1..n} with no crossing or nesting edges.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A326350 Number of non-nesting connected simple graphs with vertices {1..n}.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A326351 Number of non-nesting connected simple graphs on a subset of {1..n}.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

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