جایگشت π از مجموعهی {1,2,…,n} را منتظم مینامیم اگر برای هر (1≤i≤n)i، مقدار |π(i)−i| ثابت باشد. تعداد جایگشتهای منتظم را به ازای n=1996 پیدا کنید.
π(i) عددی است که در جای i ام جایگشت قرار گرفته است. به عنوان مثال، اگر جایگشت π=(3,1,2,4) برای مجموعهی {1,2,3,4} را در نظر بگیریم، آنگاه π(3)=2،π(2)=1،π(1)=3 و π(4)=4.
پاسخ
فرض کنید |π(i)−i|=k. بنابراین π(i) برابر با k+1 و یا i−k است که مورد اخیر به ازای k≥i غیر قابل قبول است. پس برای هر 1≤i≤k داریم π(i)=k+i. حالا ادعا میکنیم که برای هر 1≤i≤k داریم π(k+i)=i چون در غیر این صورت باید برای هر j≥1 داشته باشیم π(jk+i)=(i+1)k+i. حالا ادعا میکنیم که برای هر 1≤i≤k داریم π(k+i)=i. با همین استدلال خواهیم داشت: π((2j−1)k+i)=2jk+i (برای هر j≥1 و 1≤i≤k). بنابراین جایگشت π برای هر j، مجموعهی {kj+1,…,kj+k} را به مجموعهی {kj+k+1,…,kj+2k} میبرد. بنابراین باید n مضربی از 2k باشد. پس تعداد جایگشتهای منتظم غیر از حالت بدیهی k=0، برابر است با تعداد مقسومعلیههای n2. یعنی برای n=1996، ۵ جایگشت منتظم داریم.