A089436 -id:A089436 - cp's OEIS frontend

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

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

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

cp's OEIS Frontend

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

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