HMMT 二月 2003 · 团队赛 · 第 2 题

英文解析

2. Suppose A is a set with n elements, and k is a divisor of n . Find the number ofconsistent k -configurations of A of order 1.
   Solution: Given such a k -configuration, we can write out all the elements of one ofthe k -element subsets, then all the elements of another subset, and so forth, eventuallyobtaining an ordering of all n elements of A . Conversely, given any ordering of theelements of A , we can construct a consistent k -configuration of order 1 from it bygrouping together the first k elements, then the next k elements, and so forth. In fact,
   n/keach consistent k -configuration of order 1 corresponds to ( n/k )!( k !) different suchorderings, since the elements of A within each of the n/k k -element subsets can beordered in k ! ways, and the various subsets can also be ordered with respect to eachother in ( n/k )! different ways. Thus, since there are n ! orderings of the elements of A ,
   n !
   we get different consistent k -configurations of order 1.
   n/k
   ( n/k )!( k !)