Maths Olympiad Prep

Library / /541 of 860

Combinatorics Difficulty 5.3 AIME, harder Find the answer

Suppose AA is a set with nn elements, and kk is a divisor of nn. Find the number of consistent kk-configurations of AA of order 1.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Given such a k k -configuration, we can write out all the elements of one of the k k -element subsets, then all the elements of another subset, and so forth, eventually obtaining an ordering of all n n elements of A A . Conversely, given any ordering of the elements of A A , we can construct a consistent k k -configuration of order 1 from it by grouping together the first k k elements, then the next k k elements, and so forth. In fact, each consistent k k -configuration of order 1 corresponds to (n/k)!(k!)n/k (n / k)!(k!)^{n / k} different such orderings, since the elements of A A within each of the n/k n / k k k -element subsets can be ordered in k! k! ways, and the various subsets can also be ordered with respect to each other in (n/k)! (n / k)! different ways. Thus, since there are n! n! orderings of the elements of A A , we get n!(n/k)!(k!)n/k \frac{n!}{(n / k)!(k!)^{n / k}} different consistent k k -configurations of order 1.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.