Consider the element $(1 2 3)\in A_n$, for a fixed $n$. I am interested to find the set of elements $g\in A_n$ such that $\langle g, (123)\rangle=A_n$. Let call it $G_{(123)}$. My main target is to find $\rho:=|G_{(123)}|$.
Of course, I know, if $n$ is odd, that $\langle (123), (12..n)\rangle=A_n$. If I conjugate $(12..n)$ with $(123)$ iteratively, I obtain other elements that generate with $(123)$ the whole group $A_n$, but there are many others, because the elements obtained in this way have only order $n$.
This way also suggests another way to find all these elements:
- for every possible order $m$ of an element in $A_n$, if $(123)$ generates $A_n$ with an opportune element of this order, than take all of its conjugates with $(123)$ and count them. It will be $\rho=|I|\cdot 3$, where $I$ is the size of the set of all possible orders of $A_n$. Right?
But this way opens up another question: how can I find all possible orders in $A_n$? How many are there?
In addiction, the final task that I want to demonstrate is this: let's call $\rho(n)$ the size of $G_{(123)}$ in $A_n$. Then it will be $O(\rho(n))<O(n!)$.
As YCor pointed out, my argument wasn't right, so here is another attempt (in brief).
Assume that $\langle (1,2,3),g \rangle = A_n$. Then, since $A_n$ is transitive, $g$ is a product of at most three disjoint cycles (counting fixed points as cycles of length 1). To solve the second problem, let's try and get an upper bound on the number of elements in $S_n$ that are a product of at most three cycles.
The number consisting of a single cycle, which must have length $n$, is $(n-1)!$.
The number of $g$ that are a product of two disjoint cycles of lengths $k$ and $(n-k)$ is $n!/(k(n-k))$ when $n \ne 2k$, and half that number when $n=2k$, so an upper bound on the number of all elements that are a product of two cycles is $$n!\sum_{k=1}^{n-1} \frac{1}{k(n-k)} = (n-1)! \sum_{k=1}^{n-1} \left(\frac{1}{k} + \frac{1}{(n-k)}\right) = 2(n-1)!H_{n-1},$$ where $H_n$ is the $n$-th harmonic number (in fact that expression is exactly twice the number of such $g$).
Since $H_n = O(\log n)$, the proportion of such elements in $S_n$ is about $\log n/n = o(1)$.
Similarly, an upper bound for the number of $g$ that are the product of three cycles is $$n!\sum_{i+j+k=n} \frac{1}{ijk} = (n-1)! \sum_{i+j+k=n} \frac{1}{ij}+\frac{1}{jk}+\frac{1}{ik}< 3(n-1)!\sum_{k=1}^{n-2}H_k$$ which (if I have got it right) is $O((n-1)!(\log n)^2)$, and again the proportion of elements in $S_n$ of this form is $o(1)$.