¿Dos permutaciones en$S_n$ generan un subgrupo transitivo de$S_n$?

Question

En la página 139 de Flajolet y Sedgewick Analíticas de la Combinatoria leemos:

"A dos permutaciones $\sigma,\tau$ del mismo tamaño, asociado a un gráfico de $G_{\sigma,\tau}$ cuyo conjunto de vértices es $V=[1\ldots n],$ si $n = |σ| = |τ |,$ y el conjunto de aristas está formado por todos los pares de $(x,\sigma(x)), (x,\tau(x)),$$x\in V.$"

El reclamo es entonces que la probabilidad de que un azar gráfico está conectado es

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

Esto no puede ser correcto. (Creo que el factor de $1/n!$ debe $1/n!^2$) ?

Entiendo que el número de tales gráficos, que están conectados es el número de pares ordenados en $S_n$ que generaría un transitiva grupo.

En Sloane del OEIS A122949 vemos un recuento del número de pares ordenados de $n$-permutaciones que generan transitivo subgrupo. La exponencial de generación de función (egf) es $\log(\sum_{n\geq0} n!x^n).$

Quiero derivar (a través del método simbólico) un feag para el número de tamaño de $2$ (y por lo general, el tamaño de la $k$) de subconjuntos de a $S_n$ que generan transitivo grupo. Cf. A266910. Por la fuerza bruta me las arreglé para conseguir Mathematica para contar el número de subconjuntos de tamaño $3$ $S_n$ $n = 3,4,5.$ son $20,$ $1932,$ y $269040$ respectivamente.

Mi preguntas son: ¿está usted de acuerdo que la declaración hecha en el libro es un error?

Puedo utilizar el feag para la gráfica conectada objetos (pares ordenados en $S_n$ que generan transitivo grupo) para obtener una feag para el tamaño de la $k$ subconjuntos de a $S_n$ que generan transitivo grupo?

Puede BRECHA de verificar los tres términos que he calculado por encima con Mathematica?

Answer 1

La fórmula dada en el libro es realmente correcto. Es fácil calcular "a mano" y que el coeficiente de $n=2$ en el poder formal de la serie de $\log \sum_{n=0}^\infty n! x^n$$\frac32$. La probabilidad de que dos uniformemente al azar de los elementos de $S_2$ generar transitivo subgrupo es $\frac34 = \frac{1}{2!} \frac{3}{2}$, mientras que su modificación daría $\frac{1}{2!^2}\frac{3}{2} = \frac{3}{8}$.

La referencia original para que el resultado en sí es Dixon, John D., La probabilidad de generar el grupo simétrico, de Matemáticas. Z. 110, 1969, 199-205. La prueba (la del Teorema 2 en el papel) es relativamente corto, utiliza el estándar de notación matemática, y llega a la identidad formal $$ \sum_{n=0}^\infty n! X^n = \exp \sum_{i=1}^\infty yo! t_i X^i $$ donde $t_i$ es la probabilidad de que dos uniformemente al azar particiones de $S_i$ generar transitivo subgrupo. Esto es equivalente a la fórmula dada en el libro.