emmmmm

一句话题意：给你一个长度为n的排列，求有多少长度为n的排列使得 冒泡排序交换数。 首先，可以证明给出的条件就是要求排列中没有一个长度为3的下降子序列。如何证明？ 打表是一种方法，但是我还想了一种证明方法： 考虑排列中的第i位的数字p[i]，不妨设p[i]>i