IMO 1983 LL FRG25

How many permutations a1, a2, . . . , an of {1, 2, . . ., n} are

imolonglistmathematicsolympiad

IMO 1983 LL FRG25

Origin: FRG

Problem

How many permutations a1, a2, . . . , an of {1, 2, . . ., n} are sorted into increasing order by at most three repetitions of the following operation: Move from left to right and interchange ai and ai+1 whenever ai > ai+1 for i running from 1 up to n −1?