|
%I #34 Jul 28 2017 09:39:05
%S 1,1,7,73,879,11713,167423,2519937,39458047,637446145,10561615871,
%T 178683815937,3076487458815,53766284722177,951817354412031,
%U 17039752595865601,308068940431556607,5618467344224354305
%N c(n) = number of c-nets on n vertices.
%C Definition of c-net: a 3-connected planar map, rooted by a directed edge on the outer face.
%H Gheorghe Coserea, <a href="/A106651/b106651.txt">Table of n, a(n) for n = 3..302</a>
%H M. Bodirsky, C. Groepl, D. Johannsen and M. Kang, <a href="http://www.emis.de/journals/SLC/wpapers/s54Abogrjoka.html">A Direct Decomposition of 3-connected Planar Graphs</a>, conference paper (FPSAC05).
%H Gheorghe Coserea, <a href="/A106651/a106651.txt">Algebraic equation for g.f.</a>
%H R. C. Mullin, P. J. Schellenberg, <a href="http://dx.doi.org/10.1016/S0021-9800(68)80007-9">The enumeration of c-nets via quadrangulations</a>, J. Combinatorial Theory 4 1968 259--276. MR0218275 (36 #1362).
%F 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.
%e c(0)=c(1)=1 because the only c-nets on 3 respectively 4 vertices are the complete graphs.
%t 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);
%o (PARI)
%o x='x; y='y;
%o system("wget http://oeis.org/A106651/a106651.txt");
%o Fxy = read("a106651.txt");
%o seq(N) = {
%o my(y0 = 1 + O('x^N), y1=0);
%o for (k = 1, N,
%o y1 = y0 - subst(Fxy, y, y0)/subst(deriv(Fxy, y), y, y0);
%o if (y1 == y0, break()); y0 = y1);
%o Vec(y0);
%o };
%o seq(18) \\ _Gheorghe Coserea_, Jan 08 2017
%o (PARI)
%o A290326(n,k) = {
%o if (n < 3 || k < 3, return(0));
%o sum(i=0, k-1, sum(j=0, n-1,
%o (-1)^((i+j+1)%2) * binomial(i+j, i)*(i+j+1)*(i+j+2)/2*
%o (binomial(2*n, k-i-1) * binomial(2*k, n-j-1) -
%o 4 * binomial(2*n-1, k-i-2) * binomial(2*k-1, n-j-2))));
%o };
%o a(n) = if (n==3, 1, sum(k = (n+3)\2, 2*n-5, A290326(n-1, k)));
%o vector(18, n, a(n+2)) \\ _Gheorghe Coserea_, Jul 28 2017
%Y Cf. A001506, A001507, A001508, A285165, A290326.
%K easy,nonn
%O 3,3
%A Daniel Johannsen (johannse(AT)informatik.hu-berlin.de), May 12 2005
%E Mathematica code improved by _David Radcliffe_, Feb 12 2011
| 