|
|
A006384
|
|
Number of planar maps with n edges.
(Formerly M1281)
|
|
5
|
|
|
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.
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
|
|
|
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}] (* Jean-François Alcover, after Valery A. Liskovets *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|