1樓：不改名更不了答案
命題：若置換 不含任何逆序，則 ，即恒等對映。
證明：置換 不含逆序 。首先，滿足 的置換 是不可能存在的，因為這與置換作為雙射的單射性衝突，所以條件中的等於號可以去掉，即 。
其次， ，對 進行歸納，顯然 （小於等於任何自然數而 ），而若結論對 成立，則 ，而由於 ，有 ，故 ，歸納假設成立，結論得證。最後，若 使得 ，則 ，因為 ，以此類推，這將導致 （與置換的像仍是 矛盾）。因此， ，而 正是恒等對映的定義。
■定義（逆差）：若序對 在置換 下是逆序，則稱正整數 為 的逆差。
命題：設定換 有逆序，則必然存在某一逆序 的逆差為 。
證明：反證法。假設置換 有逆序，但任一逆序 的逆差均不為 （亦即 ），對 作歸納。
初始情況應從 開始，但顯然出現矛盾（唯一的非恒等排列恰是乙個逆差為 的對換），故初始情況成立。現歸納地假設命題對 皆成立，考慮 的情況。給定任意 元排列，考慮 （由於置換是雙射， 必然存在）；則以下兩種情況必居其一——
i） 。則對於 的任意逆序 ，必有 。依歸納假設，命題成立。
ii）。則 ， 皆為逆序，並且依照開始的假設，必然有 ，而這意味著 ；然而，由於置換作為雙射必然是滿射， 使得 。現考慮數字 在排列中相對於 的位置，若它在 之右，即 使得 ，則立刻得到逆差為 的逆序 ；否則， 在 之左，即與 一同位於 之同側，那麼將同樣的論證施加於 ……依次類推。
由於 元集是有限的，這一過程不可能無窮地進（遞）行（降）下去，從而必然止於某一 ，即—— 與 分別居於 之兩側，且前者在左而後者在右；那麼顯然逆序 的逆差為 ，即與最初的假設矛盾，從而完成歸納。
綜上，歸納假設成立，命題得證。■
命題：若置換 含有逆序，定義對換 （其中 是某個逆差為 的逆序），則 中不含有 的逆序 ，且 的逆序數比 少 。
證明：首先，逆差為 的逆序 的存在性由上一命題可知，考慮 ，且 ，進而 ，這便證明了中不含有 的逆序 。其次，令 ，則——。
可以看出i）逆序 不復存在，亦即對換 消除了 的一對逆序關係，逆序數量減1ii）既不含 ，也不含 的逆序對完全不會被 改變，自然它們的數量也就不變iii）集合 和集合 中的逆序對，在 作用下的輸出結果會改變，但逆序關係不變，自然逆序關係的總數仍然不變iv）集合 和集合 中的逆序對，分別滿足條件 \sigma\left( x \right)" eeimg="1"/>和 l" eeimg="1"/>，也就是 和 ；由於 作為雙射具有單射性，故 ， ，那麼條件可以改進為：對於 中的逆序 ，\sigma\left( x \right)" eeimg="1"/>和 \sigma\left(i\right)=l+1" eeimg="1"/>，即 \tau\sigma\left( x \right)" eeimg="1"/>和 \tau\sigma\left( j \right)" eeimg="1"/>。那麼，集合 的逆序在 的作用下輸出的結果會改變，然而逆序關係仍然不變，自然其總數依舊不變以上四個部分不重不漏地遍歷了全部的（順）序對；那麼，對於命題中設定的對換 而言， 的逆序數比 少 。
■推論：若 是置換 的逆序數，存在 個對換 使得 。
證明：依以上各命題，顯然。
關於環排列的乙個問題？
紅色高加索戰士 舉乙個例子 四個人圍成一圈，有幾種不同的排列方式？第一步 如下圖所示，在沒有排第乙個元素前，由於圓上的位置沒有相對位置之分 沒有首尾之分 所以第乙個人只有1種排列方式。第二步 此時，圓上的各個位置已經有相對位置之分，因此第二個人有3種排列方式。第三步 同理第三個人有2種排列方式 第四...
可以寫出乙個簡潔優美的依次給出下乙個排列的函式嗎？
flowmemo 你這個是要求三個向量的笛卡兒積，python的itertools裡已經自帶了。實現的話，將輸出的組合向量想象成三位的記分牌 或里程表 模仿一下記分牌的記分進製過程就行。 知之 一 python的標準API裡已經提供了該功能，如此即可 from itertools import pr...
乙個非常規的排列組合問題？
大老李 答案有可能是理論最大值110天，其中每個工人出工11天。這種情況問題屬於BIDB設計。其中v 100,n 10,1。這個三個引數符合BIDB存在性定義。但是符合存在性條件還有一些可能是構造不出來的。用專業軟體查了下，發現確實還沒有構造出 100,10,1 的BIDB設計 但是不能否認存在的可...