A007297 -id:A007297 - cp's OEIS frontend

A089436 Number of non-crossing connected graphs on n nodes on a circle in which a fixed (distinguished) node has degree one.

1, 2, 9, 54, 374, 2820, 22485, 186494, 1592778, 13914108, 123750874, 1116809628, 10201516332, 94140605832, 876332565837, 8219124900558, 77594375595266, 736785675010380, 7031930543228910, 67420537625021460, 649070964647075700

Offset: 2

Emeric Deutsch, Dec 28 2003

nonn

Convolution of (1, A007297) with itself.

			a(3)=2 because among the four non-crossing graphs on the points A,B,C, the distinguished node A has degree equal to 1 only in the graphs {AB,BC} and {AC,BC}; in the other two graphs ({AB,AC} and {AB,BC,AC}) the node A has degree 2.

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

Column k=1 of A143022.

Cf. A007297.

terms = 21;
g[x_] = 0;
Do[g[x_] = g[x]^2 + x (1 + g[x])^3 + O[x]^(terms+2), {terms+2}];
Drop[CoefficientList[(x + x g[x])^2 + O[x]^(terms+2), x], 2] (* Jean-François Alcover, Oct 05 2011, updated Jul 29 2018 after Andrew Howroyd *)

a(n)=if(n<3, n==2, sum(k=2, 2*n-4, 2*binomial(k-2, n-3)*binomial(3*n-5, 2*n-k-4))/(n-2)); \\ Andrew Howroyd, Nov 12 2017

Vec((x+x*serreverse((x-x^2)/(1+x)^3 + O(x^25)))^2) \\ Andrew Howroyd, Nov 13 2017

a(n) = Sum_{k=2..2*n-4} 2*binomial(k-2, n-3)*binomial(3*n-5, 2*n-k-4)/(n-2) for n > 2. - Andrew Howroyd, Nov 12 2017
G.f.: g^2, where g satisfies g^3+g^2-3zg+2z^2=0, g(0)=0, or, in Maple notation, g := -1/3+(2/3)*sqrt(1+9*z)*sin((1/3)*arcsin((2+27*z+54*z^2)/2/(1+9*z)^(3/2))).
G.f.: (x+x*g)^2 where g satisfies g - g^2 = x*(1 + g)^3. - Andrew Howroyd, Nov 13 2017
a(n) ~ 2^(n-1) * 3^(3*n/2-9/4) / (sqrt(Pi)*n^(3/2)*sqrt(45+26*sqrt(3))). - Vaclav Kotesovec, Mar 17 2014
D-finite with recurrence n*(2*n-3)*(n-2)*a(n) +6*(9*n-10)*a(n-1) -12*(3*n-10)*(3*n-8)*(2*n-1)*a(n-2)=0. - R. J. Mathar, May 10 2018

A365842 Expansion of (1/x) * Series_Reversion( x*(1-x)^2/(1+x)^3 ).

Original entry on oeis.org

1, 5, 37, 325, 3141, 32261, 345605, 3818501, 43197445, 497868805, 5825331205, 69013667845, 826213203973, 9979713945605, 121472752156677, 1488482728148997, 18346810389299205, 227319830355640325, 2829629321065267205, 35369618935665131525, 443775430273133445125

Offset: 0

Seiichi Manyama, Sep 20 2023

nonn

Cf. A007297, A365843, A365844, A365845.

a(n) = sum(k=0, n, binomial(2*n+k+1, k)*binomial(3*(n+1), n-k))/(n+1);

a(n) = (1/(n+1)) * Sum_{k=0..n} binomial(2*n+k+1,k) * binomial(3*(n+1),n-k).

a(n) = (1/(n+1)) * [x^n] ( (1+x)^3 / (1-x)^2 )^(n+1). - Seiichi Manyama, Feb 17 2024

A143018 Triangle read by rows: T(n,k) (n >= 2, k >= 1) is the number of non-crossing connected graphs on n nodes on a circle such that the distance from a fixed node (root) to the next node is k. Rows are indexed 2,3,4,...; columns are indexed 1,2,3, ... .

Original entry on oeis.org

1, 3, 1, 16, 6, 1, 105, 41, 9, 1, 768, 306, 75, 12, 1, 6006, 2422, 630, 118, 15, 1, 49152, 19980, 5394, 1104, 170, 18, 1, 415701, 169941, 47061, 10197, 1755, 231, 21, 1, 3604480, 1479786, 417439, 94116, 17425, 2610, 301, 24, 1

Offset: 2

Emeric Deutsch, Jul 30 2008

Row sums yield A007297.
T(n,1) = A085614(n-1).
Sum_{k=1..n-1} k*T(n,k) = A143020(n).

			T(3,1)=3 and T(3,2)=1 because in the graphs (AB,BC,CA), (AB,AC), (AB,BC) and (AC,BC) the distances from A to B are 1, 1, 1 and 2, respectively.
Triangle starts:
    1;
    3,   1;
   16,   6,  1;
  105,  41,  9,  1;
  768, 306, 75, 12, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 2..1276
P. Flajolet and M. Noy, Analytic combinatorics of noncrossing configurations, Discrete Math. 204 (1999), 203-229.

Cf. A085614, A143020, A007297.

L:=proc(p,q,r) options operator, arrow: sum(binomial(q, i)*binomial(r+p-1-i, r-1), i=0..min(p,q)) end proc: T:=proc(n,k) options operator, arrow: k*L(n-k-1, 3*n-k-4, n-1)/(n-1) end proc: for n from 2 to 10 do seq(T(n,k),k=1..n-1) end do; # yields sequence in triangular form

t[n_, k_] := k*L[n - k - 1, 3*n - k - 4, n-1]/(n-1); L[p_, q_, r_] := Sum[ Binomial[q, i]*Binomial[r + p - 1 - i, r-1], {i, 0, Min[p, q]}]; Flatten[ Table[ t[n, k], {n, 2, 10}, {k, 1, n-1}]] (* Jean-François Alcover, Oct 05 2011, Oct 05 2011, after Maple *)

T(n,k)=k*sum(i=0, min(n-k-1, 3*n-k-4), binomial(3*n-k-4, i)*binomial(2*n-k-i-3, n-2))/(n-1);
for(n=2, 10, for(k=1, n-1, print1(T(n, k), ", ")); print); \\ Andrew Howroyd, Nov 17 2017

T(n,k) = k*L(n-k-1, 3n-k-4, n-1)/(n-1) (n >= 2, 1 <= k <= n-1), where L(p,q,r) = [u^p](1+u)^q/(1-u)^r = Sum_{i=0..min(p,q)} binomial(q,i)*binomial(r+p-1-i, r-1).
G.f.: G(t,z) = zg/[g - t*(g - z)], where g=g(z), the g.f. for the number of non-crossing connected graphs on n nodes on a circle, satisfies g^3 + g^2 - 3z*g + 2*z^2 = 0 (A007297).
T(n,k) = k*Sum_{i=0..min(n-k-1, 3*n-k-4)} binomial(3*n-k-4, i)*binomial(2*n-k-i-3, n-2)/(n-1). - Andrew Howroyd, Nov 17 2017

A143022 Triangle read by rows: T(n,k) is the number of non-crossing connected graphs on n nodes on a circle in which the root (a distinguished node) has degree k (n >= 2, 1 <= k <= n-1).

Original entry on oeis.org

1, 2, 2, 9, 10, 4, 54, 62, 32, 8, 374, 436, 248, 88, 16, 2820, 3316, 1984, 816, 224, 32, 22485, 26586, 16404, 7320, 2416, 544, 64, 186494, 221350, 139424, 65512, 24032, 6688, 1280, 128, 1592778, 1895740, 1211848, 590040, 231824, 73088, 17664, 2944

Offset: 2

Emeric Deutsch, Jul 30 2008

Row sums yield A007297.
T(n,1) = A089436(n).
Sum_{k=1..n-1} k*T(n,k) = A143023.

			T(3,1)=2, T(3,2)=2 because in the graphs (AB,BC,CA), (AB,AC), (AB,BC) and (AC,BC) the node A has degrees 2, 2, 1 and 1, respectively.
Triangle starts:
     1;
     2,    2;
     9,   10,    4;
    54,   62,   32,   8;
   374,  436,  248,  88,  16;
  2820, 3316, 1984, 816, 224, 32;

Andrew Howroyd, Table of n, a(n) for n = 2..1276
P. Flajolet and M. Noy, Analytic Combinatorics of Noncrossing Configurations, Discr. Math. 204 (1999), 203-229.

Cf. A007297, A089436, A143023.

L:=proc(p,q,r) options operator, arrow: sum(binomial(q, i)*binomial(r+p-1-i, r-1), i=0..min(p, q)) end proc: T:=proc(n,k) options operator, arrow: 2^(k-1)*(k*L(n-k-1,3*n-k-4,n-2)-L(n-k-2,3*n-k-3,n-1))/(n-1) end proc: for n from 2 to 10 do seq(T(n,k),k=1..n-1) end do; # yields sequence in triangular form

L[p_, q_, r_] := Sum[Binomial[q, i]*Binomial[r + p - 1 - i, r-1], {i, 0, Min[p, q]}]; t[n_, k_] := 2^(k-1)*(k*L[n - k - 1, 3*n - k - 4, n - 2] - L[n - k - 2, 3*n - k - 3, n-1])/(n-1); t[2, 1] = 1; Flatten[ Table[t[n, k], {n, 2, 10}, {k, 1, n-1}]] (* Jean-François Alcover, Oct 05 2011, after Maple *)

L(p,q,r)={sum(i=0, min(p,q), binomial(q,i)*binomial(r+p-1-i,r-1))}
T(n,k)={if(n<3, n==2&&k==1, 2^(k-1)*(k*L(n-k-1, 3*n-k-4, n-2) - L(n-k-2, 3*n-k-3, n-1))/(n-1))}
for(n=2, 10, for(k=1, n-1, print1(T(n, k), ", ")); print); \\ Andrew Howroyd, Nov 17 2017

S(n)={my(g=x+x*serreverse((x-x^2)/(1+x)^3 + O(x^n))); Vec(g*(x - y*(g-x))/(g - 2*y*(g - x)))}
my(v=S(10)); for(n=2, #v, my(p=v[n]); for(k=1, n-1, print1(polcoeff(p,k), ", ")); print) \\ Andrew Howroyd, Nov 17 2017

T(n,k) = 2^(k-1)*(k*L(n-k-1, 3*n-k-4, n-2) - L(n-k-2, 3*n-k-3, n-1))/(n-1) (n >= 2, 1 <= k <= n-1), where L(p,q,r) = [u^p](1+u)^q/(1-u)^r = Sum_{i=0..min(p,q)} binomial(q,i)*binomial(r+p-1-i, r-1).

G.f.: G(t,z) = g*(z - t*(g-z))/(g - 2*t*(g-z)), where g=g(z), the g.f. for the number of non-crossing connected graphs on n nodes on a circle, satisfies g^3 + g^2 - 3*z*g + 2*z^2 = 0 (A007297).

A326341 Number of minimal topologically connected chord graphs covering {1..n}.

Original entry on oeis.org

1, 0, 1, 0, 1, 5, 22, 119

Offset: 0

Gus Wiseman, Jun 29 2019

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

			The a(4) = 1 through a(6) = 22 edge-sets:
  {13,24}  {13,14,25}  {13,25,46}
           {13,24,25}  {14,25,36}
           {13,24,35}  {14,26,35}
           {14,24,35}  {15,24,36}
           {14,25,35}  {13,14,15,26}
                       {13,14,25,26}
                       {13,15,24,26}
                       {13,15,26,46}
                       {13,24,25,26}
                       {13,24,25,36}
                       {13,24,26,35}
                       {13,24,35,36}
                       {13,24,35,46}
                       {14,15,26,36}
                       {14,24,35,36}
                       {14,24,35,46}
                       {14,25,35,46}
                       {15,24,35,46}
                       {15,25,35,46}
                       {15,25,36,46}
                       {15,26,35,46}
                       {15,26,36,46}

The non-minimal case is A324327.
Minimal covers are A053530.
Topologically connected graphs are A324327 (covering) or A324328 (all).
Cf. A000108, A006125, A007297, A054726, A136653, A324169, A326210, A326293.

croXQ[stn_]:=MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;x0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
crosscmpts[stn_]:=csm[Union[Subsets[stn,{1}],Select[Subsets[stn,{2}],croXQ]]];
Table[Length[fasmin[Select[Subsets[Subsets[Range[n],{2}]],And[Union@@#==Range[n],Length[crosscmpts[#]]<=1]&]]],{n,0,5}]

A361243 Number of nonequivalent noncrossing cacti with n nodes up to rotation and reflection.

Original entry on oeis.org

1, 1, 1, 2, 5, 17, 79, 421, 2537, 16214, 108204, 743953, 5237414, 37574426, 273889801, 2023645764, 15128049989, 114256903169, 870786692493, 6690155544157, 51771411793812, 403238508004050, 3159259746188665, 24884525271410389, 196966954270163612

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

			The a(4) = 5 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}, {1,3,4}},
  {{1,2,3,4}}.
Graphically these can be represented:
   1---4    1   4    1---4    1---4    1---4
   | \      | \ |    |        | \ |    |   |
   2   3    2   3    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, A361239, A361242.

\\ 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/(1 - x*subst(f + O(x^(n\2+1)), x, x^2)) + 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)/2}

A365844 Expansion of (1/x) * Series_Reversion( x*(1-x)^4/(1+x)^3 ).

Original entry on oeis.org

1, 7, 74, 931, 12894, 189798, 2913980, 46140347, 748022678, 12354604274, 207148525484, 3516699607022, 60328735646620, 1044182053141612, 18212018061261600, 319771572646888811, 5647677332549552870, 100266714048150595770, 1788366334642393259292

Offset: 0

Seiichi Manyama, Sep 20 2023

nonn

Cf. A007297, A365842, A365843, A365845.

a(n) = sum(k=0, n, binomial(4*n+k+3, k)*binomial(3*(n+1), n-k))/(n+1);

a(n) = (1/(n+1)) * Sum_{k=0..n} binomial(4*n+k+3,k) * binomial(3*(n+1),n-k).

A365845 Expansion of (1/x) * Series_Reversion( x*(1-x)^5/(1+x)^3 ).

Original entry on oeis.org

1, 8, 97, 1400, 22243, 375584, 6614508, 120136984, 2234022775, 42322629960, 813939319697, 15849232257824, 311858145053076, 6191083938051840, 123852349440862504, 2494251111318893400, 50526944132627936127, 1028872756710478785560

Offset: 0

Seiichi Manyama, Sep 20 2023

nonn

Cf. A007297, A365842, A365843, A365844.

a(n) = sum(k=0, n, binomial(5*n+k+4, k)*binomial(3*(n+1), n-k))/(n+1);

a(n) = (1/(n+1)) * Sum_{k=0..n} binomial(5*n+k+4,k) * binomial(3*(n+1),n-k).

A089433 Number of noncrossing connected graphs on n nodes having exactly two interior faces.

Original entry on oeis.org

2, 30, 315, 2856, 23940, 191268, 1480050, 11196900, 83304936, 611931320, 4450217772, 32104210320, 230080173960, 1639890119016, 11634355574100, 82216112723640, 579022013389050, 4065827626164150, 28475852003986695

Offset: 4

Emeric Deutsch, Dec 28 2003

nonn

			a(4)=2 because the only connected graphs on the nodes A,B,C,D having exactly two interior faces are {AB,BC,CD,DA,AC} and {AB,BC,CD,DA,BD}.

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

Column k=2 of A089434.

Cf. A007297.

a(n) = n*binomial(3*n-3, n-4)/2; \\ Michel Marcus, Oct 26 2015

a(n) = n*binomial(3n-3, n-4)/2.

D-finite with recurrence -2*(2*n+1)*(n-4)*a(n) +3*(3*n-4)*(3*n-5)*a(n-1)=0. - R. J. Mathar, Jul 26 2022

A089435 Triangle read by rows: T(n,k) (n >= 2, k >= 0) is the number of non-crossing connected graphs on n nodes on a circle, having k triangles. Rows are indexed 2,3,4,...; columns are indexed 0,1,2,....

Original entry on oeis.org

1, 3, 1, 13, 8, 2, 66, 60, 25, 5, 367, 442, 255, 84, 14, 2164, 3248, 2380, 1064, 294, 42, 13293, 23904, 21192, 11832, 4410, 1056, 132, 84157, 176397, 183303, 122115, 56430, 18216, 3861, 429, 545270, 1305480, 1554850, 1200320, 657195, 262262, 75075

Offset: 2

Emeric Deutsch, Dec 28 2003

			T(4,1)=8 because, considering the complete graph K_4 on the nodes A,B,C and D, we obtain a non-crossing connected graph on A,B,C,D, with exactly one triangle, by deleting one of the two diagonals and one of the four sides (8 possibilities).
Triangle starts:
    1;
    3,   1;
   13,   8,   2;
   66,  60,  25,   5;
  367, 442, 255,  84,  14;
  ...

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

T(n, n-2) yields the Catalan numbers (A000108) corresponding to triangulations, T(n, 0) yields A045743, row sums yield A007297.

Cf. A007297, A000108, A045743.

t[n_, k_] = Binomial[n+k-2, k]*Sum[Binomial[n+k+i-2, i]*Binomial[3n-3-k-i, 2n-1+i], {i, 0, Floor[(n-k-2)/2]}]/(n-1) ;
Flatten[Table[t[n, k], {n, 2, 10}, {k, 0, n-2}]][[1 ;; 43]] (* Jean-François Alcover, Jun 20 2011 *)

T(n, k) = binomial(n+k-2, k)*sum(i=0,floor((n-k-2)/2),binomial(n+k+i-2, i)*binomial(3*n-3-k-i, 2*n-1+i))/(n-1); \\ Michel Marcus, Oct 26 2015

T(n, k) = binomial(n+k-2, k)*sum(binomial(n+k+i-2, i)*binomial(3*n-3-k-i, 2*n-1+i), i=0..floor((n-k-2)/2))/(n-1), n>=2, k>=0.

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

Keyword tabl added by Michel Marcus, Apr 09 2013

cp's OEIS Frontend

A089436 Number of non-crossing connected graphs on n nodes on a circle in which a fixed (distinguished) node has degree one.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A365842 Expansion of (1/x) * Series_Reversion( x*(1-x)^2/(1+x)^3 ).

Views

Author

Keywords

Crossrefs

Programs

PARI

Formula

A143018 Triangle read by rows: T(n,k) (n >= 2, k >= 1) is the number of non-crossing connected graphs on n nodes on a circle such that the distance from a fixed node (root) to the next node is k. Rows are indexed 2,3,4,...; columns are indexed 1,2,3, ... .

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A143022 Triangle read by rows: T(n,k) is the number of non-crossing connected graphs on n nodes on a circle in which the root (a distinguished node) has degree k (n >= 2, 1 <= k <= n-1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

A326341 Number of minimal topologically connected chord graphs covering {1..n}.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A361243 Number of nonequivalent noncrossing cacti with n nodes up to rotation and reflection.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A365844 Expansion of (1/x) * Series_Reversion( x*(1-x)^4/(1+x)^3 ).

Views

Author

Keywords

Crossrefs

Programs

PARI

Formula

A365845 Expansion of (1/x) * Series_Reversion( x*(1-x)^5/(1+x)^3 ).

Views

Author

Keywords