login
Number of conjugacy classes of subgroups of index n in free group of rank 2.
13

%I #75 Apr 04 2023 07:44:24

%S 1,3,7,26,97,624,4163,34470,314493,3202839,35704007,433460014,

%T 5687955737,80257406982,1211781910755,19496955286194,333041104402877,

%U 6019770408287089,114794574818830735,2303332664693034476,48509766592893402121,1069983257460254131272

%N Number of conjugacy classes of subgroups of index n in free group of rank 2.

%C Number of (unlabeled) dessins d'enfants with n edges. A dessin d'enfant ("child's drawing") by A. Grothendieck, 1984, is a connected bipartite multigraph with properly bicolored nodes (w and b) in which a cyclic order of the incident edges is assigned to every node. For n=2 these are w--b--w, b--w--b and w==b. - _Valery A. Liskovets_, Mar 17 2005

%C Also (apparently), a(n+1) = number of sensed hypermaps with n darts on a surface of any genus (see Walsh 2012). - _N. J. A. Sloane_, Aug 01 2012

%C Response from Timothy R. Walsh, Aug 01 2012: The conjecture in the previous comment is true. A combinatorial map is a connected graph, loops and multiple edges allowed, in which a cyclic order of the incident edge-ends is assigned to every node. The equivalence between combinatorial maps and topological maps was conjectured by several researchers and finally proved by Jones and Singerman. In my 1975 paper "Generating nonisomorphic maps without storing them", I established a genus-preserving bijection between hypermaps with n darts, w vertices and b edges and properly bicolored bipartite maps with n edges, w white vertices and b black vertices. A bipartite map can't have any loops; so a combinatorial bipartite map is a multigraph and it suffices to impose a cyclic order of the edges, rather than the edge-ends, incident to each node. Thus it is just the child's drawing described above by Liskovets.

%D R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.13(c), pp. 76, 112.

%H Alois P. Heinz, <a href="/A057005/b057005.txt">Table of n, a(n) for n = 1..450</a>

%H M. Deryagina, <a href="ftp://ftp.pdmi.ras.ru/pub/publicat/znsl/v446/p031.pdf">On the enumeration of hypermaps which are self-equivalent with respect to reversing the colors of vertices</a>, Preprint 2016.

%H J. B. Geloun and S. Ramgoolam, <a href="http://arxiv.org/abs/1307.6490">Counting Tensor Model Observables and Branched Covers of the 2-Sphere</a>, arXiv preprint arXiv:1307.6490 [hep-th], 2013.

%H Paawan Jethva, <a href="https://vrs.amsi.org.au/wp-content/uploads/sites/92/2023/03/jethva_paawan_vrs-report.pdf">Exploring the Euler Characteristics of Dessins d'Enfants</a>, Univ. Adelaide (Australia, 2023).

%H G. A. Jones and D. Singerman, <a href="http://dx.doi.org/10.1112/plms/s3-37.2.273">Theory of maps on orientable surfaces</a>, Proc. London Math. Soc. (3) 37:2 (1978), 273-307.

%H J. H. Kwak and J. Lee, <a href="https://doi.org/10.1002/(SICI)1097-0118(199610)23:2&lt;105::AID-JGT1&gt;3.0.CO;2-X">Enumeration of connected graph coverings</a>, J. Graph Th., 23 (1996), 105-109.

%H J. H. Kwak and J. Lee, <a href="http://com2mac.postech.ac.kr/resorce/Lecture_text.htm">Enumeration of graph coverings and surface branched coverings</a>, Lecture Note Series 1 (2001), Com^2MaC-KOSEF, Korea. See chapter 3.

%H V. A. Liskovets, <a href="http://dx.doi.org/10.1023/A:1005950823566">Reductive enumeration under mutually orthogonal group actions</a>, Acta Applic. Math., 52 (1998), 91-120.

%H Carlos I. Pérez-Sánchez, <a href="https://arxiv.org/abs/1608.08134">The full Ward-Takahashi Identity for colored tensor models</a>, arXiv preprint arXiv:1608.08134 [math-ph], 2016.

%H M. Planat, A. Giorgetti, F. Holweck, and M. Saniga, <a href="https://arxiv.org/abs/1310.4267">Quantum contextual finite geometries from dessins d'efants</a>, arXiv:1310.4267 [quant-ph], 2013-2015.

%H P. Vrana, <a href="https://doi.org/10.1088/1751-8113/44/22/225304">On the algebra of local unitary invariants of pure and mixed quantum states</a>, J. Phys A: Math. Theor. 44 (2011) 225304 doi:10.1088/1751-8113/44/22/225304, Table 2.

%H Timothy R. Walsh, <a href="http://www.info2.uqam.ca/~walsh_t/papers/GENERATING NONISOMORPHIC.pdf">Space-efficient generation of nonisomorphic maps and hypermaps</a>

%H Timothy R. Walsh, <a href="http://dx.doi.org/10.1137/0604018">Generating nonisomorphic maps without storing them</a>, SIAM J. Algebraic Discrete Methods 4 (1983), no. 2, 161-178.

%H Timothy R. Walsh, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Walsh/walsh3.html">Space-Efficient Generation of Nonisomorphic Maps and Hypermaps</a>, J. Int. Seq. 18 (2015) # 15.4.3.

%H L. Zapponi, <a href="http://www.ams.org/notices/200307/index.html">What is a dessin d'enfant?</a>, Notices AMS, 50:7, 2003, 788-789.

%H <a href="/index/Gre#groups">Index entries for sequences related to groups</a>

%F prod_{n>0} (1-x^n)^{-a(n)} = prod_{i>0} sum_{j>=0} j!*i^j*x^{i*j}. (Liskovets) - _Valery A. Liskovets_, Mar 17 2005 ... and both sides = sum_{j>=0} A110143(j)*x^j . - _R. J. Mathar_, Oct 18 2012

%F a(n) ~ n! * (1 - 1/n - 1/n^2 - 4/n^3 - 23/n^4 - 171/n^5 - 1542/n^6 - 16241/n^7 - 194973/n^8 - 2622610/n^9 - 39027573/n^10 - ...), for the coefficients see A113869. - _Vaclav Kotesovec_, Aug 09 2019

%t f[1] = {a[0] -> 0, a[1] -> 1};

%t f[max_] := f[max] = (p1 = Product[(1 - x^n)^(-a[n]), {n, 0, max}]; p2 = Product[Sum[j!*If[j == 0, 1, i^j]*x^(i*j), {j, 0, max}], {i, 0, max}];

%t s = Series[p1 - p2 /. f[max - 1], {x, 0, max}] // Normal // Expand;

%t sol = Thread[CoefficientList[s, x] == 0] // Solve // First;

%t Join[f[max - 1], sol]);

%t Array[a, 22] /. f[22] (* _Jean-François Alcover_, Mar 11 2014, updated Jan 01 2021 *)

%Y Cf. A057004-A057013. Inverse Euler transform of A110143.

%K nonn

%O 1,2

%A _N. J. A. Sloane_, Sep 09 2000

%E More terms from Francisco Salinas (franciscodesalinas(AT)hotmail.com), Dec 25 2001