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)$.
One can prove this inductively by analysing permutation groups as in abx's answer, or alternatively by thinking about covering spaces of graphs---see the answers to this question on MSE for a few more details.
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.
