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

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?

• As to the mathematics, what is the $x$ in the probability formula? Also, $n$ appears both outside and inside the sum (which diverges for all nonzero $x$.) – Lukas Geyer Jan 10 '16 at 4:06
• @LukasGeyer by $[x^n]\log...$ he means the coefficient of $x^n$ in the power series expansion of $\log...$. – Sfarla Jan 10 '16 at 11:38
• @ Lukas Geyer. If you google "formal power series" there is a short answer in the Math World article and a more detailed answer in the Wikipedia article. – Geoffrey Critzer Jan 10 '16 at 11:54
• @GeoffreyCritzer, I think it would be helpful to briefly mention in the question what $[x^n]$ means. I'm familiar with this notation, but I didn't recognize it until I saw Sfarla's comment. It might also be helpful to rename the formal variable $x$, since $x$ is used in the previous paragraph to denote an element of $V$. – Vectornaut Jan 11 '16 at 20:21

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.