Una recurrencia más agradable para los polinomios eulerianos.

Question

Estaba estudiando el tema de los polinomios eulerianos. Estoy asumiendo la definición de que el polinomio euleriano está definido por $C_n(t)=\sum_{\pi\in S_n}t^{1+d(\pi)}$ donde $d(\pi)$ es el número de descensos.

Los polinomios eulerianos satisfacen una recurrencia estándar $C_n(t)=t(1-t)C'_{n-1}(t)+ntC_{n-1}(t)$ . Aparentemente también satisfacen la relación más estética $$ C_n(t)=tC'_{n-1}(t)+t^nC'_{n-1}(t^{-1}). $$

La función generadora en $t^{-1}$ es problemático para mí. ¿Cómo se puede derivar esta otra relación de recurrencia? Muchas gracias,

Answer 1

Escriba a $C_{n-1}(t) = \sum_{k=1}^{n-1} a_k t^k$ y mira exactamente cómo contribuye cada término en $C_n(t)$ :

Su primera relación de recurrencia dice : $C_n(t) = t(1-t)C'_{n-1}(t)+ntC_{n-1}t = (t-t^2)(\sum_{k=1}^{n-1} k a_k t^{k-1}) + nt(\sum_{k=1}^{n-1} a_k t^k) \\ = \sum_{k=1}^{n-1} (k-kt+nt)a_k t^k = \sum_{k=1}^{n-1} (k + (n-k)t)a_k t^k $

Esencialmente, cada término $t^k$ se convierte en $k t^k + (n-k) t^{k+1}$ La segunda relación de recurrencia intenta mostrar esta separación de aspecto simétrico :

$tC'_{n-1}(t) = \sum_{k=1}^{n-1} k a_k t^k$ Recuperamos la primera mitad, lo que nos deja con la otra mitad.

Como es lo mismo pero en el otro sentido, hay que cambiar los coeficientes del polinomio, diferenciar, ajustar la potencia de $t$ y luego cámbialos de nuevo. De hecho, como los polinomios de Euler son simétricos, $a_k = a_{n-k}$ podemos saltarnos el primer paso. El último paso de cambio explica por qué se ve que $C'_{n-1}(t^{-1})$ :

$\sum_{k=1}^{n-1} (n-k) a_k t^{k+1} = \sum_{k=1}^{n-1} (n-k) a_{n-k} t^{k+1} = \sum_{k=1}^{n-1} k a_k t^{n-k+1} \\ = t^n \sum_{k=1}^{n-1} k a_k (t^{-1})^{k-1} = t^n C'_{n-1}(t^{-1})$ .

Aunque utilice $t^{-1}$ , $t^n C'_{n-1}(t^{-1})$ sigue siendo un polinomio en $t$ . Se trata de un sencillo truco para invertir los coeficientes de un polinomio. Por ejemplo, afirmando que los polinomios son simétricos ( $a_k = a_{n-k}$ ), es lo mismo que afirmar que $C_n(t) = t^{n+1} C_n(t^{-1})$