|
|
生如夏花(2365*****) 12:29:13
18个数进行排列，要求每个数字两侧要么比他大要么比他小，问有几种排列方法。
首先要说一下这题的叙述不够严谨，首先应该强调数字是不是不同的，因为有相同的数字就会影响结果，为免歧义，下面将题目改成：
18个不同的数进行排列，除了头尾两个数字外，要求每个数字两侧的两个数字要么都比它大要么都比它小，问有几种排列方法。
解：
为方便叙述，先约定词语：
设有 $n$ 个不同的数，用数列 \an 表示排列，在符合条件的排列中，
若 $a_2>a_1$，则称该排列为“头增”；
若 $a_2<a_1$，则称该排列为“头减”；
若 $a_n>a_{n-1}$，则称该排列为“尾增”；
若 $a_n<a_{n-1}$，则称该排列为“尾减”。
记符合条件的排列个数为 $f(n)$，下面证明，以上四种排列的个数都是 $f(n)/2$。
若 $n$ 为偶数，由于排列是“锯齿”形的，故头尾增减性相同。
如果将排列倒过来排，显然也符合条件，而“头增尾增”就会变成“头减尾减”，反之亦然，
这说明“头增头减”和“尾增尾减”构成一一对应，所以个数都为 $f(n)/2$；
若 $n$ 为奇数，由于排列是“锯齿”形的，故头尾增减性相反。
当排列为“头增尾减”时，
若 $a_n>a_1$，则将 $a_n$ 放到 $a_1$ 前面，
若 $a_n<a_1$，则将 $a_1$ 放到 $a_n$ 后面，
显然无论哪种情况，都将得到符合条件的“头减尾增”排列，
这说明“头增尾减”的个数不小于“头减尾增”的个数；
同样道理，当排列为“头减尾增”时，亦可用类似的操作将其变为“头增尾减”，
于是“头减尾增”的个数也不小于“头增尾减”的个数，所以它们的个数是相同的。
综上所述，四种排列的个数都是 $f(n)/2$。
现在来研究 $f(n)$。
不难数出 $f(2)=2$, $f(3)=4$, $f(4)=10$，当 $n\geqslant 5$ 时，不妨设最大的数排在第 $k$ 位。
当 $k=1$，则后面的 $n-1$ 个数只需为“头增”即可，即 $f(n-1)/2$；
当 $k=2$，则第一个数随便取，剩下的 $n-2$ 个数为“头增”，即 $(n-1)f(n-2)/2$；
当 $3\leqslant k\leqslant n-2$，则先从 $n-1$ 个数中选出 $k-1$ 个放在前面，剩下的放后面，且前面的是“尾减”，后面的是“头增”，即 $C_{n-1}^{k-1}\cdot f(k-1)/2 \cdot f(n-k)/2$；
当 $k=n-1$ 和 $n$ 时，类似于前面，分别为 $(n-1)f(n-2)/2$ 和 $f(n-1)/2$。
综上，得到 $n\geqslant 5$ 时的递推关系
\[f(n)=f(n-1)+(n-1)f(n-2)+\sum_{k=3}^{n-2}C_{n-1}^{k-1}\cdot \frac12f(k-1)\cdot \frac12f(n-k),\]
若另外令 $f(0)=f(1)=2$，则上式就能统一为
\[f(n)=\frac14\sum_{k=1}^nC_{n-1}^{k-1}f(k-1)f(n-k),\]
而且对 $n\geqslant 2$ 都成立。
至于怎么求通项，暂时还没想到，用软件递推上去的话，得到
\[\{f(2),\ldots,f(18)\}=\{2, 4, 10, 32, 122, 544, \ldots, 4809759350882\},\]
最后这个数就是本题的结果。 |
|
zhcosin
发表于 2017-4-18 17:02
色k
发表于 2017-4-18 17:24
hbghlyj
发表于 2022-3-18 17:02
