[go: up one dir, main page]
login
The OEIS is supported by the many generous donors to the OEIS Foundation.
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
Search: a069727 -id:a069727
Displaying 1-7 of 7 results found.
page 1
     Sort: relevance | references | number | modified | created      Format: long | short | data
A090371
Number of unrooted planar 2-constellations with n digons. Also number of n-edge unrooted planar Eulerian maps with bicolored faces.
+10
10
1, 3, 6, 20, 60, 291, 1310, 6975, 37746, 215602, 1262874, 7611156, 46814132, 293447817, 1868710728, 12068905911, 78913940784, 521709872895, 3483289035186, 23464708686960, 159346213738020, 1090073011199451, 7507285094455566, 52021636161126702
(list; graph; refs; listen; history; text; internal format)
OFFSET
1,2
COMMENTS
a(n) is also the number of unrooted planar hypermaps with n darts up to orientation-preserving homeomorphism (darts are semi-edges in the particular case of ordinary maps). - Valery A. Liskovets, Apr 13 2006
LINKS
R. J. Mathar, Table of n, a(n) for n = 1..100
M. Bousquet-Mélou and G. Schaeffer, Enumeration of planar constellations, Adv. in Appl. Math. v.24 (2000), 337-368.
A. Mednykh and R. Nedela, Counting unrooted hypermaps on closed orientable surface, 18th Intern. Conf. Formal Power Series & Algebr. Comb., Jun 19, 2006, San Diego, California (USA).
A. Mednykh and R. Nedela, Enumeration of unrooted hypermaps of a given genus, Discr. Math., 310 (2010), 518-526. [From N. J. A. Sloane, Dec 19 2009]
A. Mednykh and R. Nedela, Recent progress in enumeration of hypermaps, J. Math. Sci., New York 226, No. 5, 635-654 (2017) and Zap. Nauchn. Semin. POMI 446, 139-164 (2016), table 2.
Timothy R. Walsh, Space-efficient generation of nonisomorphic maps and hypermaps
Timothy R. Walsh, Space-Efficient Generation of Nonisomorphic Maps and Hypermaps, J. Int. Seq. 18 (2015) # 15.4.3.
EXAMPLE
The 3 Eulerian maps with 2 edges are the digon and two figure eight graphs ("8") in which both loops are colored, resp., black or white.
MAPLE
A090371 := proc(n)
local s, d;
if n=0 then
1 ;
else
s := -2^n*binomial(2*n, n);
for d in numtheory[divisors](n) do
s := s+ numtheory[phi](n/d)*2^d*binomial(2*d, d)
od;
3/(2*n)*(2^n*binomial(2*n, n)/((n+1)*(n+2))+s/2);
fi;
end proc:
MATHEMATICA
h0[n_] := 3*2^(n-1)*Binomial[2*n, n]/((n+1)*(n+2)); a[n_] := (h0[n] + DivisorSum[n, If[#>1, EulerPhi[#]*Binomial[n/#+2, 2]*h0[n/#], 0]&])/n; Array[a, 30] (* Jean-François Alcover, Dec 06 2015, adapted from PARI *)
PROG
(PARI) h0(n) = 3*2^(n-1)*binomial(2*n, n)/((n+1)*(n+2));
a(n) = (h0(n) + sumdiv(n, d, (d>1)*eulerphi(d)*binomial(n/d+2, 2)*h0(n/d)))/n; \\ Michel Marcus, Dec 11 2014
CROSSREFS
Cf. A000257, A069727, A090372, A118094.
KEYWORD
easy,nonn
AUTHOR
Valery A. Liskovets, Dec 01 2003
EXTENSIONS
More terms from Michel Marcus, Dec 11 2014
STATUS
approved
A069724
Number of nonisomorphic unrooted unicursal planar maps with n edges (unicursal means that exactly two vertices are of odd valency; there is an Eulerian path).
+10
7
1, 2, 9, 38, 214, 1253, 7925, 51620, 346307, 2365886, 16421359, 115384738, 819276830, 5868540399, 42357643916, 307753571520, 2249048959624, 16520782751969, 121915128678131, 903391034923548, 6719098772562182
(list; graph; refs; listen; history; text; internal format)
OFFSET
1,2
LINKS
G. C. Greubel, Table of n, a(n) for n = 1..1000
V. A. Liskovets and T. R. S. Walsh, Enumeration of Eulerian and unicursal planar maps, Discr. Math., 282 (2004), 209-221.
FORMULA
There is an easy formula.
a(n) ~ 8^(n-1) / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Aug 28 2019
MATHEMATICA
a[n_] := 1/(2 n) DivisorSum[n, If[OddQ[n/#], EulerPhi[n/#] 2^(#-2) Binomial[2 #, #], 0]&] + If[OddQ[n], 2^((n-3)/2) Binomial[n-1, (n-1)/2], 2^((n-6)/2) Binomial[n, n/2]]; Array[a, 21] (* Jean-François Alcover, Sep 18 2016 *)
CROSSREFS
Cf. A069720, A069727, A005470.
KEYWORD
easy,nice,nonn
AUTHOR
Valery A. Liskovets, Apr 07 2002
STATUS
approved
A103939
Number of unrooted Eulerian n-edge maps in the plane (planar with a distinguished outside face).
+10
3
1, 1, 3, 8, 32, 136, 722, 3924, 22954, 138316, 860364, 5472444, 35503288, 234070648, 1564945158, 10589356592, 72412611194, 499788291616, 3478059566250, 24383023246284, 172074483068320, 1221654305104920, 8720583728414354, 62560709120463028, 450854177292364660
(list; graph; refs; listen; history; text; internal format)
OFFSET
0,3
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*binomial(2n, n)/(n+1) + Sum_{0<k<n, k|n} phi(n/k)*2^k*binomial(2k, k)) where phi is the Euler function A000010.
MATHEMATICA
a[n_] := (1/(2n)) (2^n Binomial[2n, n]/(n+1) + Sum[Boole[0<k<n] EulerPhi[ n/k] 2^k Binomial[2k, k], {k, Divisors[n]}]);
Array[a, 20] (* Jean-François Alcover, Aug 28 2019 *)
PROG
(PARI) a(n)={if(n==0, 1, sumdiv(n, d, if(d<n, 1, 1/(n+1)) * eulerphi(n/d) * 2^d * binomial(2*d, d))/(2*n))} \\ Andrew Howroyd, Mar 29 2021
CROSSREFS
Cf. A052701, A103940, A069727.
KEYWORD
easy,nonn
AUTHOR
Valery A. Liskovets, Mar 17 2005
EXTENSIONS
a(0)=1 prepended and terms a(21) and beyond from Andrew Howroyd, Mar 29 2021
STATUS
approved
A103940
Number of unrooted bipartite n-edge maps in the plane (planar with a distinguished outside face).
+10
3
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
(list; graph; refs; listen; history; text; internal format)
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.
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
A069725
Number of nonisomorphic unrooted unicursal planar maps with n edges and two vertices of valency 1 (unicursal means that exactly two vertices are of odd valency; there is an Eulerian path).
+10
2
1, 1, 3, 11, 62, 342, 2152, 13768, 91800, 622616, 4301792, 30100448, 213019072, 1521473984, 10954616064, 79420280064, 579300888960, 4248201302400, 31302536066560, 231638727063040
(list; graph; refs; listen; history; text; internal format)
OFFSET
1,3
COMMENTS
There is an easy formula.
LINKS
Table of n, a(n) for n=1..20.
V. A. Liskovets and T. R. S. Walsh, Enumeration of Eulerian and unicursal planar maps, Discr. Math., 282 (2004), 209-221.
MATHEMATICA
a[1] = a[2] = 1;
a[n_] := With[{m = Floor[(n+1)/2]}, 1/n 2^(n-3) Binomial[2n-2, n-1] + 2^(m-3) Binomial[2m-2, m-1]];
Array[a, 20] (* Jean-François Alcover, Aug 28 2019 *)
CROSSREFS
Cf. A069727, A003645, A069732.
KEYWORD
easy,nonn
AUTHOR
Valery A. Liskovets, Apr 07 2002
STATUS
approved
A090375
Number of unrooted Eulerian maps with bicolored faces which are self-isomorphic under reversing the colors.
+10
1
1, 1, 2, 4, 8, 17, 40, 93, 224, 538, 1344, 3352, 8448, 21573, 54912, 143037, 366080, 968083, 2489344, 6664856, 17199104, 46515759, 120393728, 328382874, 852017152, 2340706462, 6085836800, 16822999572, 43818024960, 121777594508, 317680680960, 887053276477
(list; graph; refs; listen; history; text; internal format)
OFFSET
1,3
LINKS
Table of n, a(n) for n=1..32.
M. Deryagina, On the enumeration of hypermaps which are self-equivalent with respect to reversing the colors of vertices, Preprint 2016.
V. Liskovets, Some easily derivable integer sequences, J. Integer Seq., v.3 (2000), Article 00.2.2.
V. A. Liskovets, Enumerative formulas for unrooted planar maps: a pattern, Electron. J. Combin., 11:1 (2004), R88.
FORMULA
a(n) = 2*A069727(n) - A090371(n).
a(2k+1) = 2^k*Catalan(k) = A052701(k+1).
MATHEMATICA
A069727[n_] := (1/(2n)) (3*2^(n - 1) Binomial[2 n, n]/((n + 1) (n + 2)) + Sum[EulerPhi[n/k] d[n/k] 2^(k - 2) Binomial[2 k, k], {k, Most[Divisors[n]]}]) + q[n]; A069727[0] = 1;
q[n_?EvenQ] := 2^((n - 4)/2) Binomial[n, n/2]/(n + 2); q[n_?OddQ] := 2^((n - 1)/2) Binomial[(n - 1), (n - 1)/2]/(n + 1);
d[n_] := 4 - Mod[n, 2];
h0[n_] := 3*2^(n - 1) Binomial[2n, n]/((n + 1)(n + 2));
A090371[n_] := (h0[n] + DivisorSum[n, If[# > 1, EulerPhi[#]*Binomial[n/# + 2, 2] h0[n/#], 0] &])/n;
a[n_] := 2 A069727[n] - A090371[n];
Array[a, 32] (* Jean-François Alcover, Aug 28 2019 *)
PROG
(PARI) h0(n) = 3*2^(n-1)*binomial(2*n, n)/((n+1)*(n+2));
a090371(n) = (h0(n) + sumdiv(n, d, (d>1)*eulerphi(d)*binomial(n/d+2, 2)*h0(n/d)))/n;
d(n) = if (n%2, 3, 4);
q(n) = if (n%2, 2^((n-1)/2)*binomial(n-1, (n-1)/2)/(n+1), 2^((n-4)/2)*binomial(n, n/2)/(n+2));
a069727(n) = if (n==0, 1, q(n) + (3*2^(n-1)*binomial(2*n, n)/((n+1)*(n+2)) + sumdiv(n, k, (k!=n)*eulerphi(n/k)*d(n/k)*2^(k-2)*binomial(2*k, k)))/(2*n));
a(n) = 2*a069727(n) - a090371(n); \\ Michel Marcus, Dec 11 2014
CROSSREFS
Cf. A052701, A069727, A090371.
KEYWORD
easy,nonn
AUTHOR
Valery A. Liskovets, Dec 01 2003
EXTENSIONS
More terms from Michel Marcus, Dec 11 2014
STATUS
approved
A069730
Number of nonisomorphic unrooted unicursal planar maps with n edges.
+10
0
1, 2, 4, 13, 50, 248, 1407, 8600, 55154, 365292, 2473956, 17053468, 119191992, 842688120, 6015275094, 43292026736, 313788095994, 2288506113056, 16781638172458, 123656774440396, 915123392599456
(list; graph; refs; listen; history; text; internal format)
OFFSET
0,2
COMMENTS
Unicursal (in a broad sense) means that no more than two vertices are of odd valency (that is, maps possessing an Eulerian path).
LINKS
Table of n, a(n) for n=0..20.
V. A. Liskovets and T. R. S. Walsh, Enumeration of Eulerian and unicursal planar maps, Discr. Math., 282 (2004), 209-221.
FORMULA
a(n) = A069727(n) + A069724(n).
MATHEMATICA
A069724[n_] := 1/(2 n) DivisorSum[n, If[OddQ[n/#], EulerPhi[n/#] 2^(# - 2) Binomial[2 #, #], 0] &] + If[OddQ[n], 2^((n - 3)/2) Binomial[n - 1, (n - 1)/2], 2^((n - 6)/2) Binomial[n, n/2]];
A069727[n_] := (1/(2 n))*(3*2^(n - 1)*Binomial[2 n, n]/((n + 1)*(n + 2)) + Sum[EulerPhi[n/k]*d[n/k]*2^(k - 2)*Binomial[2 k, k], {k, Most[Divisors[n]]}]) + q[n]; A069727[0] = 1;
q[n_?EvenQ] := 2^((n - 4)/2)*Binomial[n, n/2]/(n + 2); q[n_?OddQ] := 2^((n - 1)/2)*Binomial[(n - 1), (n - 1)/2]/(n + 1);
d[n_] := 4 - Mod[n, 2];
a[n_] := A069727[n] + A069724[n];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Aug 28 2019 *)
CROSSREFS
Cf. A069727, A069724.
KEYWORD
easy,nonn
AUTHOR
Valery A. Liskovets, Apr 07 2002
STATUS
approved
page 1

Search completed in 0.007 seconds

Lookup Welcome Wiki Register Music Plot 2 Demos Index WebCam Contribute Format Style Sheet Transforms Superseeker Recents
The OEIS Community
Maintained by The OEIS Foundation Inc.
Last modified November 7 00:48 EST 2024. Contains 377523 sequences.
License Agreements, Terms of Use, Privacy Policy