HMMT 二月 2012 · COMB 赛 · 第 8 题

英文解析

8. How many ways can one color the squares of a 6 x 6 grid red and blue such that the number of redsquares in each row and column is exactly 2?
   Answer: 67950 Assume the grid is n × n . Let f ( n ) denote the number of ways to color exactly twosquares in each row and column red. So f (1) = 0 and f (2) = 1. We note that coloring two squaresred in each row and column partitions the set 1 , 2 , . . . , n into cycles such that i is in the same cycle as,
   and adjacent to, j iff column i and column j have a red square in the same row. Each i is adjacent totwo other, (or the same one twice in a 2-cycle).
   ( )
   Now consider the cycle containing 1, and let it have size k . There are ways to color two squaresnred in the first column. Now we let the column that is red in the same row as the top ball in the first 2
   column, be the next number in the cycle. There are n − 1 ways to pick this column, and n − 2 ways topick the second red square in this column (unless k = 2). Then there are ( n − 2)( n − 3) ways to pickthe red squares in the third column. and ( n − j )( n − j + 1) ways to pick the j th ones for j ≤ k − 1.
   Then when we pick the k th column, the last one in the cycle, it has to be red in the same row as the second red square in column 1, so there are just n − k + 1 choices. Therefore if the cycle has length kthere aren ( n − 1) n !( n − 1)!
   × ( n − 1)( n − 2) × . . . × ( n − k + 1)( n − k + 2) × ( n − k + 1) ways, which equals: .
   2 2( n − k )!( n − k )!
   Summing over the size of the cycle containing the first column, we getn
   ∑
   1 ( n )!( n − 1)!
   f ( n ) = f ( n − k )
   2 ( n − k )!( n − k )!
   k =2
   ∑n
   2 nf ( n ) f ( n − k )
   n ! n ! ( n − k )!( n − k )!=
   k =2
   2 nf ( n ) 2( n − 1) f ( n − 1) f ( n − 2) − =
   n ! n ! ( n − 1)!( n − 1)! ( n − 2)!( n − 2)!
   We thus obtain the recursion:
   n ( n − 1)2
   f ( n ) = n ( n − 1) f ( n − 1) + f ( n − 2)
   Combinatorics Test 2
   Then we get:
   f (1) = 0
   f (2) = 1
   f (3) = 6
   f (4) = 12 × 6 + 18 = 90
   f (5) = 20 × 90 + 40 × 6 = 2040
   f (6) = 30 × 2040 + 75 × 90 = 67950.