Q3 Matemática  (Rioplatense Mathematical Olympiad, Level 3 2009)

Chame uma permutação dos inteiros $(1,2,\dots ,n)$ $d$-ordered se não contiver uma subsequência decrescente de comprimento $d$. Prove que para cada $d=2,3,\dots ,n$, o número de permutações $d$-ordenadas de $(1,2,\dots ,n)$ é no máximo $(d-1{)}^{2n}$.