【附】为便于编辑修改，特提供纯文本文档如下：
2021年北大夏令营一道排列计数问题思路剖析与解答
冯跃峰
【真题2-5】对给定正整数n，记ai=2i-1（1≤i≤n），b1，b2，…，bn是2，4，…，2n的一个排列。若对1≤i≠j≤n，均有min{ai，bi}+ min{aj，bj}≠min{ai，bj}+ min{aj，bi}，则称（b1，b2，…，bn）为“好排列”。求所有的好排列个数。（2021年北大夏令营第一天第3题）
【题感】从目标看，本题属于组合计数问题。从条件看，直接给出了要素列（b1，b2，…，bn），但其限定条件非常别扭。
解题的关键，是确定怎样的两个数对（ai，aj）、（bi，bj），方能满足“min{ai，bi}+ min{aj，bj}≠min{ai，bj}+ min{aj，bi}”。
由于ai、aj是给定的，我们只需讨论怎样的数对（bi，bj）满足上述条件。为方便，我们称满足上述条件的数对（bi，bj）是好的。
为了找到好数对（bi，bj），只需穷举bi、bj与ai、aj之间的大小关系。这有多种可能，讨论似乎相当繁琐。但注意到bi、bj交换，不等式仍然成立，所以（bi，bj）是好的，等价于（bj，bi）是好的。因此我们不妨假定bi<bj，使讨论得到简化。
【下定义】如果数对（bi，bj）满足min{ai，bi}+ min{aj，bj}≠min{ai，bj}+ min{aj，bi}，则称之为好的。
【减少工作量】bi、bj交换，不等式仍然成立，所以（bi，bj）是好的，等价于（bj，bi）是好的，我们不妨假定bi<bj。
【穷举大小关系】对i<j，将ai、aj；bi、bj排成递增序列。由于ai=2i-1<2j-1=aj，bi<bj，其大小关系有6种可能：将bi、bj插入ai、aj形成3个“空”，当bi、bj相邻时有C31=3种，bi、bj不相邻时有C32=3种。
（1）ai<aj<bi<bj，此时min{ai，bi}=ai，min{aj，bj}=aj，min{ai，bj}=ai，min{aj，bi}=aj，（bi，bj）不是好的。
（2）bi<bj <ai <aj，此时min{ai，bi}=bi，min{aj，bj}=bj，min{ai，bj}=bj，min{aj，bi}=bi，（bi，bj）不是好的。
（3）ai <bi<bj<aj，此时min{ai，bi}=ai，min{aj，bj}=bj，min{ai，bj}=ai，min{aj，bi}=bi，（bi，bj）是好的。
（4）bi<ai <bj<aj，此时min{ai，bi}=bi，min{aj，bj}=bj，min{ai，bj}=ai，min{aj，bi}=bi，（bi，bj）是好的。
（5）ai<bi <aj <bj，此时min{ai，bi}=ai，min{aj，bj}=aj，min{ai，bj}=ai，min{aj，bi}=bi，（bi，bj）是好的。
（6）bi<ai<aj<bj，此时min{ai，bi}=bi，min{aj，bj}=aj，min{ai，bj}=ai，min{aj，bi}=bi，（bi，bj）是好的。
前两种情形，（bi，bj）不是好的；后4种情形，（bi，bj）是好的。为叙述方便，我们称前两种是“清排列”，两种是“混排列”。
【下定义】对i<j，将ai、aj；bi、bj由小到大排列，若bi、bj都排在ai的左边，或者都排在aj的右边，则称ai、aj；bi、bj是 “清排列”，否则称为“混排列”。
【发掘规律】由上可知，（bi，bj）是好的，等价于ai、aj；bi、bj是“混排列”。
由此可见，（b1，b2，…，bn）是好排列，等价于任何i<j，ai、aj；bi、bj是“混排列”。
这样理解限定条件，求好排列（b1，b2，…，bn）就变得非常简单了：依次考虑b1，b2，…，bn的取值即可。它是一种“任意型”条件，适当赋值即可确定bi的取值。
【分步计数】记好排列（b1，b2，…，bn）个数为xn，先考虑b1的取值。
显然，b1有n种可能，但b1的不同取值，导致后面排列（b2，b3，…，bn）的方法数不同，需要对b1的取值分类讨论。
【分类计数】考察b1=2k（1≤k≤n）的好排列（b1，b2，…，bn）。
因为（b1，b2，…，bn）中的所有对子（bi，bj）都是好对子，可适当选取其中若干好对子建立不等式，求出b1，b2，…，bn的值。
注意到b1=2k>2k-1=ak，可见相应的混排列中b1排在ak的后面，当然排在任何aj（2≤j≤k）的后面，得到顺序排列：（a1，aj，b1）。
由此想到，在其中加入bj构成混排列。
【赋值】考虑a1、aj；b1、bj（2≤j≤k）构成的混排列，因为a1<aj=2j-1≤2k-1<2k=b1，得到顺序排列：（a1，aj，b1），由混排列可知，bj <aj=2j-1。
由j的任意性，取j=2，3，…，k，得b2<3，b3<5，…，bk<2k-1。
又b2，b3，…，bk是正偶数，依次得b2=2，b3=4，…，bk=2k-2。
以下只需确定（bk+1，b k+2，…，bn）的取值。
注意到bk+1，b k+2，…，bn是2k+2，2k+4，…，2n的一个排列，且（ak+1，a k+2，…，an）=（2k+1，2k+3，…，2n-1）。所以，排列（bk+1，b k+2，…，bn）相对于（ak+1，a k+2，…，an）是好排列（或者将所有数都减去2k），从而（bk+1，b k+2，…，bn）有xn-k种可能（设xn为好排列个数）。
上述讨论有一个小漏洞：不包括k=n的情形（x0无意义），需另外讨论。
当k=n时，b1=2n。此时，由b2<3，b3<5，…，bn<2n-1，得b2=2，b3=4，…，bn=2n-2，好排列唯一存在。
注意到k有多种取值，这利用加法原理即可。
【加法原理】令k=1，2，…，n，得xn=xn-1+xn-2+…+x1+1。
如何解此递归方程？利用变量替换，转化为常见递归方程即可。
【变量替换】记Sn= xn+xn-1+…+x1，则当n>1时，Sn-Sn-1=Sn-1+1，即Sn=2Sn-1+1。
这是常见的一阶线性递归方程，可转化为等比数列求解。
【待定系数】设Sn+d=2（Sn-1+d），即Sn=2Sn-1+d。
与原递归方程比较，取d=1即可。
【化归】递归方程变形，得Sn+1=2（Sn-1+1），于是，Sn+1=2n-1（S1+1）=2n，所以Sn=2n-1。
进而，xn=Sn-Sn-1=（2n-1）-（2n-1-1）=2n-1（n>1）。
这里要特别注意递归方程中的限定“n>1”，需要补充n=1的项。
又x1=1=20，所以对任何正整数n，有xn=2n-1，即好排列个数为2n-1。
【新写】对i<j，将ai、aj、bi、bj由小到大排列，若bi、bj不都排在ai的左边，也不都排在aj的右边，则称ai、aj；bi、bj是 “混排列”。 易知，（b1，b2，…，bn）是好排列，等价于对任何i<j，ai、aj；bi、bj都是“混排列”（ 穷举ai、aj与bi、bj的各种大小关系即可）。
记好排列（b1，b2，…，bn）个数为xn。当b1=2k（k∈N+）时，考虑混排列a1、aj；b1、bj（2≤j≤k），其中a1=1<2k=b1，aj=2j-1≤2k-1<2k=b1，必有2j-1=aj>bj（2≤j≤k）。
令j=2，3，…，k，得b2<3，b3<5，…，bk<2k-1。又b2，b3，…，bk是正偶数，依次得b2=2，b3=4，…，bk=2k-2。
当k<n时，bk+1，b k+2，…，bn是2k+2，2k+4，…，2n的一个排列，所以排列（bk+1，b k+2，…，bn）相对于（ak+1，a k+2，…，an）是好排列，有xn-k种可能，从而b1=2k（1≤k<n）的好排列有xn-k个。
当k=n时，b1=2n。此时，由b2<3，b3<5，…，bn<2n-1，得b2=2，b3=4，…，bn=2n-2，此时的好排列唯一存在。
于是，xn=xn-1+xn-2+…+x1+1。令Sn= xn+xn-1+…+x1，则n>1时，Sn-Sn-1=Sn-1+1，解得Sn=2n-1，进而xn=2n-1（n>1）。又x1=20，所以xn=2n-1（n∈N+），故好排列个数为2n-1。
联系客服
