Problem:
Call a permutation a1​,a2​,…,an​ of the integers 1,2,…,n quasi-increasing if ak​≤ak+1​+2 for each 1≤k≤n−1. For example, 53421 and 14253 are quasi-increasing permutations of the integers 1,2,3,4,5, but 45123 is not. Find the number of quasi-increasing permutations of the integers 1,2,…,7.
Solution:
Let Sn​ be the number of quasi-increasing permutations of 1,2,…,n. It is easy to check that S1​=1,S2​=2, and S3​=6. For n≥3,Sn​=3Sn−1​ is proved as follows.
First note that if a1​,a2​,…,an−1​ is a quasi-increasing permutation of 1,2,…, n−1, then one can construct a quasi-increasing permutation of 1,2,…,n by placing the n immediately in front of n−1, immediately in front of n−2, or after an−1​. If n is placed in any other position, then it will be followed by an integer k with 1≤k≤n−3 so n≤k+2 will not be true. Thus every quasiincreasing permutation of 1,2,…,n−1 leads to 3 quasi-increasing permutations of 1,2,…,n.
Conversely, suppose that we have a quasi-increasing permutation a1​,a2​,…,an​ of 1,2,…,n. If an​=n or a1​=n, then removing an​ results in a quasi-increasing permutation of 1,2,…,n−1. If n=ak​,kî€ =1,n, then ak+1​=n−1 or ak+1​=n−2. In either case
ak−1​<n≤ak+1​+2
so removing n again results in a quasi-increasing permutation of 1,2,…,n−1. Furthermore, as the previous paragraph showed, for each quasi-increasing permutation π of 1,2,…,n−1, there are exactly 3 quasi-increasing permutations of 1,2,…,n that result in π when n is removed. This completes the proof that Sn​=3Sn−1​ for n≥3.
Hence Sn​=3n−2S2​=2⋅3n−2 for n≥3. In particular, S7​=2⋅35=486​.
The problems on this page are the property of the MAA's American Mathematics Competitions