HMMT 二月 2007 · COMB 赛 · 第 5 题

英文解析

5. [ 5 ] Determine the number of ways to select a positive number of squares on an 8 × 8 chessboard suchthat no two lie in the same row or the same column and no chosen square lies to the left of and belowanother chosen square.
   ( ) ( )1
   16 8
   Answer: 12869 = − 1 . If k is the number of squares chosen, then there are ways to choose k
   8 k
   ( )
   columns, and ways to choose k rows, and this would uniquely determine the set of squares selected.8
   Thus the answer isk
   ( )( ) ( )( ) ( )
   8 8
   ∑ ∑
   8 8 8 8 16 = − 1 + = − 1 + = 12869
   k k k k 8
   k =1 k =0