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

HMMT February 2003 — Team Round — Problem 2

[15] Suppose A is a set with n elements, and k is a divisor of n . Find the number of consistent k -configurations of A of order 1.

解析

Suppose A is a set with n elements, and k is a divisor of n . Find the number of consistent k -configurations of A of order 1. Solution: Given such a k -configuration, we can write out all the elements of one of the k -element subsets, then all the elements of another subset, and so forth, eventually obtaining an ordering of all n elements of A . Conversely, given any ordering of the elements of A , we can construct a consistent k -configuration of order 1 from it by grouping together the first k elements, then the next k elements, and so forth. In fact, n/k each consistent k -configuration of order 1 corresponds to ( n/k )!( k !) different such orderings, since the elements of A within each of the n/k k -element subsets can be ordered in k ! ways, and the various subsets can also be ordered with respect to each other 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 !)