Question

求详解！排列组合

一个正在行进的10人队列，每人身高各不相同，按从低到高的次序排列，现在他们要变成并排的2列纵队，每列仍然是按从低到高的次序排列，同时要求并排的每两人中左边的人比右边的人要矮，那么，2列纵队有___________种不同排法．

Answer 1

很有意思的题目
目前想到的方法
设两纵队为AB，且按身高编号从1到10，最高在排头，从5分为两队
A B
5 10
4 9
3 8
2 7
1 6
则1和10的位置不能变，剩下的可以在AB间交换
首先考虑交换一个的情况， 如果只交换一个肯定可以排出唯一的结果
所以有 C(4,1)*C(4,1) =16种
然后考虑交换2个的情况，A中2，3不能同时换出，B中8,9不能同时换出，剩下的可以排出唯一结果，所以有(C(4,2)-1)*(C(4,2)-1) = 25种
交换3个和4个的情况，肯定不能排出符合条件的结果
所以一共有 1+16+25 = 42种

坐等更好的解法

Answer 2

1和10的位置必须是确定的，所以只需要对剩余的八个进行排列（o表示未确定）：
1 o
o o
o o
o o
o 10
从逆向考虑，排除不可能的情况。全排列为8C4=70（当然包括了不可能的情况），只要考虑其中一列确定，那么另一列自然确定（因为同一列从上到下依次增大）。接着考虑不可能的情况，剩余的数为2~9，首先左边那列如果2和3中一个都不取，那么必然不可能，排除6C4=15；第二，如果左边那列只取了2或3之中的一个，这里有两种情况，假设是2，那么填上自然确定的数后情况为：
1 3
2 o
o o
o o
o 10
剩下4~9，排除o o o(如果左边那列三个数全部从6、7、8、9里面取)，4C3=4，排除o 8 9（o为4、5中的一个，两种情况），所以这种情况排除了2*（4C3+2）=12种；最后，如果左边同时选了2、3，但剩余的选了8和9也是不可以的，所以排除，1种。总共排除15+12+1=28种，所以可能的排列为70-28=42种。