MathDB

Number of decreasing subsequences of 1,2,...,n permutation

Source: XVIII Olimpíada Matemática Rioplatense (2009)

July 23, 2011

combinatorics unsolvedcombinatorics

Problem Statement

Call a permutation of the integers

(1,2,\ldots,n)

d

-ordered if it does not contains a decreasing subsequence of length

d

. Prove that for every

d=2,3,\ldots,n

, the number of

d

-ordered permutations of

(1,2,\ldots,n)

is at most

(d-1)^{2n}