T01 Número médio de inversões em permutações
Seja \(S_N\) o conjunto das permutações de $[N]=\{1,\dots,N\}$. Uma inversão em uma permutação $\sigma\in S_N$ é um par $(i,j)$ com $1\leq i<j\leq N$ tal que $\sigma(i)>\sigma(j)$. Dada uma permutação $\sigma\in S_N$, seja $i(\sigma)$ o número de inversões em $\sigma$.
Determine o número médio $I_N$ de inversões em $\sigma\in S_N$. Isto é, determine \( I_N=|S_N|^{-1}\sum_{\sigma\in S_N}i(\sigma). \)
Sugestão. Considere $S_N$ como um espaço de probabilidade, considerando a distribuição uniforme sobre $S_N$. Para cada $1\leq i<j\leq N$, tome $X_{ij}(\sigma)=1$ se $\sigma(i)>\sigma(j)$ e $X_{ij}(\sigma)=0$ caso contrário. Assim, $X_{ij}$ é a função indicadora do evento $\{\sigma(i)>\sigma(j)\}$. Note que o que se pede neste exercício é o valor esperado $E(X)$ de $X=\sum_{1\leq i<j\leq N}X_{ij}$. Determine $E(X_{ij})$ e use a linearidade da esperança.
Observação. Lembre que há uma folha específica para entrega de exercícios teóricos: