n^2+1高矮不等的人排成一列，总可以剔减成至少n+1 个人的顺高队列

mathe

很显然，对于上面定义的方排列，其中每一行都是单调增，每一列都是单调减的。 呵呵，余下就可以大胆猜测，于是容易解决的

hujunhua

排列->二叉阵是同胚映射，所有的排列自是$n^2!$，所有二叉阵又是多少呢？

hujunhua

排列->二叉树也是同胚映射，所有的排列自是$n^2!$，所有的二叉树又是多少？ 单独考虑12#和本楼的问题，我们不必取平方数为自变量，直接取n就行了（更有一般性）。

hujunhua

猜想二叉阵与二叉树是一一对应的。因为对于二叉阵中的每一个元素，回溯路径都是唯一的。

zgg___

看了mathe的9层的问题和11层的东东，又尝试了一些例子，就猜测9层问题的答案s总是平方数，呵呵。 假设11层的方阵m（“每一行都是单调增，每一列都是单调减的。”）的总个数是s1，假设每个方阵m对应的n^2长度的序列的个数是s2（这里猜测对于不同的m，s2都一样），那么s=s1*s2，因为猜测s1==s2，所以s就是平方数了，呵呵。

suiyili

我觉得我在3楼中的红字部分说的不对，即使有某个棋子出现在最右边（假设在第k列），也不能说最长递增序列为k, 应该改为存在某个递增序列，它的长度至少为k。 还有在7楼中，倒数第二段，这句话也不对 ‘那也一定是踩着自己上面的棋子过来的，而A(n)上面的棋子一个踩一个，总有一个（顶多到这一列的最上一个）是要踩着自己左边的棋子A(n-1)来的’ 应该改为，A(n)当初一定是踩着第n-1行的某个子到达第n行的，然后有可能向下走才到达它现在的位置A(n)。

hujunhua

从排列到二叉阵，以及从排列到二叉树，用Mathematica实现，Wayne有何高招？

zgg___

恩，实际上，我也没有完全弄明白将序列转变成方阵的算法，呵呵。 先贴一些代码吧：

1. n = 4;
2. m0 = Table[0, {n n}, {n n}];
3. m1[s_] := Module[{fs, rs, c1, c2},
4. If[Length[s] <= 1, Return[s]];
5. fs = First[s]; rs = Rest[s]; c1 = m1[rs];
6. c2 = m1[Select[rs, # > fs &]];
7. If[Length[c1] >= Length[c2] + 1, c1, Prepend[c2, fs]]];
8. m2[s_] := Module[{fs, rs, c1, c2},
9. If[Length[s] <= 1, Return[s]];
10. fs = First[s]; rs = Rest[s]; c1 = m2[rs];
11. c2 = m2[Select[rs, # < fs &]];
12. If[Length[c1] >= Length[c2] + 1, c1, Prepend[c2, fs]]];
13. m3[s_] := Module[{mm = m0, x, y, i},
14. Do[x = 1; y = 1;
15. While[mm[[x, y]] > 0, If[mm[[x, y]] > s[[i]], x++, y++]];
16. mm[[x, y]] = s[[i]], {i, n n}];
17. mm];
18. s = {6, 3, 1, 13, 7, 9, 8, 10, 2, 14, 11, 15, 5, 4, 16, 12}
19. m1[s]
20. m2[s]
21. m3[s] // MatrixForm

复制代码

其中m1（和m2）返回一个序列s的某个最长的递增（和递减）序列，m3返回某个序列s的（我自以为的）转变后的方阵，也不知道理解对不，然后是对某个s的运算，结果大致如下： m1:{1, 7, 8, 10, 11, 15, 16} m2:{13, 9, 8, 5, 4} m3:{ {6,13,14,15,16, 0, 0}, {3, 7, 9,10,11,12, 0}, {1, 2, 8, 0, 0, 0, 0}, {0, 0, 5, 0, 0, 0, 0}, {0, 0, 4, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0}} 貌似有些问题呢。呵呵。

hujunhua

搜到12#和13#的答案了，就是二叉树的计数： n个结点的不相似二叉树共有${{:((2n),(n)):}}/{n+1}$ 我没学过数据结构，但此地的编程高人全都学过，可能都知道这个答案。:L

zgg___

提供一些数吧，例如在下面第8个方阵中的第3行第4列的数是8036，表示在长度为8的总共40320个序列中，最长递增数列长度为3且最长递减数列长度为4的序列的总个数是8036个。（可以看到其中的平方数还是很多的，呵呵。）

1. ss = {};
2. Do[
3. t0 = Permutations[Range[n]];
4. t1 = Map[{Length[m1[#]], Length[m2[#]]} &, t0];
5. t2 = Map[First[#] -> Length[#] &, Split[Sort[t1]]];
6. AppendTo[ss, SparseArray[t2]];
7. , {n, 9}]
8. Map[MatrixForm, ss]

复制代码