Question

【題目】設為給定的大于2的正整數，集合，已知數列：，，…，滿足條件：

①當時，；

②當時，.

如果對于，有，則稱為數列的一個逆序對.記數列的所有逆序對的個數為.

（1）若，寫出所有可能的數列；

（2）若，求數列的個數；

（3）對于滿足條件的一切數列，求所有的算術平均值.

Answer 1

【答案】（1）不同的分別為：；（2）；（3）.

【解析】

（1）根據可列出滿足條件的.

（2）就構成逆序對的元素的個數分類計數可得滿足條件的的個數.

（3）引進一個定義：，有，則稱為數列的一個順序對，可證明所有的中，逆序對的總數和順序對的總數相等，從而可得逆序對的個數為，故可求其平均值.

（1）因為， 故只有一個逆序對，

則不同的分別為：.

（2）因為，故數列：，，…，有兩種情況：

①2對逆序數由3個元素提供，即

，

這樣的共有個.

②2對逆序數由4個元素提供，即

.

這樣的共有.

綜上，滿足的數列的個數為.

（3）對任意的：，，…，，其逆序對的個數為，

我們引進一個定義：，有，則稱為數列的一個順序對，

則中的順序對個數為.

考慮：，，…，與：，，…，，

中的逆序對的個數為中順序對的個數，中順序對的個數為中逆序對個數，

把所有的按如上形式兩兩分類，則可得所有的中，逆序對的總數和順序對的總數相等，而它們的和為，故逆序對的個數為，

所以所有的算術平均值為.