一道组合题求助

lwy4321

对于1，2，……，n的任意一个排列，如果相邻的两个数a，b满足a小于b称为递增的，a大于b称为递减的。请问有多少种排列使得其中恰好有且只有两对相邻数递增？

mathe

在两对递增顺序处将序列断开，可以分成三个非空递减序列，可以对应三个非空子集。
所以我们可以先将n个数按顺序分成三个集合，数目可以写成$\sum_{k=1}^{n-2}C_n^k*\sum_{h=1}^{k-1}C_k^h=\sum_{k=1}^{n-2}C_n^k(2^k-2)$
后面应该还可以化简，我就不做了。
但是上面计数包含一些非法值，比如第二部分的数完全小于第一部分的。那么第一部分k个，第二部分h个的这种情况相当于分成两部分第一部分h+k个的情况有$C_n^{h+k}$种
同样还有后两部分的情况以及三个都能串在一起的情况等，所以应该改为
$\sum_{k=1}^{n-2}\sum_{h=1}^{k-1}(C_n^k*C_k^h-C_n^{h+k}-C_n^k+1)$,
根据对称性可以写成$\sum_{k=1}^{n-2}\sum_{h=1}^{k-1}(C_n^kC_k^h-2C_n^k+1)=\sum_{k-1}^{n-2}(C_n^k(2^k-2)-2(k-1)C_n^k+(k-1))$
然后慢慢化简吧，应该不难

lwy4321

mathe 发表于 2015-1-17 21:44
在两对递增顺序处将序列断开，可以分成三个非空递减序列，可以对应三个非空子集。
所以我们可以先将n个数 ...

明白了，万分感谢！

fungarwai

什么情况？不是斯特灵数吗？
\(S(n,3)=\cfrac{1}{6}(3^n-3\times 2^n +3)\)

fungarwai

不是斯特灵数，是这个
\(\displaystyle \sum_{k=0}^2 (-1)^k C_{n+1}^k (3-k)^n = 3^n-C_{n+1}^1 2^n +C_{n+1}^2\)