构造无长度为n+1的递增/递减子序列的1~n²排列问题

嘿，这个问题我当年学组合学时也琢磨过！其实答案就在你提到的Rosen子序列定理的反向构造里，咱们一步步来拆解：

首先，先给你一个直接的构造方案，拿小例子先直观感受下——比如n=3的时候，我们可以把1到9的数分成3组：[1,2,3]、[4,5,6]、[7,8,9]，然后把每组从大到小排列，再按组的顺序拼接起来，得到排列：3,2,1,6,5,4,9,8,7。

你可以验证下：

• 最长递增子序列的长度是3（比如3,6,9或者2,5,8），达不到n+1=4；
• 最长递减子序列的长度也是3（比如3,2,1或者6,5,4），同样达不到4。

把这个思路推广到任意正整数n的情况：

1. 把1到n²的整数分成n个连续的块，第k块的数是 [(k-1)*n + 1, k*n]（k从1到n）；
2. 对每个块内部的数，按从大到小的顺序排列；
3. 把这n个排好序的块按k从小到大的顺序拼接起来，就得到了符合要求的排列。

为什么这个构造成立？ #

• 对于递增子序列：因为每个块内部是递减的，所以你不可能从同一个块里取两个数放进递增子序列里，最多只能从每个块取一个数，所以最长递增子序列的长度最多是n，不会达到n+1；
• 对于递减子序列：因为块与块之间是递增的（第k块的所有数都小于第k+1块的数），所以你不可能从不同的块里取数组成递减子序列，最多只能在同一个块里取，而每个块只有n个数，所以最长递减子序列的长度最多是n，也不会达到n+1。

当然，你也可以反过来构造：把每个块内部从小到大排列，然后把块按从大到小的顺序拼接，比如n=3时得到7,8,9,4,5,6,1,2,3，同样满足要求，原理是一样的。

其实这个构造就是Rosen子序列定理的构造性反向例子——定理说n²+1个数的排列必然存在长度n+1的递增/递减子序列，而n²个数刚好可以通过这种分块构造，把最长递增/递减子序列的长度卡在n，完美避开n+1的情况。

备注：内容来源于stack exchange，提问作者Vinay Karthik