A006384 Number of sensed planar maps with n edges. (Formerly M1281)

1, 2, 4, 14, 57, 312, 2071, 15030, 117735, 967850, 8268816, 72833730, 658049140, 6074058060, 57106433817, 545532037612, 5284835906037, 51833908183164, 514019531037910, 5147924676612282, 52017438279806634, 529867070532745464

Offset

0,2

Comments

The planar maps considered are connected and may contain loops and parallel edges. - Andrew Howroyd, Jan 13 2025

References

V. A. Liskovets, A census of nonisomorphic planar maps, in Algebraic Methods in Graph Theory, Vol. II, ed. L. Lovasz and V. T. Sos, North-Holland, 1981.

V. A. Liskovets, Enumeration of nonisomorphic planar maps, Selecta Math. Sovietica, 4 (No. 4, 1985), 303-323.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. R. S. Walsh, personal communication.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..300

Valery A. Liskovets, Enumerative formulas for unrooted planar maps: a pattern, Electron. J. Combin., 11:1 (2004), R88.

Valery A. Liskovets, A reductive technique for enumerating non-isomorphic planar maps, Discrete Math. 156 (1996), no. 1-3, 197--217. MR1405018 (97f:05087) - From N. J. A. Sloane, Jun 03 2012

Timothy R. Walsh, Generating nonisomorphic maps without storing them, SIAM J. Algebraic Discrete Methods 4 (1983), no. 2, 161-178.

N. J. A. Sloane, Notes

T. R. S. Walsh, Number of sensed planar maps with n edges and m vertices

T. R. S. Walsh, Data (Preprint 1, Part 1)

T. R. S. Walsh, Data (Preprint 1, Part 2)

T. R. S. Walsh, Data (Preprint 1, Part 3)

T. R. S. Walsh, Notes

T. R. S. Walsh, Number of sensed planar maps with n edges and m vertices

T. R. S. Walsh & N. J. A. Sloane, Correspondence, 1991

Nicholas C. Wormald, Counting unrooted planar maps, Discrete Math. 36 (1981), no. 2, 205-225.

Nicholas C. Wormald, On the number of planar maps, Can. J. Math. 33.1 (1981), 1-11. (Annotated scanned copy)

Formula

For n>0, a(n) = (1/2n)[A'(n)+sum_{k<n,k|n}phi(n/k) binomial(k+2,2) A'(k)]+q(n) where phi(n) is the Euler function A000010, q(n)=(n+3) A'(n-1/2)/4 if n is odd and q(n) = (n-1)A'(n-2/2)/4 if n is even, where A'(n)=A000168(n), the number of rooted maps. - Valery A. Liskovets, May 27 2006

Equivalently, a(n) = (1/2n)[2*3^n/((n+1)(n+2))*binomial(2n,n) +sum_{k<n,k|n} phi(n/k)3^k*binomial(2k,k)]+q(n) where q(n)=2*3^((n-1)/ 2)/ (n+1)*binomial(n-1,(n-1)/2) if n is odd and q(n)=2(n-1)*3^((n-2)/2)/ (n(n+2))*binomial(n-2,(n-2)/2) if n is even. - Valery A. Liskovets, May 27 2006

a(n) ~ 12^n / (sqrt(Pi) * n^(7/2)). - Vaclav Kotesovec, Sep 12 2014

Maple

with(numtheory): a:= n-> `if` (n=0, 1, floor (2*3^n /(n+1)/(n+2) *binomial(2*n, n) +add (phi(n/t) *3^t *binomial(2*t, t), t=divisors(n) minus {n}))/2/n +`if` (irem(n, 2)=1, 2*3^((n-1)/2) /(n+1) *binomial(n-1, (n-1)/2), 2*(n-1) *3^((n-2)/2) /n/(n+2) *binomial(n-2, (n-2)/2))): seq (a(n), n=0..30); # Alois P. Heinz, Apr 24 2009

Mathematica

a[0] = 1; a[n_] := (1/(2n))*(2*(3^n/((n+1)*(n+2)))*Binomial[2n, n] + Sum[ EulerPhi[n/k]*3^k*Binomial[ 2k, k], {k, Most[ Divisors[n]]}]) + q[n]; q[n_?OddQ] := 2*(3^((n-1)/2)/(n+1))*Binomial[ n-1, (n-1)/2]; q[n_?EvenQ] := 2*(n-1)*(3^((n-2)/2)/(n*(n+2)))*Binomial[ n-2, (n-2)/2]; Table[ a[n], {n, 0, 21}] (* Jean-François Alcover, after Valery A. Liskovets *)

Crossrefs

Antidiagonal sums of A379430.

Cf. A000168 (rooted), A006385 (unsensed), A006443 (achiral), A006402 (2-connected).

Sequence in context: A030809 A030958 A030885 * A204198 A003322 A170939

Adjacent sequences: A006381 A006382 A006383 * A006385 A006386 A006387

Keyword

nonn,nice

Author

N. J. A. Sloane

Extensions

More terms from Alois P. Heinz, Apr 24 2009

Status

approved