Planteamiento del problema
Esta es la parte que creo que es analizable.
La distancia de Cayley del elemento $g_1$ a $g_2$ es el menor número de transposiciones que transforma $g_1$ a $g_2$ . Es invariable a la izquierda y a la derecha, por lo que \begin{equation} d( g_1, g_2) = d( I, g_1^{-1} g_2 ) = d( I, g_2 g_1^{-1} ) \end{equation} La distancia al elemento de identidad es sólo $ n$ menos el número de ciclos en la notación de ciclo.
Por definición, la distancia satisface la desigualdad del triángulo \begin{equation} d( g_1, g_2 ) + d( g_1, g_3 ) \ge d( g_2, g_3 ) \end{equation} En particular, \begin{equation} d( I, g ) + d( I, \tau g ) \ge d( g, \tau g ) = d( I, \tau) \end{equation}
Ahora para un elemento fijo $\tau = (123\cdots n )$ Quiero encontrar el número de elementos $a_n$ (en términos de $n$ ) que saturan la desigualdad del triángulo, \begin{equation} a_n = \text{Cardinality}\{ g \in S_n | d( I, g) + d( I, \tau g ) = d( I, \tau) = n - 1 \} \end{equation}
Durante los primeros $n$ , $a_{2} = 2, a_3 = 5, a_4 = 14$ .
ACTUALIZACIÓN
Como señaló @san, $a_n$ es probable que sea el Número catalán . Así que lo comprobé numéricamente usando sage: hasta $n = 10$ $a_n$ ¡coincide con el número catalán!
\begin{equation} \begin{aligned} a_2 &= 2,\quad a_3 = 5, \quad a_4 = 14,\quad a_5 = 42,\quad a_6 = 132, \\ a_7 &= 429, \quad a_8 = 1430,\quad a_9 = 4862,\quad a_{10} = 16796 \end{aligned} \end{equation}
Además, su derivada es la deseada $\frac{1}{2}$ , \begin{equation} \partial_n \frac{2n!}{n!(n+1)!}\Big|_{n = 1} = \partial_n \frac{1}{n(n+1) B( n, n+ 1)}\Big|_{n = 1} = \frac{1}{2} \end{equation}
Así que creo que esto debe ser una suposición exacta, y vamos a buscar una prueba.
@san sugirió probar \begin{equation} a_{n, n-k} = \text{Cardinality}\{g \in S_n | d( I, g ) = n-k, d( I, \tau g ) = k - 1 \} = \frac{1}{k} {n \choose k - 1 } {n - 1 \choose k-1} \end{equation}
tal que \begin{equation} a_n = \sum_{k=1}^n a_{n, n-k} = \sum_{k=1}^n \frac{1}{k} {n \choose k - 1 } {n - 1 \choose k-1} = \frac{2n!}{n! (n+1)!} = C_n \end{equation}
Tal vez una ruta recursiva para demostrar \begin{equation} a_n = \sum_{i=0}^{n-1} a_{i} a_{n-1-i} \end{equation} es posible.
Si $g$ puede descomponerse como una permutación de la primera $k$ elementos $g_1$ y la permutación del resto $n-k$ elementos $g_2$ y, a continuación, establecer $\tau_1$ y $\tau_2$ para ser la operación de desplazamiento en estos correspondientes grupos de permutación más pequeños, tenemos \begin{equation} d(I, g ) + d(I, \tau g ) = d(I, g_1) + d( I, \tau_1 g_1) + d(I, g_2) + d(I, \tau_2 g_2 ) + 1 \le k-1 + n-k-1 + 1 = n-1 \end{equation} La única manera de saturar el límite es que ambos $g_1$ y $g_2$ estatuir el límite en el grupo de permutación más pequeño, por lo tanto en para estos $g$ el coeficiente superior es $a_k a_{n-k}$ .
Pero obviamente la elección de un pivote diferente $k$ sobrecostes, por lo que todavía no puedo construir una fórmula recursiva que relacione $a_n$ y $\sum_k a_k a_{n-k}$ .
Puesto original: un problema más general
Estaba buscando la expresión analítica (necesito tomar la derivada) del siguiente polinomio \begin{equation} f_n(x, y) = \sum_{g \in S_n} x^{\chi(g)} y^{\chi( \tau g )} \end{equation} donde $g$ se toma del grupo de permutación $S_n$ el exponente $\chi(g)$ son el número de ciclos en la notación de ciclo de $g$ y $\tau$ es un elemento fijo en $S_n$ : $\tau = (123\cdots n )$ es decir, pone $1$ al final y desplazar cada letra hacia delante.
Tal vez no debería llamarse función generadora, pero no tengo un nombre apropiado para ella. Algunos ejemplos aclararán la definición. Cuando $n = 4$ , tomando $g = (12)(3)(4)$ hay 3 ciclos (incluyendo el ciclo de longitud 1), por lo que $\chi( g ) = 3$ . Por otro lado, \begin{equation} \tau g = (1234) \cdot (12) (3)(4) = (134)(2) \end{equation} así que $\chi( \tau g ) = 2$ el monomio correspondiente de $g$ es $x^3 y^2$ . Sumando sobre los monomios de todos los elementos de $S_n$ da $f_n(x, y)$ .
He calculado el caso de $n = 2,3,4$ los resultados son \begin{equation} \begin{aligned} f_2(x,y) &= x^2 y + x y^2 \\ f_3(x,y) &= x^3 y + 3x^2 y^2 + x y^3 + xy \\ f_4(x,y) &= x^4 y + 6 x^3 y^2 + 6x^2 y^3 + x y^4 + 5 x^2 y + 5 x y^2 \end{aligned} \end{equation}
Sería ideal tener la expresión analítica de todos los coeficientes, pero me interesa sobre todo el coeficiente de mayor potencia de $f_n(x,x)$ \begin{equation} f_n(x,x) = a_{n} x^{n+1} + \cdots \end{equation} Me gustaría obtener la expresión analítica de $a_n$ que es el mismo $a_n$ en el planteamiento del problema.
$\chi(g)$ y la distancia de Cayley
He leído un puesto relevante sobre el número de ciclos y aprendió que la función $\chi(g)$ está relacionada con la distancia de Cayley \begin{equation} d( I, g ) = n - \chi( g ) \end{equation}
El poder de $x$ en $f_n(x,x)$ es \begin{equation} \begin{aligned} \chi( g) + \chi(\tau g ) &= 2n - d( I, g ) - d( I, \tau g ) \\ &\le 2n - d( g, \tau g ) = 2n - d( I, g^{-1} \tau g ) \\ &= 2n - d(I, \tau) = n + \chi(\tau) = n +1 \end{aligned} \end{equation} por lo que los coeficientes $a_n$ es sólo el número de elementos que saturan la desigualdad del triángulo de la distancia de Cayley \begin{equation} d( I, g ) + d( I , \tau g ) = d( I, g^{-1} \tau g ) = n - 1 \end{equation}
Función generadora
De este Puesto de MO hay una buena fórmula para $f_n( x, 1 )$ que es \begin{equation} f_n( x, 1 ) = \sum_{g\in S_n} x^{\chi(g )} = \prod_{k=1}^{n-1} (x + k ) \end{equation} y hay una bonita prueba biyectiva aquí
EDITAR
Obtuve a través de un enfoque independiente no riguroso que $\partial_n a_n\Big|_{n=1} = \frac{1}{2}$ pero aún no conozco la expresión analítica para $a_n$
