A007297 -id:A007297 - cp's OEIS frontend

A143020 Sum of the distances from a fixed node (root) to the next node in all non-crossing graphs on n nodes on a circle.

1, 5, 31, 218, 1658, 13293, 110675, 947870, 8297926, 73924162, 668038006, 6108962580, 56426393268, 525673683069, 4933634156571, 46604425575734, 442753710351950, 4227598589181750, 40549714320544770, 390522305786747820

Offset: 2

Emeric Deutsch, Jul 30 2008

nonn

			a(3)=5 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.

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

Cf. A007297, A143018.

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: seq(add(k*T(n,k),k=1..n-1),n=2..22);

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]}]; a[n_] := Sum[k*t[n, k], {k, 1, n-1}] ; Table[a[n], {n, 2, 21}] (* Jean-François Alcover, Oct 05 2011, after Maple *)

Vec((g->g*(g-x)/x)(x + x*serreverse((x-x^2)/(1+x)^3 + O(x^20)))) \\ Andrew Howroyd, Nov 17 2017

L(p,q,r)={sum(i=0, min(p,q), binomial(q,i)*binomial(r+p-1-i,r-1))}
a(n)=sum(k=1, n-1, k^2*L(n-k-1,3*n-k-4, n-1)/(n-1)); \\ Andrew Howroyd, Nov 17 2017

a(n) = Sum_{k=1..n-1} k*T(n,k), where T(n,k) = k*L(n-k-1,3n-k-4,n-1)/(n-1) (n >= 2, 1 <= k <= n-1), with L(p,q,r)=[u^p](1+u)^q/(1-u)^r = Sum[binomial(q,i)binomial(r+p-1-i,r-1), i=0..min(p,q)] (T(n,k) is A143018).
G.f.: g(g-z)/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 - 3zg + 2z^2 = 0 (A007297).
a(n) = Sum_{k=1..n-1} k*A143018(n, k).
Conjecture: -(n-1) *(n+1) *(39*n^2-136*n+60) *a(n) +60 *(-18*n^2+57*n-7) *a(n-1) +12 *(3*n-7) *(3*n-8) *(39*n^2-58*n-37) *a(n-2)=0. - R. J. Mathar, May 10 2018

A143023 Sum of the root degrees over all non-crossing connected graphs on n nodes on a circle (by root we mean a distinguished node).

Original entry on oeis.org

1, 6, 41, 306, 2422, 19980, 169941, 1479786, 13127114, 118217268, 1077955034, 9932655348, 92342765868, 865126386072, 8159523358029, 77411610053658, 738263424935170, 7073522484902820, 68056887469098990, 657269559836605980

Offset: 2

Emeric Deutsch, Jul 30 2008

nonn

The number of non-crossing connected graphs on n nodes on a circle is given in A007297.

			a(3)=6 because in the graphs (AB,BC,CA), (AB,AC), (AB,BC) and (AC,BC) the root, say A, has degrees 2, 2, 1 and 1, respectively.

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

Cf. A143022, A007297.

eq:=G*(1-G)-z*(1+G)^3: G:=RootOf(eq,G): Gser:=series(z*G*(1+G)/(1-G),z=0,25): seq(coeff(Gser,z,n),n=2..21); # end
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: a:=proc(n) options operator, arrow: (L(n-2,3*n-2, n+1)+L(n-3,3*n-3,n))/(n-1) end proc: seq(a(n),n=2..21);

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; a[n_] := Sum[ k*t[n, k], {k, 1, n-1}]; Table[a[n], {n, 2, 21}] (* Jean-François Alcover, Oct 05 2011, after Maple *)

{my(n=25); my(g=serreverse(x*(1-x)/(1+x)^3 + O(x*x^n))); Vec(g*(1+g)/(1-g))} \\ Andrew Howroyd, Dec 22 2017

a(n) = (L(n-2, 3n-2, n+1) + L(n-3, 3n-3, n))/(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.:  zG(1+G)/(1-G) where G=G(z) satisfies G(1-G)=z(1+G)^3.
a(n) = Sum_{k=1..n-1} k*A143022(n,k).
D-finite with recurrence 5*n*(n-1)*a(n) -18*(n-1)*(n-3)*a(n-1) +12*(-45*n^2+180*n-178)*a(n-2) +216*(3*n-10)*(3*n-11)*a(n-3)=0. - R. J. Mathar, Jul 26 2022

A244469 a(0) = 0, thereafter, a(n) = 2^(2n-1)( binomial((3n-1)/2,n) - binomial(3n/2, n)/3 ).

Original entry on oeis.org

0, 1, 7, 58, 515, 4746, 44758, 428772, 4154403, 40599130, 399429602, 3950996556, 39255152846, 391466112324, 3916110379020, 39281346256008, 394942611929379, 3978982062756090, 40160256911157610, 405995113593507900, 4110284071450416090, 41666530928566504620, 422876855107176561780

Offset: 0

N. J. A. Sloane, Jun 28 2014

nonn

Vincenzo Librandi, Table of n, a(n) for n = 0..200
I. M. Gessel, A short proof of the Deutsch-Sagan congruence for connected non crossing graphs, arXiv preprint arXiv:1403.7656 [math.CO], 2014. See f_4(n).

Cf. A000108, A007297, A064062, A091527, A244039.

[n eq 0 select 0 else Round(2^(2*n-1)*(Gamma((3*n+1)/2)/Gamma((n+1)/2) - Gamma((3*n+2)/2)/(3*Gamma((n+2)/2)))/Factorial(n)): n in [0..30]]; // G. C. Greubel, Apr 17 2019

f4:=n->-(2^(2*n-1)/3)*binomial(3*n/2,n) + 2^(2*n-1)*binomial((3*n-1)/2,n);
[seq(f4(n),n=1..40)]; # then prepend f4(0)=0.

Join[{0}, Table[-(2^(2 n - 1)/3) Binomial[3 n/2, n] + 2^(2 n - 1) Binomial[(3 n - 1)/2, n], {n, 1, 30}]] (* Vincenzo Librandi, Jun 29 2014 *)

{a(n) = if(n==0,0, 2^(2*n-1)*(binomial((3*n-1)/2, n) - binomial(3*n/2, n)/3) )}; \\ G. C. Greubel, Apr 17 2019

def a(n):
   if n==0: return 0
   else: return 2^(2*n-1)*(binomial((3*n-1)/2, n) - binomial(3*n/2, n)/3)
[a(n) for n in (0..30)] # G. C. Greubel, Apr 17 2019

G.f.: g'(x)/g(x)-1, g(x)=(2*sqrt(9*x+1)*sin(arcsin((54*x^2+27*x+2)/(2*(9*x+1)^(3/2)))/3))/3-1/3. - Vladimir Kruchinin, Apr 14 2019
From Peter Bala, Mar 05 2022: (Start)
a(n) = (1/n)*Sum_{k = 0..n} k*2^(n-k)*binomial(n+k-1,k)*binomial(2*n-k-1,n-k) for n >= 1.
a(n) = [x^n] G(x)^n = [x^n] 1/(1 - x*C(2*x))^n, where C(x) = (1 - sqrt(1 - 4*x))/(2*x) is the g.f. of the Catalan numbers A000108 and G(x) is the g.f. of A064062.
n*(n-1)*(6*n-7)*a(n) = - 18*(n-1)*a(n-1) + 12*(3*n-5)*(6*n-1)*(3*n-4)*a(n-2) with a(1) = 1 a(2) = 7.
exp(Sum_{n >= 1} a(n)*x^n/n) = 1 + x + 4*x^2 + 23*x^3 + 156*x^4 + ... is the g.f. of A007297.
The Gauss congruences a(n*p^k) == a(n*p^(k-1)) (mod p^k) hold for all primes p and positive integers n and k. (End)

A143021 Number of vertices of degree 1 in all non-crossing connected graphs on n points on a circle.

Original entry on oeis.org

2, 6, 36, 270, 2244, 19740, 179880, 1678446, 15927780, 153055188, 1485010488, 14518525164, 142821228648, 1412109087480, 14021321053392, 139725123309486, 1396698760714788, 13998927825197220, 140638610864578200

Offset: 2

Emeric Deutsch, Jul 30 2008

nonn

			a(3)=6 because in the graphs (AB,BC,CA), (AB,AC), (AB,BC) and (AC,BC) the vertices of degree 1 are (none), {B,C}, {A,C} and {A,B}.

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

Cf. A007297, A089436.

g:=-1/3+(2/3)*sqrt(1+9*z)*sin((1/3)*arcsin(((2+27*z+54*z^2)*1/2)/(1+9*z)^(3/2))): ser:=series(z*(diff(g^2,z)),z=0,25): seq(coeff(ser,z,n), n=2..21);

terms = 19;
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] Range[2, terms+1] (* Jean-François Alcover, Jul 29 2018, after A089436 and Andrew Howroyd *)

{ my(n=30); Vec(deriv((x+x*serreverse((x-x^2)/(1+x)^3 + O(x^n)))^2)) } \\ Andrew Howroyd, Dec 22 2017

a(n) = n*A089436(n).
G.f.: z*(d/dz)g^2, 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 - 3zg + 2z^2 = 0 (A007297).
D-finite with recurrence (n-1)*(n-2)*a(n) -34*(n-2)*(n-4)*a(n-1) +4*(29*n^2-396*n+937)*a(n-2) +24*(153*n^2-1071*n+1810)*a(n-3) -2688*(3*n-14)*(3*n-16)*a(n-4)=0. - R. J. Mathar, Jul 22 2022

A143024 Triangle read by rows: T(n,k) is the number of non-crossing connected graphs on n nodes on a circle having root (a distinguished node) of degree 1 and having k edges (n >= 2, 1 <= k <= 2n-4).

Original entry on oeis.org

1, 0, 2, 0, 0, 7, 2, 0, 0, 0, 30, 20, 4, 0, 0, 0, 0, 143, 156, 65, 10, 0, 0, 0, 0, 0, 728, 1120, 720, 224, 28, 0, 0, 0, 0, 0, 0, 3876, 7752, 6783, 3192, 798, 84, 0, 0, 0, 0, 0, 0, 0, 21318, 52668, 58520, 36960, 13860, 2904, 264, 0, 0, 0, 0, 0, 0, 0, 0, 120175, 354200, 478170

Offset: 2

Emeric Deutsch, Jul 31 2008

Row n contains 2n-4 terms, the first n-2 of which are 0.
Row sums yield A089436.
T(n,n-1) = A006013(n-2).
Sum_{k=2..2n-4} k*T(n,k) = A143025.

			T(3,2)=2 because we have {AB,BC} and {AC, BC} (A is the root).
Triangle starts:
  1;
  0,   2;
  0,   0,   7,   2;
  0,   0,   0,  30,  20,   4;
  0,   0,   0,   0, 143, 156,  65,  10;

C. Domb and A. J. Barrett, Enumeration of ladder graphs, Discrete Math. 9 (1974), 341-358.
P. Flajolet and M. Noy, Analytic combinatorics of non-crossing configurations, Discrete Math., 204, 203-229, 1999.

Cf. A007297, A089436, A006013, A143025.

T:=proc(n,k) options operator, arrow: 2*binomial(k-2,n-3)*binomial(3*n-5,2*n-k-4)/(n-2) end proc: 1; for n from 3 to 10 do 0, seq(T(n,k),k=2..2*n-4) end do; % yields sequence in triangular form

T(n,k) = 2*binomial(k-2, n-3)*binomial(3n-5, 2n-k-4)/(n-2) (n >= 3, 2 <= k <= 2n-4); T(2,1)=1; T(2,k)=0 (k >= 2).

The trivariate g.f. G=G(t,s,z) for non-crossing connected graphs on nodes on a circle, with respect to number of nodes (marked by z), number of edges (marked by t) and degree of root (marked by s) is G=z + tszg^2/[z-ts(g - z + g^2)], where g=g(t,z) satisfies tg^3 + tg^2 - (1 + 2t)zg +(1 + t)z^2 = 0 (see Domb & Barrett, Eq. (47); Flajolet & Noy, Eq. (18)).

A291536 Expansion of the series reversion of x(1 + 4x + x^2)/(1 - x)^4.

Original entry on oeis.org

1, -8, 101, -1544, 26190, -474144, 8975229, -175492664, 3516970490, -71858843264, 1491301438354, -31349284476496, 666133734882748, -14284509655611840, 308734263333717021, -6718525508918998872, 147085140049822666626, -3237191565662618280384, 71584853778205231503750

Offset: 1

Ilya Gutkovskiy, Aug 25 2017

sign

Reversion of g.f. for the cubes (A000578).

N. J. A. Sloane, Transforms
Eric Weisstein's World of Mathematics, Series Reversion
Index entries for reversions of series

Cf. A000578, A007297, A263843.

Rest[CoefficientList[InverseSeries[Series[x (1 + 4 x + x^2)/(1 - x)^4, {x, 0, 19}], x], x]]

G.f. A(x) satisfies: A(x)*(1 + 4*A(x) + A(x)^2)/(1 - A(x))^4 = x.
a(n) ~ -(-1)^n * (5*sqrt(6) - 12) * 2^(3*n-2) * 3^n / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Nov 11 2017
D-finite with recurrence 7*n*(n-1)*(n+1)*a(n) +4*n*(n-1)*(58*n-83)*a(n-1) -36*(n-1)*(16*n^2-80*n+155)*a(n-2) +432*(-96*n^3+720*n^2-1794*n+1495)*a(n-3) +6912*(4*n-15)*(2*n-7)*(4*n-13)*a(n-4)=0. - R. J. Mathar, Jan 25 2023

A306551 Number of non-double-crossing set partitions of {1,...,n}.

Original entry on oeis.org

1, 1, 2, 5, 15, 52, 202, 863, 3999, 19880, 105134, 587479, 3449505

Offset: 0

Gus Wiseman, Feb 23 2019

Two blocks of a set partitions double-cross each other if they are of the form {{...a...b...c...},{...x...y...z...}} for some a < x < b < y < c < z or x < a < y < b < z < c.

			Most small set partitions are not double-crossing. The smallest that is double-crossing is {{1,3,5},{2,4,6}}.

Kenneth J. Dykema, Generating functions for purely crossing partitions, arXiv:1602.03469 [math.CO], 2016.

Cf. A000108, A000110, A001263, A002061, A005493, A007297, A016098, A054726, A099947, A324166, A324167, A324172, A324324.

nonXXQ[stn_]:=!MatchQ[stn,{_,{_,a_,_,b_,_,c_,_},_,{_,x_,_,y_,_,z_,_},_}/;a_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
Table[Length[Select[sps[Range[n]],nonXXQ]],{n,0,8}]

A306558 Number of double-crossing set partitions of {1,...,n}.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 1, 14, 141, 1267, 10841, 91091, 764092

Offset: 0

Gus Wiseman, Feb 23 2019

Two blocks of a set partitions double-cross each other if they are of the form {{...a...b...c...},{...x...y...z...}} for some a < x < b < y < c < z or x < a < y < b < z < c.

			The a(7) = 14 double-crossing set partitions:
  {{1,3,5},{2,4,6,7}}
  {{1,3,6},{2,4,5,7}}
  {{1,4,6},{2,3,5,7}}
  {{1,2,4,6},{3,5,7}}
  {{1,3,4,6},{2,5,7}}
  {{1,3,5,6},{2,4,7}}
  {{1,3,5,7},{2,4,6}}
  {{1},{2,4,6},{3,5,7}}
  {{1,3,5},{2,4,6},{7}}
  {{1,3,5},{2,4,7},{6}}
  {{1,3,6},{2,4,7},{5}}
  {{1,3,6},{2,5,7},{4}}
  {{1,4,6},{2},{3,5,7}}
  {{1,4,6},{2,5,7},{3}}

Kenneth J. Dykema, Generating functions for purely crossing partitions, arXiv:1602.03469 [math.CO], 2016.

Cf. A000108, A000110, A001263, A002061, A005493, A007297, A016098 (crossing set partitions), A054726, A099947, A324166, A324172, A324324.

croXXQ[stn_]:=MatchQ[stn,{_,{_,a_,_,b_,_,c_,_},_,{_,x_,_,y_,_,z_,_},_}/;a_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
Table[Length[Select[sps[Range[n]],croXXQ]],{n,0,8}]

cp's OEIS Frontend

A143020 Sum of the distances from a fixed node (root) to the next node in all non-crossing graphs on n nodes on a circle.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

A143023 Sum of the root degrees over all non-crossing connected graphs on n nodes on a circle (by root we mean a distinguished node).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A244469 a(0) = 0, thereafter, a(n) = 2^(2*n-1)*( binomial((3*n-1)/2,n) - binomial(3*n/2, n)/3 ).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

A143021 Number of vertices of degree 1 in all non-crossing connected graphs on n points on a circle.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A143024 Triangle read by rows: T(n,k) is the number of non-crossing connected graphs on n nodes on a circle having root (a distinguished node) of degree 1 and having k edges (n >= 2, 1 <= k <= 2n-4).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A291536 Expansion of the series reversion of x*(1 + 4*x + x^2)/(1 - x)^4.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A306551 Number of non-double-crossing set partitions of {1,...,n}.

Views

Author

Keywords

Comments

Examples

Links

A244469 a(0) = 0, thereafter, a(n) = 2^(2n-1)( binomial((3n-1)/2,n) - binomial(3n/2, n)/3 ).

A291536 Expansion of the series reversion of x(1 + 4x + x^2)/(1 - x)^4.