PUERTA | PUERTA-CS-2003 | Pregunta 61

En una permutación a1…..an de n enteros distintos, una inversión es un par (ai, aj) tal que i aj. Si todas las permutaciones son igualmente probables, ¿cuál es el número esperado de inversiones en una permutación elegida al azar de 1…..n?
(A) n(n-1)/2

(B) n(n – 1)/4
(C) n(n + 1)/4
(D) 2n[log2 n]

Respuesta: (B)
Explicación:

There are n(n-1)/2 pairs such that i < j.

For a pair (ai, aj), probability of being inversion is 1/2.

Therefore expected value of inversions = 1/2 * (n(n-1)/2)
                                       = n(n-1)/4

Cuestionario de esta pregunta