集合[n]的递减排列数量求解疑问及结论验证

嗨，我来帮你理清这个问题的思路～

首先先把你的问题和尝试整理出来：

问题：对于集合 [n] = {1, 2, ..., n} 的排列 σ，如果对任意的 i < j，都满足 σ(i) > σ(j)，则称 σ 是递减排列。那么 [n] 的递减排列有多少个？

我的尝试：
因为对于所有 i ∈ {2, ..., n}，都有 1 < i，所以 σ(1) 必须等于 n。否则会存在某个 j，使得 σ(j) = n > σ(1)，但 1 < j，这就违反了递减排列的定义。
用同样的逻辑可以推出：σ(2) = n-1
.
.
.
由此得出结论：当 n 是偶数时，恰好有 1 个递减排列；当 n 不是偶数时，不存在递减排列。
我看不出哪里错了，但这个结论又好像太简单了，有人能帮忙确认一下吗？

你的前半部分推理其实完全正确！按照递减排列的严格定义，每个位置的元素都必须比后面所有位置的元素大：

• 第一个位置必须是整个集合里最大的数 n，否则后面某个位置的 n 会比它大，违背 i<j 时 σ(i)>σ(j) 的要求；
• 第二个位置必须是剩下元素里最大的 n-1，同理；
• 以此类推，最后一个位置只能是最小的数 1。

但你后面关于奇偶性的结论是错误的，这个判断没有任何依据哦！举个例子，当 n=3（奇数）时，排列 [3,2,1] 完全符合递减排列的定义：

• 1<2 时，3>2；
• 1<3 时，3>1；
• 2<3 时，2>1；
  所有 i<j 的情况都满足 σ(i)>σ(j)，这就是一个有效的递减排列。

所以正确的结论是：不管 n 是正整数（奇数还是偶数），集合 [n] 的递减排列都恰好有 1 个，就是从 n 到 1 依次排列的那个序列。

备注：内容来源于stack exchange，提问作者Kova1