A001508 -id:A001508 - cp's OEIS frontend

A290326 Triangle read by rows: T(n,k) is the number of c-nets with n+1 faces and k+1 vertices.

0, 0, 0, 0, 0, 1, 0, 0, 0, 4, 3, 0, 0, 0, 3, 24, 33, 13, 0, 0, 0, 0, 33, 188, 338, 252, 68, 0, 0, 0, 0, 13, 338, 1705, 3580, 3740, 1938, 399, 0, 0, 0, 0, 0, 252, 3580, 16980, 39525, 51300, 38076, 15180, 2530, 0, 0, 0, 0, 0, 68, 3740, 39525, 180670, 452865, 685419, 646415, 373175, 121095, 16965, 0, 0, 0, 0, 0, 0, 1938, 51300, 452865, 2020120, 5354832, 9095856, 10215450, 7580040, 3585270, 981708, 118668

Offset: 1

Gheorghe Coserea, Jul 27 2017

Row n >= 3 contains 2*n-3 terms.
c-nets are 3-connected rooted planar maps. This array also counts simple triangulations.
Table in Mullin & Schellenberg has incorrect values T(14,14) = 43494961412, T(15,13) = 21697730849, T(15,14) = 131631305614, T(15,15) = 556461655783. - Sean A. Irvine, Sep 28 2015

			A(x;t) = t^3*x^3 + (4*t^4 + 3*t^5)*x^4 + (3*t^4 + 24*t^5 + 33*t^6 + 13*t^7)*x^5 + ...
Triangle starts:
n\k  [1] [2] [3] [4] [5] [6]  [7]   [8]    [9]    [10]   [11]   [12]   [13]
[1]  0;
[2]  0,  0;
[3]  0,  0,  1;
[4]  0,  0,  0,  4,  3;
[5]  0,  0,  0,  3,  24, 33,  13;
[6]  0,  0,  0,  0,  33, 188, 338,  252,   68;
[7]  0,  0,  0,  0,  13, 338, 1705, 3580,  3740,  1938,  399;
[8]  0,  0,  0,  0,  0,  252, 3580, 16980, 39525, 51300, 38076, 15180, 2530;
[9]  ...

Gheorghe Coserea, Rows n = 1..103, flattened
R. C. Mullin, P. J. Schellenberg, The enumeration of c-nets via quadrangulations, J. Combinatorial Theory 4 1968 259--276. MR0218275 (36 #1362).

Cf. A000260, A001506, A001507, A001508.
Rows/Columns sum give A106651 (enumeration of c-nets by the number of vertices).
Antidiagonals sum give A000287 (enumeration of c-nets by the number of edges).

T(n,k) = {
  if (n < 3 || k < 3, return(0));
  sum(i=0, k-1, sum(j=0, n-1,
     (-1)^((i+j+1)%2) * binomial(i+j, i)*(i+j+1)*(i+j+2)/2*
     (binomial(2*n, k-i-1) * binomial(2*k, n-j-1) -
      4 * binomial(2*n-1, k-i-2) * binomial(2*k-1, n-j-2))));
};
N=10; concat(concat([0,0,0], apply(n->vector(2*n-3, k, T(n,k)), [3..N])))
\\ test 1: N=100; y=x*Ser(vector(N, n, sum(i=1+(n+2)\3, (2*n)\3-1, T(i,n-i)))); 0 == x*(x+1)^2*(x+2)*(4*x-1)*y' + 2*(x^2-11*x+1)*(x+1)^2*y + 10*x^6
/*
\\ test 2:
x='x; t='t; N=44; y=Ser(apply(n->Polrev(vector(2*n-3, k, T(n, k)), 't), [3..N+2]), 'x) * t*x^3;
0 == (t + 1)^3*(x + 1)^3*(t + x + t*x)^3*y^4 + t*(t + 1)^2*x*(x + 1)^2*((4*t^4 + 12*t^3 + 12*t^2 + 4*t)*x^4 + (12*t^4 + 16*t^3 - 4*t^2 - 8*t)*x^3 + (12*t^4 - 4*t^3 - 49*t^2 - 30*t + 3)*x^2 + (4*t^4 - 8*t^3 - 30*t^2 - 21*t)*x + 3*t^2)*y^3 + t^2*(t + 1)*x^2*(x + 1)*((6*t^5 + 18*t^4 + 18*t^3 + 6*t^2)*x^5 + (18*t^5 + 12*t^4 - 30*t^3 - 24*t^2)*x^4 + (18*t^5 - 30*t^4 - 123*t^3 - 58*t^2 + 17*t)*x^3 + (6*t^5 - 24*t^4 - 58*t^3 + 25*t^2 + 56*t)*x^2 + (17*t^3 + 56*t^2 + 48*t + 3)*x + 3*t)*y^2 + t^3*x^3*((4*t^6 + 12*t^5 + 12*t^4 + 4*t^3)*x^6 + (12*t^6 - 36*t^4 - 24*t^3)*x^5 + (12*t^6 - 36*t^5 - 99*t^4 - 26*t^3 + 25*t^2)*x^4 + (4*t^6 - 24*t^5 - 26*t^4 + 81*t^3 + 80*t^2)*x^3 + (25*t^4 + 80*t^3 + 44*t^2 - 14*t)*x^2 + (-14*t^2 - 17*t)*x + 1)*y + t^6*x^6*((t^4 + 2*t^3 + t^2)*x^4 + (2*t^4 - 7*t^3 - 9*t^2)*x^3 + (t^4 - 9*t^3 + 11*t)*x^2 + (11*t^2 + 13*t)*x - 1)
*/

T(n,k) = Sum_{i=0..k-1} Sum_{j=0..n-1} (-1)^(i+j+1) * ((i+j+2)!/(2!*i!*j!)) * (binomial(2*n, k-i-1) * binomial(2*k, n-j-1) - 4 * binomial(2*n-1, k-i-2) * binomial(2*k-1, n-j-2)) for all n >= 3, k >= 3.
A106651(n+1) = Sum_{k=1..2*n-3} T(n,k) for n >= 3.
A000287(n) = Sum_{i=1+floor((n+2)/3)..floor(2*n/3)-1} T(i,n-i).
A001506(n) = T(n,n), A001507(n) = T(n+1,n), A001508(n) = T(n+2,n).
A000260(n-2) = T(n, 2*n-3) for n>=3.
G.f. y = A(x;t) satisfies: 0 = (t + 1)^3*(x + 1)^3*(t + x + t*x)^3*y^4 + t*(t + 1)^2*x*(x + 1)^2*((4*t^4 + 12*t^3 + 12*t^2 + 4*t)*x^4 + (12*t^4 + 16*t^3 - 4*t^2 - 8*t)*x^3 + (12*t^4 - 4*t^3 - 49*t^2 - 30*t + 3)*x^2 + (4*t^4 - 8*t^3 - 30*t^2 - 21*t)*x + 3*t^2)*y^3 + t^2*(t + 1)*x^2*(x + 1)*((6*t^5 + 18*t^4 + 18*t^3 + 6*t^2)*x^5 + (18*t^5 + 12*t^4 - 30*t^3 - 24*t^2)*x^4 + (18*t^5 - 30*t^4 - 123*t^3 - 58*t^2 + 17*t)*x^3 + (6*t^5 - 24*t^4 - 58*t^3 + 25*t^2 + 56*t)*x^2 + (17*t^3 + 56*t^2 + 48*t + 3)*x + 3*t)*y^2 + t^3*x^3*((4*t^6 + 12*t^5 + 12*t^4 + 4*t^3)*x^6 + (12*t^6 - 36*t^4 - 24*t^3)*x^5 + (12*t^6 - 36*t^5 - 99*t^4 - 26*t^3 + 25*t^2)*x^4 + (4*t^6 - 24*t^5 - 26*t^4 + 81*t^3 + 80*t^2)*x^3 + (25*t^4 + 80*t^3 + 44*t^2 - 14*t)*x^2 + (-14*t^2 - 17*t)*x + 1)*y + t^6*x^6*((t^4 + 2*t^3 + t^2)*x^4 + (2*t^4 - 7*t^3 - 9*t^2)*x^3 + (t^4 - 9*t^3 + 11*t)*x^2 + (11*t^2 + 13*t)*x - 1). - Gheorghe Coserea, Sep 29 2018

A106651 c(n) = number of c-nets on n vertices.

Original entry on oeis.org

1, 1, 7, 73, 879, 11713, 167423, 2519937, 39458047, 637446145, 10561615871, 178683815937, 3076487458815, 53766284722177, 951817354412031, 17039752595865601, 308068940431556607, 5618467344224354305

Offset: 3

Daniel Johannsen (johannse(AT)informatik.hu-berlin.de), May 12 2005

Definition of c-net: a 3-connected planar map, rooted by a directed edge on the outer face.

			c(0)=c(1)=1 because the only c-nets on 3 respectively 4 vertices are the complete graphs.

Gheorghe Coserea, Table of n, a(n) for n = 3..302
M. Bodirsky, C. Groepl, D. Johannsen and M. Kang, A Direct Decomposition of 3-connected Planar Graphs, conference paper (FPSAC05).
Gheorghe Coserea, Algebraic equation for g.f.
R. C. Mullin, P. J. Schellenberg, The enumeration of c-nets via quadrangulations, J. Combinatorial Theory 4 1968 259--276. MR0218275 (36 #1362).

Cf. A001506, A001507, A001508, A285165, A290326.

c[0] = 1; c[1] = 1; c[2] = 7; c[3] = 73; c[4] = 879; c[5] = 11713; c[6] = 167423; c[7] = 2519937; c[n_] := c[n] = ( (-189665280 + 134270976 n - 31309824 n^2 + 2408448 n^3) c[n - 7] + (-479162880 + 376680448 n - 98932224 n^2 + 8692736 n^3) c[n - 6] + (-446660160 + 384601888 n - 112131264 n^2 + 11026784 n^3) c[n - 5] + (-183645792 + 168826836 n - 52598160 n^2 + 5361276 n^3) c[n - 4] + (-25324080 + 24563948 n - 6853668 n^2 + 418816 n^3) c[n - 3] + (1156086 - 2064937 n + 1206966 n^2 - 180467 n^3) c[n - 2] + (-3192 + 4842 n - 29796 n^2 + 18930 n^3) c[n - 1] ) / (126 + 693 n + 1134 n^2 + 567 n^3);

x='x; y='y;
system("wget http://oeis.org/A106651/a106651.txt");
Fxy = read("a106651.txt");
seq(N) = {
  my(y0 = 1 + O('x^N), y1=0);
  for (k = 1, N,
    y1 = y0 - subst(Fxy, y, y0)/subst(deriv(Fxy, y), y, y0);
    if (y1 == y0, break()); y0 = y1);
  Vec(y0);
};
seq(18)  \\ Gheorghe Coserea, Jan 08 2017

A290326(n,k) = {
  if (n < 3 || k < 3, return(0));
  sum(i=0, k-1, sum(j=0, n-1,
     (-1)^((i+j+1)%2) * binomial(i+j, i)*(i+j+1)*(i+j+2)/2*
     (binomial(2*n, k-i-1) * binomial(2*k, n-j-1) -
      4 * binomial(2*n-1, k-i-2) * binomial(2*k-1, n-j-2))));
};
a(n) = if (n==3, 1, sum(k = (n+3)\2, 2*n-5, A290326(n-1, k)));
vector(18, n, a(n+2)) \\ Gheorghe Coserea, Jul 28 2017

c(0)=1, c(1) = 1, c(2) = 7, c(3) = 73, c(4) = 879, c(5) = 11713, c(6) = 167423, c(7) = 2519937, c(n) = ( (-189665280 + 134270976 n - 31309824 n^2 + 2408448 n^3) c(n-7) + (-479162880 + 376680448 n - 98932224 n^2 + 8692736 n^3) c(n-6) + (-446660160 + 384601888 n - 112131264 n^2 + 11026784 n^3) c(n-5) + (-183645792 + 168826836 n - 52598160 n^2 + 5361276 n^3) c(n-4) + (-25324080 + 24563948 n - 6853668 n^2 + 418816 n^3) c(n-3) + (1156086 - 2064937 n + 1206966 n^2 - 180467 n^3) c(n-2) + (-3192 + 4842 n - 29796 n^2 + 18930 n^3) c(n-1) ) / (126 + 693 n + 1134 n^2 + 567 n^3). Generating function C(t)=sum_(n>=0){c(n-3)t^n} implicitly given by: 0 = -1 + C(t) + 36 t - 43 C(t) t + 6 C(t)^2 t + 131 t^2 - 337 C(t) t^2 + 218 C(t)^2 t^2 + 12 C(t)^3 t^2 + 350 t^3 - 1021 C(t) t^3 + 894 C(t)^2 t^3 - 228 C(t)^3 t^3 + 8 C(t)^4 t^3 + 540 t^4 - 1828 C(t) t^4 + 2190 C(t)^2 t^4 - 988 C(t)^3 t^4 + 72 C(t)^4 t^4 + 616 t^5 - 2404 C(t) t^5 + 3284 C(t)^2 t^5 - 1756 C(t)^3 t^5 + 264 C(t)^4 t^ 5 + 536 t^6 - 2128 C(t) t^6 + 3120 C(t)^2 t^6 - 2032 C(t)^3 t^6 + 504 C(t)^4 t^6 + 304 t^7 - 1344 C(t) t^7 + 2304 C(t)^2 t^7 - 1792 C(t)^3 t^7 + 528 C(t)^4 t^7 + 160 t^8 - 768 C(t) t^8 + 1344 C(t)^2 t^8 - 1024 C(t)^3 t^8 + 288 C(t)^4 t^8 + 64 t^9 - 256 C(t) t^9 + 384 C(t)^2 t^9 - 256 C(t)^3 t^9 + 64 C(t)^4 t^9. Explicit generating function can be obtained using Mathematica.

Mathematica code improved by David Radcliffe, Feb 12 2011

cp's OEIS Frontend

A290326 Triangle read by rows: T(n,k) is the number of c-nets with n+1 faces and k+1 vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A106651 c(n) = number of c-nets on n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions