# Number of subgroups of a given index of a free group

Given $n,d\in \mathbb{Z}^+$, how many subgroups of index $d$ does the free group of rank $n$ have?

In case $n=1$ the question is trivial, and in case $n=2, d=2$ there are 3 such subgroups. I think I have got a algorithm to solve case $d=2$ for arbitrary $n$. But the general case seems very difficult. For example in case $n=2$ and $d$ a prime number, I don't know how to proceed.

That's my question. Any suggestions will be appreciated. Thanks

This calculation was performed by Marshall Hall Jr. Let $N(d,n)$ be the number of subgroups of index $d$ in the free group of rank $n$. Then
$N(d,n)=d(d!)^{n-1}-\sum_{i=1}^{d-1}((d-i)!)^{n-1}N(i,n)$.
• A more elegant way of stating Hall's result is $\log\sum_{d\geq 0} d!^{n-1} x^d= \sum_{d\geq 1}N(d,n)\frac{x^d}{d}$. See Enumerative Combinatorics, vol. 2, Exercise 5.13 for this and related results. – Richard Stanley Feb 25 '14 at 21:33
This is a very incomplete answer. The case $d=2$ is particular because a subgroup of index 2 is normal. In this case subgroups of order 2 of $F_n$ correspond bijectively to surjective homomorphisms $F_n\rightarrow \mathbb{Z}/2$. Such a map factors through the abelian quotient $\mathbb{Z}^n$, thus there are $2^n-1$ subgroups of index 2 of $F_n$.
In general subgroups of index $d$ of $F_n$ correspond to $n$-uples of permutations $(\sigma _1,\ldots ,\sigma _n)$ in $\mathfrak{S}_d$ such that the subgroup they generate acts transitively on $[1,d]$, up to conjugacy by $\mathfrak{S}_{d-1}$. They also correspond to $d$-sheeted covering of the sphere branched along $\{1,\ldots ,d\}$. This is reminiscent of Hurwitz numbers though it does not seem to be directly related.