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?

  • 2
    $\begingroup$ 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$.) $\endgroup$ – Lukas Geyer Jan 10 '16 at 4:06
  • 3
    $\begingroup$ @LukasGeyer by $[x^n]\log...$ he means the coefficient of $x^n$ in the power series expansion of $\log...$. $\endgroup$ – Sfarla Jan 10 '16 at 11:38
  • $\begingroup$ @ 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. $\endgroup$ – Geoffrey Critzer Jan 10 '16 at 11:54
  • $\begingroup$ @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$. $\endgroup$ – 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.

  • $\begingroup$ Yes. Thank you. I agree that the formula in the book is correct. $\endgroup$ – Geoffrey Critzer Jan 12 '16 at 11:03
  • $\begingroup$ Cf. Sloane's OEIS A267575 $\endgroup$ – Geoffrey Critzer Jan 17 '16 at 14:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.