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