|
我在本公众号11月5日发表的文章“又一个组合计数问题征解”中，曾经提出如下一个问题征解，即 有高矮各不相同的100名同学，随机地排成一个10×10的方阵。每行取最高的一个同学，一共10个高个子，记为集合T；每列取最矮的一个同学，一共10个矮个子，记为集合S。当T中最矮的和S中最高的是同一个人时，这样的排列有多少种？ 为了研究一般化，我将10改成一般的n。 当n = 2时，(n^2)! =24个全排列中，容易知道符合条件的排列数为16。由于数值较小，既可以编程，也可以手工编排计数。 当n = 3时，全排列数为(n^2)! =362880，是用计算机全搜索查找出来的。全排列的数目急剧增加，但是仍然可以采用穷举法用计算机编程，得到符合条件的排列数为108864。个人电脑搜索的时间只有不到3秒。 我曾经说过，当n进一步增加时，即使采用计算机进行暴力搜索也是不现实的，比如，当n = 4时，全排列数为(n^2)! = 2.09e13，即达到10^13数量级，比n = 3时的复杂度高了8个数量级。如果n = 3时计算机需要接近3秒，那么n = 4时计算机可能要数十年才行(用我的同一台计算机，大型机除外)。 对于n >= 4的情况，我采用仿真的方法，计算得到排列的近似值如下： n 试验值 4 2.3913e+012 5 6.1750e+023 6 4.8601e+039 7 2.5639e+060 8 1.6153e+086 9 2.0638e+117 10 9.6126e+153 今天得到一个署名biglion(大狮子)的朋友给出n = 4时的排列结果为2391175987200，和我的仿真结果2.3913e+012的前四位有效数字相同，说明我的实验方法结果是十分精确的。得到这个数据也是相当不容易的，感谢大狮子朋友！ biglion朋友建议我不要仅仅考虑正方形阵列的情形，不妨考虑长方形阵列，可以更好地寻找规律。
|
|
|
