一句话题意:给你一个长度为n的排列,求有多少长度为n的排列使得 冒泡排序交换数.
首先,可以证明给出的条件就是要求排列中没有一个长度为3的下降子序列.如何证明?
打表是一种方法,但是我还想了一种证明方法:
考虑排列中的第i位的数字p[i],不妨设p[i]>i.我们把排列中大于p[i]的数字用1表示,其他数字用0表示,那么排列是这样的:
emmmmm大概就是说一共会有n-p[i]个1,p[i]-1个0.而且很显然,包含这个i的逆序对,仅仅是以i为左端点的就有右面的0那么多,就是p[i]-i那么多.如果i左边有1,右面的零就会更多,左边的1也可以和i形成逆序对,那么就会超出限制.这样我们就知道对于这个i所有左边的元素都小于它.再同理讨论p[i]<i和p[i]=i的情况,我们发现由于没有元素可以当下降子序列的中间的元素,显然是没有长度为3的下降子序列的.
下一步是将一个合法的子序列转化成一个括号序列.如何转化?
写出一个dp, 表示放了前 个数,剩余的数中有 个数比之前最大的数要大.显然就有两种转移,一种是放一个比之前最大的数要大的数,这个是有 种放法.一种是放一个更小的数,因为这个更小的数后面的数都得比他大才行,所以必须是最小的数.有一个case是不能走第二种转移的,也就是 的case.
如果我们考虑 的话,相当于是二维平面上每次给 加任意数,或者是给 减1,并且不能越过 的一个随机游走,没有限制的时候显然对应了长度为 的括号序列,就是卡特兰数.
(上面两段段来自武弘勋的知乎回答)
用语言不好描述,写一点python代码,证明留给读者(鸽).
对于一个有着字典序限制的情况,可以遍历,枚举哪里超过了字典序,相当于固定了一个序列的前缀求方案数.这一步是一个经典问题,可以使用两个组合数相减来求值.
dbq,12点30分了,我不能写了,我好爬啊,希望我能做更多更好的题.