A103940 Number of unrooted bipartite n-edge maps in the plane (planar with a distinguished outside face).

1, 1, 2, 5, 18, 72, 368, 1982, 11514, 69270, 430384, 2736894, 17752884, 117039548, 782480424, 5294705752, 36206357114, 249894328848, 1739030128872, 12191512867814, 86037243899240, 610827161152012, 4360291880624504, 31280354620428378, 225427088761560916, 1631398499577667252

Offset

0,3

Comments

Bipartite planar maps are dual to Eulerian planar maps.

References

V. A. Liskovets and T. R. Walsh, Enumeration of unrooted maps on the plane, Rapport technique, UQAM, No. 2005-01, Montreal, Canada, 2005.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..500

V. A. Liskovets and T. R. Walsh, Counting unrooted maps on the plane, Advances in Applied Math., 36, No.4 (2006), 364-387.

Formula

For n > 0, a(n) = (1/(2n))*[2^(n-1)*binomial(2n, n)/(n+1) + Sum_{0<k<n, k|n} phi(n/k)*d(n/k)*2^(k-1)*binomial(2k, k)] + q(n) where phi is the Euler function A000010, d(n)=2, q(n)=0 if n is even and d(n)=1, q(n)=2^((n-1)/2)*binomial(n-1, (n-1)/2)/(n+1) if n is odd.

Mathematica

a[n_] := (1/(2 n)) (2^(n - 1) Binomial[2 n, n]/(n+1) + Sum[Boole[0 < k < n] EulerPhi[n/k] d[n/k] 2^(k-1) Binomial[2k, k], {k, Divisors[n]}]) + q[n];
d[n_] := If[EvenQ[n], 2, 1];
q[n_] := If[EvenQ[n], 0, 2^((n-1)/2) Binomial[n-1, (n-1)/2]/(n+1)];
Array[a, 25] (* Jean-François Alcover, Aug 30 2019 *)

Prog

(PARI) a(n)={if(n==0, 1, sumdiv(n, d, if(d<n, 1, 1/(n+1)) * eulerphi(n/d) * (2-n/d%2) * 2^(d-1) * binomial(2*d, d))/(2*n) + if(n%2, 2^((n-1)/2)*binomial(n-1, (n-1)/2)/(n+1)))} \\ Andrew Howroyd, Mar 29 2021

Crossrefs

Cf. A003645, A103939, A069727.

Sequence in context: A189843 A045612 A371494 * A162543 A039744 A344262

Adjacent sequences: A103937 A103938 A103939 * A103941 A103942 A103943

Keyword

easy,nonn

Author

Valery A. Liskovets, Mar 17 2005

Extensions

More terms from Jean-François Alcover, Aug 30 2019

a(0)=1 prepended by Andrew Howroyd, Mar 29 2021

Status

approved