Problem:
Find the number of permutations of 1,2,3,4,5,6 such that for each k with 1≤k≤5, at least one of the first k terms of the permutation is greater than k.
Solution:
For positive integers n and k≤n, call a permutation of 1,2,3,…,nk-stable if its first k terms are a permutation of 1,2,3,…,k. Let an,k​ be the number of permutations of 1,2,3,…,n such that k is the least positive integer for which the permutation is k-stable. The quantity to be found is a6,6​.
Note that ∑k=1n​an,k​=n!. Because every permutation of 1,2,3,…,k can be extended to a permutation of 1,2,3,…,n in (n−k) ! ways, it follows that an,k​=(n−k)!ak,k​. Thus the sequence (an,n​) satisfies the recursion an,n​= n!−∑k=1n−1​(n−k)!ak,k​. It is easily verified that a1,1​=a2,2​=1 and a3,3​=3. Therefore
​a4,4​=24−(6⋅1+2⋅1+1⋅3)=13a5,5​=120−(24⋅1+6⋅1+2⋅3+1⋅13)=71, and a6,6​=720−(120⋅1+24⋅1+6⋅3+2⋅13+1⋅71)=461​​
The problems on this page are the property of the MAA's American Mathematics Competitions