一句话题意：给你一个长度为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分了，我不能写了，我好爬啊，希望我能做更多更好的题。