|
| |
|
|
A006384
|
|
Number of planar maps with n edges.
(Formerly M1281)
|
|
4
|
|
|
|
1, 2, 4, 14, 57, 312, 2071, 15030, 117735, 967850, 8268816, 72833730, 658049140, 6074058060, 57106433817, 545532037612, 5284835906037, 51833908183164, 514019531037910, 5147924676612282, 52017438279806634, 529867070532745464
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,2
|
|
|
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.
Liskovets, Valery A. 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
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Walsh, T. R. S., Generating nonisomorphic maps without storing them. SIAM J. Algebraic Discrete Methods 4 (1983), no. 2, 161-178.
T. R. S. Walsh, personal communication.
Wormald, Nicholas C., Counting unrooted planar maps. Discrete Math. 36 (1981), no. 2, 205-225.
|
|
|
LINKS
|
Alois P. Heinz, Table of n, a(n) for n = 0..300
V. A. Liskovets, Enumerative formulae for unrooted planar maps: a pattern, Electron. J. Combin., 11:1 (2004), R88.
|
|
|
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
|
|
|
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}] (* From Jean-François Alcover, after Valery A. Liskovets *)
|
|
|
CROSSREFS
|
Cf. A000168.
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
|
| |
|
|
