A106651 -id:A106651 - 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

A285165 Triangle read by rows: T(n,k) is the number of c-nets with n-k inner vertices and k outer vertices, 3 <= n, 2 <= k <= n-1.

Original entry on oeis.org

1, 1, 1, 7, 6, 1, 73, 56, 16, 1, 879, 640, 208, 30, 1, 11713, 8256, 2848, 560, 48, 1, 167423, 115456, 41216, 9440, 1240, 70, 1, 2519937, 1710592, 624384, 156592, 25864, 2408, 96, 1, 39458047, 26468352, 9812992, 2613664, 496944, 61712, 4256, 126, 1, 637446145, 423641088, 158883840, 44169600, 9234368, 1377600, 132480, 7008, 160, 1, 10561615871, 6966960128, 2636197888, 756712960, 169378560, 28663040, 3430528, 261648, 10920, 198, 1

Offset: 3

Gheorghe Coserea, Apr 12 2017

			Triangle starts:
n\k  [2]       [3]       [4]      [5]      [6]     [7]    [8]   [9]  [10]
[3]  1;
[4]  1,        1;
[5]  7,        6,        1;
[6]  73,       56,       16,      1;
[7]  879,      640,      208,     30,      1;
[8]  11713,    8256,     2848,    560,     48,     1
[9]  167423,   115456,   41216,   9440,    1240,   70,    1;
[10] 2519937,  1710592,  624384,  156592,  25864,  2408,  96,   1;
[11] 39458047, 26468352, 9812992, 2613664, 496944, 61712, 4256, 126, 1;
[12] ...

Gheorghe Coserea, Rows n=3..203, flattened
M. Bodirsky, C. Groepl, D. Johannsen and M. Kang, A Direct Decomposition of 3-connected Planar Graphs, conference paper (FPSAC05).

Cf. A290326.

Columns k=2-9 give: A106651(k=2), A285166(k=3), A285167(k=4), A285168(k=5), A285169(k=6), A285170(k=7), A285171(k=8), A285172(k=9).

x='x; y='y;
system("wget http://oeis.org/A106651/a106651.txt");
Fy = read("a106651.txt");
A106651_ser(N) = {
  my(y0 = 1 + O(x^N), y1=0, n=1);
  while(n++,
    y1 = y0 - subst(Fy, y, y0)/subst(deriv(Fy, y), y, y0);
    if (y1 == y0, break()); y0 = y1);
  y0;
};
z='z; t='t; u='u; c0='c0;
r1 = 2*t*u + 2*t^2*u + 2*t*u^2 + 2*t^2*u^2;
r2 = 4*t^2 + 4*t^3 + 4*t^2*u + 4*t^3*u;
r3 = -4*t^2 - 4*t^3 - 2*t*u - 6*t^2*u - 4*t^3*u - 2*t*u^2 - 2*t^2*u^2;
r4 = 2*t + 2*t^2 + 4*t^3 - u + t*u + 4*t^3*u + u^2 + t*u^2 - 2*t^2*u^2;
r5 = -2*t - 2*t^2 - 4*t^3 - 4*t*u - 2*t^2*u - 4*t^3*u + 2*t^2*u^2;
r6 = u + 2*t*u + 2*t^2*u - t*u^2;
Fz = r1*z^2 + (r3*c0 + r4)*z + r2*c0^2 + r5*c0 + r6;
seq(N) = {
  N += 10; my(z0 = 1 + O(t^N) + O(u^N), z1=0, n=1,
  Fz = subst(Fz, 'c0, subst(A106651_ser(N), 'x, 't)));
  while(n++,
    z1 = z0 - subst(Fz, z, z0)/subst(deriv(Fz, z) , z, z0);
    if (z1 == z0, break()); z0 = z1);
  vector(N-10, n, vector(n, k, polcoeff(polcoeff(z0, n-k), k-1)));
};
concat(seq(11))

A106651(n) = T(n,2) = Sum_{k=3..n-1} T(n,k), for n>=4.

T(n,n-2) = A054000(n-3) for n>= 5, T(n,n-3) = 8*A006325(n-3) for n>=6. - Gheorghe Coserea, Apr 19 2017

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