Do two permutations in $S_n$ generate a transitive subgroup of $S_n$?

Question

On page 139 of Flajolet and Sedgewick's Analytic Combinatorics we read:

"To two permutations $\sigma,\tau$ of the same size, associate a graph $G_{\sigma,\tau}$ whose set vertices is $V=[1\ldots n],$ if $n = |σ| = |τ |,$ and set of edges is formed of all the pairs $(x,\sigma(x)), (x,\tau(x)),$ for $x\in V.$"

The claim is then made that the probability that such a random graph is connected is

$$\frac1{n!}[x^n]\log\left(\sum_{n\geq0} n!x^n\right).$$

This cannot be correct. (I think the factor of $1/n!$ should be $1/n!^2$) ?

I understand that the number of such graphs that are connected is the number of ordered pairs in $S_n$ that would generate a transitive group.

In Sloane's OEIS A122949 we see a count of the number of ordered pairs of $n$-permutations that generate a transitive subgroup. The exponential generating function (egf) is $\log(\sum_{n\geq0} n!x^n).$

I want to derive (via the symbolic method) an egf for the number of size $2$ (and then generally size $k$) subsets of $S_n$ that generate a transitive group. Cf. A266910. By brute force I managed to get Mathematica to count the number of such subsets of size $3$ in $S_n$ for $n = 3,4,5.$ They are $20,$ $1932,$ and $269040$ respectively.

My specific questions are: Do you agree that the statement made in the book is an error?

Can I utilize the egf for the connected graph objects (ordered pairs in $S_n$ that generate a transitive group) to derive an egf for size $k$ subsets of $S_n$ that generate a transitive group?

Can GAP verify the three terms that I have computed above with Mathematica?

Answer 1

The formula given in the book is actually correct. It is easy to calculate "by hand" that the coefficient of $n=2$ in the formal power series of $\log \sum_{n=0}^\infty n! x^n$ is $\frac32$. The probability that two uniformly random elements of $S_2$ generate a transitive subgroup is $\frac34 = \frac{1}{2!} \frac{3}{2}$, whereas your modification would give $\frac{1}{2!^2}\frac{3}{2} = \frac{3}{8}$.

The original reference for the result itself is Dixon, John D., The probability of generating the symmetric group, Math. Z. 110, 1969, 199–205. The proof (of Theorem 2 in the paper) is relatively short, uses standard mathematical notation, and arrives at the formal identity $$ \sum_{n=0}^\infty n! X^n = \exp \sum_{i=1}^\infty i! t_i X^i $$ where $t_i$ is the probability that two uniformly random partitions from $S_i$ generate a transitive subgroup. This is equivalent to the formula given in the book.