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

HMMT February 2003 — Team Round — Problem 1

(a) [10] How many k -configurations are there of a set that has n elements? (b) [10] How many k -configurations that have m elements are there of a set that has n elements?

解析

(a) How many k -configurations are there of a set that has n elements? ( ) n Solution: An n -element set has subsets of size k , and we can construct a k - k configuration by independently choosing, for each subset, whether or not to include it, n ( ) k so there are 2 k -configurations. (b) How many k -configurations that have m elements are there of a set that has n elements? ( ) ( ) n n ( ) k Solution: Again, an n -element set has subsets of size k , so there are k - k m configurations with m elements.