A054935 - OEIS

%I #40 Aug 30 2019 08:30:53

%S 1,3,7,33,156,1070,7515,59151,483925,4136964,36416865,329048627,

%T 3037029030,28553451498,272766018806,2642420298576,25916954091582,

%U 257009789443925,2573962338306141,26008719387850068,264933535266372732

%N Number of planar maps with n edges up to orientation-preserving duality.

%C Replacing each edge by a vertex of degree 4, one sees that a(n) is also the number of non-isomorphic planar maps (a.k.a. clean dessins on the Riemann sphere) with n vertices of degree 4, and 2n edges.

%H Gheorghe Coserea, <a href="/A054935/b054935.txt">Table of n, a(n) for n = 1..200</a>

%H V. A. Liskovets, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/LISK/Derseq.html">Some easily derivable sequences</a>, J. Integer Sequences, 3 (2000), #00.2.2.

%F a(2k+1) = A006384(2k+1)/2 and a(2k) = (A006384(2k) + A006849(k))/2. - _Gheorghe Coserea_, Aug 05 2015

%t a6384[0] = 1; a6384[n_] := (1/(2n))*(2*(3^n/((n + 1)*(n + 2)))*Binomial[2 n, n] + Sum[ EulerPhi[n/k]*3^k*Binomial[ 2k, k], {k, Most[ Divisors[ n]]}]) + q[n];

%t q[n_?OddQ] := 2*(3^((n - 1)/2)/(n + 1))*Binomial[ n - 1, (n - 1)/2];

%t q[n_?EvenQ] := 2*(n-1)*(3^((n-2)/2)/(n*(n+2)))*Binomial[ n - 2, (n - 2)/2];

%t a6849[n_] := 3^n*CatalanNumber[n]/2 + If[OddQ[n], 3^((n - 1)/2)* CatalanNumber[(n - 1)/2]/2, 0];

%t a[n_] := If[OddQ[n], a6384[n]/2, (a6384[n] + a6849[n/2])/2];

%t Array[a, 21] (* _Jean-François Alcover_, Aug 30 2019 *)

%o (PARI)

%o F(n) = { 3^n * binomial(2*n,n); }

%o S(n) = { my(acc = 0);

%o          fordiv(n, d, if(d != n, acc += eulerphi(n/d) * F(d)));

%o          return(acc); }

%o Q(n) = { if (n%2, 2 * F((n-1)/2) / (n+1),

%o                   2 * F((n-2)/2) * (n-1)/(n*(n+2))); }

%o A006384(n) = { if (n < 0, return(0)); if (n == 0, return(1));

%o                (2*F(n)/((n+1)*(n+2)) + S(n)) / (2*n) + Q(n); }

%o G(n) = { 3^n * binomial(2*n,n) / (n + 1); }

%o A006849(n) = { if (n <= 0, return(0));

%o                if (n%2, (G(n) + G((n-1)/2)) / 2, G(n)/2); }

%o a(n) = { if (n <= 0, return(0));

%o          if (n%2,  A006384(n)/2, (A006384(n) + A006849(n/2))/2) };

%o apply(n->a(n), vector(33, i, i)) \\ _Gheorghe Coserea_, Aug 20 2015

%Y Average of A006384 and A006849, the latter interspersed with 0's (cf. formula).

%K nonn,easy

%O 1,2

%A _N. J. A. Sloane_, May 24 2000

%E More terms from _Valery A. Liskovets_, May 27 2006

%E More terms from _Sean A. Irvine_, Mar 24 2013