免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

[组合] 来自减压研究群的一道排列计数——锯齿排列

生如夏花(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\},\]
最后这个数就是本题的结果。
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友
$\href{https://kuingggg.github.io/}{\text{About Me}}$

本帖最后由 zhcosin 于 2017-4-18 17:04 编辑

这通项明显可以猜啦,$a_n=4n!$ ,唔。。。不对。。。。。

TOP

经贴题者提醒,上述解法前半段证明“头增”之类的占总数一半其实可以更简单,首先不妨设这 $n$ 个数为 $1$, $2$, \ldots, $n$,若排列 \an 符合条件,则作变换 $a_k\to n+1-a_k$ 将得到符合条件且增减性完全相反的排列,这就说明“头增”和“头减”、“尾增”和“尾减”都是一一对应的,所以都为 $f(n)/2$。
生如夏花 2017/4/18 16:37:55
@大色k 前半段证明“头增”之类的占总数一半,可以用n+1来减去每个数得到“头减”,所以头增和头减一一对应,也就是各占一半。我之前也是考虑到这个。
大色k 2017/4/18 16:39:32
O,就是上下对称?
生如夏花 2017/4/18 16:46:18
对,没想到可以抓最大数的位置来分析。我好好看看。
大色k 2017/4/18 16:47:09
嗯,我竟然没想到上下对称,只想到了左右对称,结果就发现要分奇偶
QQ图片20170418172355.gif
2017-4-18 17:24
这名字我喜欢

TOP

回复 2# zhcosin

若令 $f(n)=4n!b_n$,则 $b_0=b_1=1/2$ 且
\[b_n=\frac1n\sum_{k=1}^nb_{k-1}b_{n-k},\]
形式好看些,但还是不知怎么求通项……

TOP

回复 4# 色k

更好看的形式是令$a_{n}=f(n)/4$,于是递推公式变为
\[ a_{n+1}=\sum_{i=0}^n C_n^i a_{n-i}a_i \]
是不是像极了二项式定理和莱布尼茨公式?

TOP

回复 5# zhcosin

然并卵

TOP

回复 5# zhcosin


    http://oeis.org/A260786

TOP

https://www.zhihu.com/answer/2392806042
生成函数,有空看看

TOP

回复 8# 爪机专用


我就是仿佛见过你写过似的~~~~~

TOP

TOP

返回列表 回复 发帖