A007297 -id:A007297 - cp's OEIS frontend

A361242 Number of nonequivalent noncrossing cacti with n nodes up to rotation.

1, 1, 1, 2, 7, 26, 144, 800, 4995, 32176, 215914, 1486270, 10471534, 75137664, 547756650, 4047212142, 30255934851, 228513227318, 1741572167716, 13380306774014, 103542814440878, 806476983310180, 6318519422577854, 49769050291536486, 393933908000862866

Offset: 0

Andrew Howroyd, Mar 07 2023

nonn

A noncrossing cactus is a connected noncrossing graph (A007297) that is a cactus graph (a tree of edges and polygons).

Since every cactus is an outerplanar graph, every cactus has at least one drawing as a noncrossing graph.

			The a(3) = 2 nonequivalent cacti have the following blocks:
   {{1,2}, {1,3}},
   {{1,2,3}}.
Graphically these can be represented:
        1           1
      /  \        /  \
     2    3      2----3
.
The a(4) = 7 nonequivalent cacti have the following blocks:
  {{1,2}, {1,3}, {1,4}},
  {{1,2}, {1,3}, {3,4}},
  {{1,2}, {1,4}, {2,3}},
  {{1,2}, {2,4}, {3,4}},
  {{1,2}, {1,3,4}},
  {{1,2}, {2,3,4}},
  {{1,2,3,4}}.
Graphically these can be represented:
   1---4    1   4    1---4    1   4
   | \      | \ |    |        | / |
   2   3    2   3    2---3    2   3
.
   1---4    1   4    1---4
   | \ |    | / |    |   |
   2   3    2---3    2---3

Andrew Howroyd, Table of n, a(n) for n = 0..500
Wikipedia, Cactus graph.
Index entries for sequences related to cacti.

Cf. A003168, A007297, A361236, A361243.

\\ Here F(n) is the g.f. of A003168.
F(n) = {1 + serreverse(x/((1+2*x)*(1+x)^2) + O(x*x^n))}
seq(n) = {my(f=F(n-1)); Vec(1 + intformal(f) - sum(d=2, n, eulerphi(d) * log(1-subst(x*f^2 + O(x^(n\d+1)),x,x^d)) / d), -n-1)}

A326331 Number of simple graphs covering the vertices {1..n} whose nesting edges are connected.

Original entry on oeis.org

1, 0, 1, 0, 1, 14, 539

Offset: 0

Gus Wiseman, Jun 27 2019

Covering means there are no isolated vertices. Two edges {a,b}, {c,d} are nesting if a < c < d < b or c < a < b < d. A graph has its nesting edges connected if the graph whose vertices are the edges and whose edges are nesting pairs of edges is connected.

Gus Wiseman, The a(5) = 14 simple nesting-connected covering graphs.

The non-covering case is the binomial transform A326330.
Covering graphs whose crossing edges are connected are A324327.
Cf. A006125, A007297, A054726, A099947, A117662, A136653, A324328.
Cf. A326210, A326293, A326335, A326336, A326337, A326338, A326339.

nesXQ[stn_]:=MatchQ[stn,{_,{x_,y_},_,{z_,t_},_}/;x0]&]},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[nestcmpts[#]]<=1&]],{n,0,5}]

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

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

Original entry on oeis.org

1, 1, 1, 1, 4, 9, 19, 42

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.

Gus Wiseman, The a(6) = 19 maximal non-crossing non-nesting graphs.

Covering graphs with no crossing or nesting edges are A326329.
The case with only crossing edges forbidden is A000108 shifted right twice.
Simple graphs without crossing or nesting edges are A326244.
Connected graphs with no crossing or nesting edges are A326339.
Cf. A006125, A007297, A054726, A117662, A136653.
Cf. A324169, A324327, A324328, A326279, A326293.

fasmax[y_]:=Complement[y,Union@@(Most[Subsets[#]]&/@y)];
Table[Length[fasmax[Select[Subsets[Subsets[Range[n],{2}]],!MatchQ[#,{_,{x_,y_},_,{z_,t_},_}/;x

A045741 Number of edges in all noncrossing connected graphs on n nodes on a circle.

Original entry on oeis.org

1, 9, 82, 765, 7266, 69930, 679764, 6659037, 65635570, 650194974, 6467730204, 64562259762, 646399361076, 6488447895540, 65276186864232, 657998685456093, 6644370824416530, 67198463606576790, 680568874690989900

Offset: 2

Emeric Deutsch

nonn

			a(3)=9; indeed, with vertices u, v, w, the noncrossing connected graphs are {uv,uw}, {vu, vw}, {wu, wv}, and {uv, vw, wu} with a total of 9 edges.

G. C. Greubel, Table of n, a(n) for n = 2..980
Sen-Peng Eu, Shu-Chung Liu and Yeong-Nan Yeh, On the congruences of some combinatorial numbers, Stud. Appl. Math. vol. 116 (2006) pp. 135-144
I. M. Gessel, A short proof of the Deutsch-Sagan congruence for connected non crossing graphs, arXiv preprint arXiv:1403.7656, 2014

Cf. A007297, A244038, A244039.

A045741 := proc(n) local k ; add(binomial(3*n-3,n+k)*binomial(k,n-1),k=0..2*n-3) ; end: seq(A045741(n),n=2..20) ; # R. J. Mathar, Feb 27 2008

Table[Sum[k*Binomial[3*n - 3, n + k]*Binomial[k - 1, k - n + 1], {k, n - 1, 2*n}]/(n - 1), {n,2,50}] (* G. C. Greubel, Jan 30 2017 *)

for(n=2,50, print1(sum(k=n-1,2*n, k*binomial(3*n-3,n+k)* binomial(k-1,k-n+1))/(n-1), ", ")) \\ G. C. Greubel, Jan 30 2017

a(n) = Sum_{k = n-1 .. 2*n} (k*binomial(3*n-3, n+k)*binomial(k-1, k-n+1))/(n-1).
a(n) = 1 mod 3 if n in A103457; a(n) = 0 mod 3 otherwise [Eu et al.]. - R. J. Mathar, Feb 27 2008
Recurrence: (n-2)*(n-1)*(6*n-17)*a(n) = 18*(n-2)*a(n-1) + 12*(3*n-8)*(3*n-7)*(6*n-11)*a(n-2). - Vaclav Kotesovec, Dec 29 2012
a(n) ~ (sqrt(3)-1)/sqrt(Pi) * (2^(n-5/2)*3^(3*n/2-3/2))/sqrt(n). - Vaclav Kotesovec, Dec 29 2012
A244038(n) = a(n) + A244039(n) [Gessel]. - N. J. A. Sloane, Jun 28 2014

A262737 O.g.f. exp( Sum_{n >= 1} A262732(n)*x^n/n ).

Original entry on oeis.org

1, 8, 95, 1336, 20642, 338640, 5791291, 102108760, 1842857390, 33879118384, 632210693270, 11944142806064, 228010741228740, 4391334026631072, 85221618348230355, 1664901954576830360, 32716286416687895862, 646228961799752926320, 12823701194384778672322

Offset: 0

Peter Bala, Sep 29 2015

O.g.f. is 1/x * the series reversion of x*(1 - x)^k/(1 + x)^(k+2) for k = 3. See the cross references for related sequences obtained from other values of k.

Peter Bala, Notes on logarithmic differentiation, the binomial transform and series reversion

Cf. A000108 (k = 0), A007297 (k = 1), A066357 (k = 2), A262738 (k = 4), A262739 (k = 5), A262740 (k = 6), A262732.

A262737 := proc (n) option remember; if n = 0 then 1 else add(1/k!*(5*k)!/GAMMA(5*k/2 + 1)*GAMMA(3*k/2 + 1)/(3*k)!*A262737(n-k), k = 1 .. n)/n end if; end proc:
seq(A262737(n), n = 0 .. 20);

a(n) = sum(k=0, n, binomial(5*(n+1),k)*binomial(4*(n+1)-k-2,(n+1)-k-1))/(n+1); \\ Altug Alkan, Oct 03 2015

a(n-1) = 1/n * Sum_{i = 0..n-1} binomial(5*n,i)*binomial(4*n-i-2,n-i-1).
O.g.f.: A(x) = exp ( Sum_{n >= 1} 1/n! * (5*n)!/(5*n/2)! * (3*n/2)!/(3*n)!*x^n/n ) = 1 + 8*x + 195*x^2 + 1336*x^3 + ....
1 + x*A'(x)/A(x) is the o.g.f. for A262732.
O.g.f. is the series reversion of x*(1 - x)^3/(1 + x)^5.
a(0) = 1 and for n >= 1, a(n) = 1/n * Sum {k = 1..n} 1/k!*(5*k)!/GAMMA(5*k/2+1)*GAMMA(3*k/2+1)/(3*k)! * a(n-k).

A262738 O.g.f. exp( Sum_{n >= 1} A211419(n)*x^n/n ).

Original entry on oeis.org

1, 10, 149, 2630, 51002, 1050132, 22539085, 498732014, 11296141454, 260613866380, 6103074997890, 144696786555580, 3466352150674324, 83776927644646952, 2040261954214847421, 50018542073019175806, 1233419779839067305350, 30572886836581693309020

Offset: 0

Peter Bala, Sep 29 2015

O.g.f. is 1/x * the series reversion of x*(1 - x)^k/(1 + x)^(k+2) at k = 4. See the cross references for related sequences obtained from other values of k.

Peter Bala, Notes on logarithmic differentiation, the binomial transform and series reversion

Cf. A211419, A000108 (k = 0), A007297 (k = 1), A066357 (k = 2), A262737 (k = 3), A262739 (k = 5), A262740 (k = 6).

A262738 := proc(n) option remember; if n = 0 then 1 else add((6*k)!*(2*k)!/((4*k)!*(3*k)!*k!)*A262738(n-k), k = 1 .. n)/n end if; end proc:
seq(A262738(n), n = 0..20);

a(n) = sum(k=0, n, binomial(6*(n+1),k)*binomial(5*(n+1)-k-2,(n+1)-k-1))/(n+1); \\ Altug Alkan, Oct 03 2015

a(n-1) = 1/n * Sum_{i = 0..n-1} binomial(6*n,i)*binomial(5*n-i-2,n-i-1).
O.g.f.: A(x) = exp ( Sum_{n >= 1} (6*n)!*(2*n)!/((4*n)!*(3*n)!*n!)*x^n/n ) = 1 + 10*x + 149*x^2 + 2630*x^3 + ....
1 + x*A'(x)/A(x) is the o.g.f. for A211419.
O.g.f. is the series reversion of x*(1 - x)^4/(1 + x)^6.
a(0) = 1 and for n >= 1, a(n) = 1/n * Sum {k = 1..n} (6*k)!*(2*k)!/((4*k)!*(3*k)!*k!)*a(n-k).

A262739 O.g.f. exp( Sum_{n >= 1} A262733(n)*x^n/n ).

Original entry on oeis.org

1, 12, 215, 4564, 106442, 2635704, 68031147, 1810302340, 49308457334, 1368019979976, 38525145673126, 1098380420669000, 31641932951483220, 919622628946689648, 26931762975278938035, 793967020231145502564, 23543663463050594677310, 701763102761640853890600, 21014048069544552257072530, 631868353403527700756671320, 19070677448561228207945931276

Offset: 0

Peter Bala, Sep 29 2015

O.g.f. is 1/x * the series reversion of x*(1 - x)^k/(1 + x)^(k+2) when k = 5. See the cross references for related sequences obtained from other values of k.

Peter Bala, Notes on logarithmic differentiation, the binomial transform and series reversion

Cf. A262733, A211419, A000108 (k = 0), A007297 (k = 1), A066357 (k = 2), A262737 (k = 3), A262738 (k = 4), A262740 (k = 6).

A262739 := proc (n) option remember; if n = 0 then 1 else add(1/k!*(7*k)!/GAMMA(7*k/2 + 1)*GAMMA(5*k/2 + 1)/(5*k)!*A262739(n-k), k = 1 .. n)/n end if; end proc:
seq(A262739(n), n = 0..20);

a(n) = sum(k=0, n, binomial(7*(n+1),k)*binomial(6*(n+1)-k-2,(n+1)-k-1))/(n+1); \\ Altug Alkan, Oct 03 2015

a(n-1) = 1/n * Sum_{i = 0..n-1} binomial(7*n,i)*binomial(6*n-i-2,n-i-1).
O.g.f.: A(x) = exp ( Sum_{n >= 1} 1/n! * (7*n)!/(7*n/2)! * (5*n/2)!/(5*n)!*x^n/n ) = 1 + 12*x + 215*x^2 + 4564*x^3 + ....
1 + x*A'(x)/A(x) is the o.g.f. for A262733.
O.g.f. is the series reversion of x*(1 - x)^5/(1 + x)^7,
a(0) = 1 and for n >= 1, a(n) = 1/n * Sum {k = 1..n} 1/k! * (7*k)!/(7*k/2)! * (5*k/2)!/(5*k)!*a(n-k).

A262740 O.g.f. exp( Sum_{n >= 1} A211421(n)*x^n/n ).

Original entry on oeis.org

1, 14, 293, 7266, 197962, 5726364, 172662765, 5367187226, 170772853790, 5534640052292, 182070248073826, 6063785526898644, 204055962203476788, 6927718839334775608, 236994877398511998717, 8161492483543100398410, 282705062046649346154006, 9843330120848835962213940

Offset: 0

Peter Bala, Sep 29 2015

O.g.f. is 1/x * the series reversion of x*(1 - x)^k/(1 + x)^(k+2) at k = 6. See the cross references for related sequences obtained from other values of k.

Peter Bala, Notes on logarithmic differentiation, the binomial transform and series reversion

Cf. A211421, A000108 (k = 0), A007297 (k = 1), A066357 (k = 2), A262737 (k = 3), A262738 (k = 4), A262739 (k = 5).

#A262740
A262740 := proc (n) option remember; if n = 0 then 1 else add(1/k!*(8*k)!/(4*k)!*(3*k)!/(6*k)!*A262740(n-k), k = 1 .. n)/n end if; end proc:
seq(A262740(n), n = 0..17);

a(n) = sum(k=0, n, binomial(8*(n+1),k)*binomial(7*(n+1)-k-2,(n+1)-k-1))/(n+1); \\ Altug Alkan, Oct 03 2015

a(n-1) = 1/n * Sum_{i = 0..n-1} binomial(8*n,i)*binomial(7*n-i-2,n-i-1).
O.g.f.: A(x) = exp ( Sum_{n >= 1} 1/n! * (8*n)!/(4*n)! * (3*n)!/(6*n)!*x^n/n ) = 1 + 14*x + 293*x^2 + 7266*x^3 + ....
1 + x*A'(x)/A(x) is the o.g.f. for A211421.
O.g.f. is the series reversion of x*(1 - x)^6/(1 + x)^8.
a(0) = 1 and for n >= 1, a(n) = 1/n * Sum {k = 1..n} 1/k! * (8*k)!/(4*k)! * (3*k)!/(6*k)!*a(n-k).

A065065 Number of noncrossing connected graphs with nodes on a circle having n edges.

Original entry on oeis.org

1, 3, 13, 64, 341, 1913, 11132, 66573, 406653, 2526351, 15913347, 101396034, 652378120, 4232439734, 27657380019, 181872596607, 1202641671293, 7991878198287, 53343146808137, 357464739709920, 2404073823950915

Offset: 1

Emeric Deutsch, Nov 06 2001

nonn

			a(3)=13 because we have 1 triangle on 3 nodes and 12 non-crossing trees on 4 nodes.

Andrew Howroyd, Table of n, a(n) for n = 1..200
P. Flajolet and M. Noy, Analytic combinatorics of non-crossing configurations, Discrete Math., 204, 203-229, 1999.

Cf. A007297, A127537.

A065065 := n-> sum(binomial(3*k-3,n+k)*binomial(n-1,n-k+1)/(k-1),k=ceil((n+3)/2)..n+1);

terms = 21;
A[_] = 0;
Do[A[x_] = x (1 + 3 A[x] + 4 A[x]^2 + A[x]^3) + O[x]^(terms+1), {terms+1}];
CoefficientList[A[x]/x, x] (* Jean-François Alcover, Jul 29 2018, after Vladimir Kruchinin *)

a(n)=sum(k=ceil((n+3)/2), n+1, binomial(3*k-3,n+k)*binomial(n-1,n-k+1)/(k-1)); \\ Andrew Howroyd, Nov 12 2017

Vec(serreverse(x/(1+3*x+4*x^2+x^3) + O(x^20))) \\ Andrew Howroyd, Nov 12 2017

a(n) = Sum_{k=ceiling((n+3)/2)..n+1} binomial(3*k-3,n+k)*binomial(n-1,n-k+1)/(k-1).
G.f. satisfies: A(x) = x*(1+3*A(x)+4*A(x)^2+A(x)^3). - Vladimir Kruchinin, Nov 12 2014
a(n) = Sum_{m=n..2*n-2} A127537(m,n). - Andrew Howroyd, Nov 12 2017
D-finite with recurrence 8*n*(2*n+1)*a(n) +2*(-46*n^2+55*n-18)*a(n-1) +6*(-30*n^2+60*n-7)*a(n-2) +2*(n-3)*(28*n-163)*a(n-3) +93*(n-3)*(n-4)*a(n-4)=0. - R. J. Mathar, Jul 26 2022

cp's OEIS Frontend

A361242 Number of nonequivalent noncrossing cacti with n nodes up to rotation.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A326331 Number of simple graphs covering the vertices {1..n} whose nesting edges are connected.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

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

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A045741 Number of edges in all noncrossing connected graphs on n nodes on a circle.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A262737 O.g.f. exp( Sum_{n >= 1} A262732(n)*x^n/n ).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

PARI

Formula

A262738 O.g.f. exp( Sum_{n >= 1} A211419(n)*x^n/n ).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

PARI

Formula

A262739 O.g.f. exp( Sum_{n >= 1} A262733(n)*x^n/n ).

Views

Author

Keywords

Comments

Links

Crossrefs