航电春季赛（七）1010 网格计数
我们把选出来的点看成一个 2 × n 2\times n 2×n的格子，第一行填行号，第二行填列号。
那么可以将题意转化为： 2 × n 2\times n 2×n的格子，每个格子填 1 m 1~m 1 m，要求每个格子比其上面和左边更大。
考虑每个格子的选择，观察其所处在的L字形，也就是这个格子和其上面的格子和右边的格子所组成的集合，这些格子的数都不相同，并且该格子大于其上面的，小于其右边的，有明确的排名。
我们先找到满足每个L形里面所有数都不同的方法，然后再排除掉大小关系不正确的情况。
对于前者，我们从依次对 ( 1 , n ) , ( 2 , n ) , ( 1 , n − 1 ) , ( 2 , n − 1 ) , . . . , ( 1 , 1 ) , ( 2 , 1 ) (1,n),(2,n),(1,n-1),(2,n-1),...,(1,1),(2,1) (1,n),(2,n),(1,n−1),(2,n−1),...,(1,1),(2,1)进行填数，产生的方案数为
∏ 1 ≤ i ≤ 2 , 1 ≤ j ≤ n ( m − ( i − 1 ) − ( n − j ) ) = m ! ( m − n ) ! × ( m − 1 ) ! ( m − n − 1 ) ! \prod_{1\le i \le 2, 1 \le j \le n}(m-(i-1)-(n-j))=\frac{m!}{(m-n)!}\times \frac{(m-1)!}{(m-n-1)!} 1≤i≤2,1≤j≤n∏(m−(i−1)−(n−j))=(m−n)!m!×(m−n−1)!(m−1)!
然后考虑后者，依次从 ( 2 , 1 ) , ( 1 , 1 ) , ( 2 , 2 ) , ( 1 , 2 ) , . . . , ( 2 , n ) , ( 1 , n ) (2,1),(1,1),(2,2),(1,2),...,(2,n),(1,n) (2,1),(1,1),(2,2),(1,2),...,(2,n),(1,n)删除掉不合法的情况，对于当前格子 ( i , j ) (i,j) (i,j)，因为其所在的L形仍然保持无序，也就是每个数字本质上都是相同的，有 1 ∣ L ∣ \frac{1}{|L|} ∣L∣1的情况是合法的，即刚好满足当前格子的数大于上面，小于右边，因此总共需要乘上
∏ 1 ≤ i ≤ 2 , 1 ≤ j ≤ n 1 i + ( n − j ) = 1 n ! × ( n + 1 ) ! \prod_{1\le i \le 2, 1 \le j \le n}\frac{1}{i+(n-j)}=\frac{1}{n!\times (n+1)!} 1≤i≤2,1≤j≤n∏i+(n−j)1=n!×(n+1)!1
因此总共为
m ! ( m − n ) ! × ( m − 1 ) ! ( m − n − 1 ) ! × 1 n ! × ( n + 1 ) ! \frac{m!}{(m-n)!}\times \frac{(m-1)!}{(m-n-1)!}\times \frac{1}{n!\times (n+1)!} (m−n)!m!×(m−n−1)!(m−1)!×n!×(n+1)!1
= m ! ( m − n ) ! × n ! × ( m − 1 ) ! ( m − n − 1 ) ! × n ! × n ! ( n + 1 ) ! =\frac{m!}{(m-n)!\times n!}\times \frac{(m-1)!}{(m-n-1)!\times n!}\times \frac{n!}{(n+1)!} =(m−n)!×n!m!×(m−n−1)!×n!(m−1)!×(n+1)!n!
= C m n C m − 1 n 1 n + 1 =C_m^nC_{m-1}^n\frac{1}{n+1} =CmnCm−1nn+11