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=1nan,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