已知
数列$a_n$是$1,2,3,\cdots,n$的一个排列,如果有且仅有一个$1 \le i \le n-1$满足 $$ a_i> a_{i+1} $$ 那么这样的排列有多少个?
题解
假设满足条件的排列有$f(n)$个,考虑从$f(n-1)$到$f(n)$的递推:
- 如果某个$1,2,\cdots,n-1$的排列已经满足题设条件: $$ a_1 < a_2 < \cdots < a_i > a_{i+1} < \cdots < a_{n-1} $$ 也就是说,上述的不等式链中只有一个大于号。
那么,我们如果想把$n$(注意,这是最大的元素)加入到这个不等式链中,并且保持大于号的数量不变。仅有两个位置($a_i$和$a_{i+1}$之间,以及整个数列的最后)可以,其余的位置都会导致大于号的数量变多。
- 如果$1,2,\cdots,n-1$的一个排列不满足题设的条件
那么想要让在加入$n$这个元素后满足条件,原先的排列必须是严格递增的(也就是不等式链中没有大于号),因为加入$n$只会让大于号的数量增加1或者不变。于是在这种情况下,除了最后一个位置,有$n-1$个位置可以选择。
综上所述: $$ f(n) = 2f(n-1)+n-1 $$
从而 $$ f(n) + n + 1 = 2(f(n-1) + n) $$
可以推出: $$ f(n)+n+1 = 2^{n-2}(f(2)+3)=2^n $$
于是: $$ f(n) = 2^n-n-1,\quad n\ge 2 $$
类似的问题
逆序数
逆序数问题和我们最开始介绍的问题非常相似
数列$a_n$是$1,2,3,\cdots,n$的一个排列,它的逆序数定义为逆序对的个数: $$ \sum_{i\ne j} I(a_i>a_j) $$ 例如,$1,2,3$的一个排列:$3,1,2$,共有两个逆序对$(3,1)$和$(3,2)$,于是它的逆序数是2.
那么:逆序数为$2$的$n$元排列(记作$f_2(n)$)有多少个?
我们依然考虑在$1,2,\cdots,n-1$的排列中插入$n$。
- 如果原先排列的逆序数就是2,想要插入之后还是2,就需要插入在最后。
- 如果原先排列的逆序数是1,就需要插入在倒数第1个位置,如此可以增加一个逆序对$(n,a_{n-1})$。
- 如果原先排列的逆序数是0,就需要插入在倒数第2个位置,如此可以增加两个逆序对$(n,a_{n-1})$和$(n,a_{n-2})$。
所以: $$ f_2(n) = f_2(n-1)+f_1(n-1)+f_0(n-1) $$
显然:
- 无逆序的排列$f_0(n)=1$,只有升序一种。
- 逆序数为1的排列$f_1(n)=n-1$,只有交换相邻的两个数字。
- 例如:$1,2,4,3,5$
- 或者我们可以继续递归: $$ f_1(n) = f_1(n-1)+f_0(n-1) $$
- 同样可以得到:$f_1(n)=n-1$
所以: $$ f_2(n) = f_2(n-1)+n-2+1 $$ 至此我们求得了递推关系。
实际上,根据上面的思路我们可以求出一般的$f_k(n)$:
k | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|
n=1 | 1 | — | — | — | — | — | — |
n=2 | 1 | 1 | — | — | — | — | — |
n=3 | 1 | 2 | 2 | 1 | — | — | — |
n=4 | 1 | 3 | 5 | 6 | 5 | 3 | 1 |
这对应于n阶置换群的分类。
最大奇约数
这种题也很常见,$2^n=2^{n-1} + 2^{n-1}$,分组求和
函数$g(m)$定义为m的最大奇约数,求: $$ a_n = g(2^{n-1}+1)+g(2^{n-1}+2)+\cdots + g(2^{n-1}+2^{n-1}) $$
我们知道,奇数的最大奇约数就是自己: $$ g(2k+1) = 2k+1 $$ 而偶数的最大奇约数和因子2无关: $$ g(2k+2) = g(k+1) $$ 所以: $$ \begin{aligned} &a_n \\ = &\sum_{k=1}^{2^{n-2}} g(2^{n-1}+2k-1) + \sum_{k=1}^{2^{n-2}} g(2^{n-1}+2k)\\ = &\sum_{k=1}^{2^{n-2}} (2^{n-1}+2k-1) + \sum_{k=1}^{2^{n-2}} g(2^{n-2}+k)\\ = &\sum_{k=1}^{2^{n-2}} (2^{n-1}+2k-1) + a_{n-1} \end{aligned} $$ 于是我们得到了递推: $$ a_n = a_{n-1} + 3\cdot 2^{2n-4} $$
礼物交换问题
在概率论中,经常能通过条件概率的方式找到递推关系
现有$n$个人的群体,每个人都准备了一份礼物, 把这些礼物混合打乱之后每个人再随机拿走一份礼物。没有任何一个人拿到自己礼物(我们称这是一个匹配)的概率$P_0(n)$是多少?
设无匹配为事件$A$,第一个人拿到自己礼物为事件$B$,那么 $$ P_0(n) = P(A) = P(A|B)P(B)+ P(A|\bar B)P(\bar B) $$ 其中$P(A|B) = 0$可以去掉这一项,而 $$ P(\bar B) = 1-P(B) = 1-\frac{(n-1)!}{n!} = \frac{n-1}{n} $$ 我们之前计算过。
设1拿到了s的礼物,考虑第三个事件$C$代表s拿到了1的礼物,那么: $$ P(A|\bar B) =P(A|C\bar B)P(C)+P(A|\bar C\bar B)P(\bar C) = \frac{1}{n-1}P_0(n-2) + P_0(n-1) $$
其中 $$ P(C) = \frac{1}{n-1} $$ 很好理解。
$\bar B C$就是1和c互换礼物情况,这时候问题就简化成$n-2$的子问题了,所以 $$ P(A|\bar B C) = P_0(n-2) $$
最后,根据Bayse公式 $$ P(A|\bar C\bar B)P(\bar C) = P(A\bar C| \bar B) $$ 问题变成:已知1没有拿到自己的礼物,想要求无匹配并且1和s没有交换礼物的概率。
1已经拿走了s的礼物,现在还有$n-1$个礼物,我们把1的礼物当作是s的礼物,问题就变成了这剩下的$n-1$个人无匹配。
由于把1的礼物当作是s的礼物,所以$\bar C$(s不拿到1的礼物)相当于是要求无匹配。
所以 $$ P(A\bar C| \bar B) = P_0(n-1) $$
综上所述 $$ P_0(n) = \frac{n-1}{n}(\frac{1}{n-1}P_0(n-2) + P_0(n-1)) $$ 我们得到了一个递推数列。
它的解是:$$P_0(n) = \frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\cdots+\frac{(-1)^n}{n!}$$ 当n很大的时候:$$P_0(n) \to e^{-1} \approx 0.3679$$ 看来有人拿到自己礼物的概率还是很高的