Llamamos a una permutación de los enteros $(1,2,\ldots,n)$ $d$ - ordenada si no contiene una subsucesión decreciente de longitud $d$. Demostrar que para cada $d=2,3,\ldots,n$, el número de permutaciones $d$ - ordenadas de $(1,2,\ldots,n)$ es a lo sumo $(d-1)^{2n}$.