A121350 Number of conjugacy class of index n subgroups in PSL_2 (ZZ).

1, 1, 1, 2, 2, 1, 8, 6, 7, 14, 27, 26, 80, 133, 170, 348, 765, 1002, 2176, 4682, 6931, 13740, 31085, 48652, 96682, 217152, 362779, 707590, 1597130, 2789797, 5449439, 12233848, 22245655, 43480188, 97330468, 182619250, 358968639, 800299302, 1542254973, 3051310056, 6783358130

Offset: 0

Author

Samuel A. Vidal, Jul 23 2006

Keywords

• nonn

Comments

Equivalently, the number of isomorphism class of transitive PSL_2(ZZ) actions on a finite set of size n.

Also the number of different connected trivalent diagrams of size n.

Also the number of (r,s) pair of permutations in S_n, up to simultaneous conjugation, which generate a transitive action and for which r is involutive i.e. r^2 = id and s is of weak order three i.e. s^3 = id.

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..1000
• S. A. Vidal, Sur la Classification et le Dénombrement des Sous-groupes du Groupe Modulaire et de leurs Classes de Conjugaison (in French), arXiv:0702223 [math.CO], 2006.
• Qiaochu Yuan, Drawing subgroups of the modular group, Annoying Precision, Blog, November 29, 2015.

Crossrefs

Connected version of A121352.

Unlabeled version of A121355.

Cf. also A005133, A121356, A121357.

Programs

Maple

with(numtheory,mobius) : mu := k -> `if`( k mod 2 = 0, 2/k, 1/k ) : nu := k -> `if`( k mod 3 = 0, 3/k, 1/k ) : u := (k,n) -> add(mu(k)^(n-2*k2)/(n-2*k2)!/k2!/(2*k)^k2,k2=0..floor(n/ 2)) ; v := (k,n) -> add(nu(k)^(n-3*k3)/(n-3*k3)!/k3!/(3*k)^k3,k3=0..floor(n/ 3)) ; N := 100 # For example. add(convert(taylor(log(add(n!*k^n*u(k,n)*v(k,n)*t^(k*n), n = 0..floor (N/k))),t=0,N+1),polynom),k=1..N) : lZF := sort (%,t, ascending) : add(mobius(k)/k*rem(subs(t=t^k,lZF),t^(N+1),t),k=1..N) : sort (%,t, ascending);

Mathematica

max = 37; mu[k_] := If[Mod[k, 2] == 0, 2/k, 1/k]; nu[k_] := If[Mod[k, 3] == 0, 3/k, 1/k]; u[k_, n_] := Sum[ mu[k]^(n - 2*k2) / (((n - 2*k2)!*k2!)*(2*k)^k2), {k2, 0, Floor[n/2]}]; v[k_, n_] := Sum[ nu[k]^(n - 3*k3) / (((n - 3*k3)!*k3!)*(3*k)^k3), {k3, 0, Floor[n/3]}]; lZF[t_] = Sum[ Normal[ Series[ Log[ Sum[n!*k^n*u[k, n]*v[k, n]*t^(k*n), {n, 0, Floor[max/k]}]], {t, 0, max + 1}]], {k, 1, max}]; Rest[ CoefficientList[ Sum[ (MoebiusMu[k]*PolynomialMod[lZF[t^k], t^(max + 1)])/k, {k, 1, max}], t]] (* Jean-François Alcover, Dec 05 2012, translated from Samuel Vidal's Maple program *)

Formula

If A(z) = g.f. of a(n) and B(z) = g.f. of A121352 then A(z) = sum_{k > 0} mu(k)/k log(B(z^k)) (Moebius inversion formula).

Extensions

a(0)=1 prepended and a(38) onwards from Andrew Howroyd, Jan 29 2025