HMMT 二月 2014 · 团队赛 · 第 9 题
HMMT February 2014 — Team Round — Problem 9
题目详情
- [ 35 ] For integers m, n 1, let A ( n, m ) be the number of sequences ( a , · · · , a ) of integers satisfying 1 nm the following two properties: (a) Each integer k with 1 k n occurs exactly m times in the sequence ( a , · · · , a ). 1 nm (b) If i , j , and k are integers such that 1 i nm and 1 j k n , then j occurs in the sequence ( a , · · · , a ) at least as many times as k does. 1 i For example, if n = 2 and m = 5, a possible sequence is ( a , · · · , a ) = (1 , 1 , 2 , 1 , 2 , 2 , 1 , 2 , 1 , 2). On 1 10 the other hand, the sequence ( a , · · · , a ) = (1 , 2 , 1 , 2 , 2 , 1 , 1 , 1 , 2 , 2) does not satisfy property (2) for 1 10 i = 5, j = 1, and k = 2. Prove that A ( n, m ) = A ( m, n ).
解析
- [ 35 ] For integers m, n ≥ 1, let A ( n, m ) be the number of sequences ( a , · · · , a ) of integers satisfying 1 nm the following two properties: (a) Each integer k with 1 ≤ k ≤ n occurs exactly m times in the sequence ( a , · · · , a ). 1 nm (b) If i , j , and k are integers such that 1 ≤ i ≤ nm and 1 ≤ j ≤ k ≤ n , then j occurs in the sequence ( a , · · · , a ) at least as many times as k does. 1 i For example, if n = 2 and m = 5, a possible sequence is ( a , · · · , a ) = (1 , 1 , 2 , 1 , 2 , 2 , 1 , 2 , 1 , 2). On 1 10 the other hand, the sequence ( a , · · · , a ) = (1 , 2 , 1 , 2 , 2 , 1 , 1 , 1 , 2 , 2) does not satisfy property (2) for 1 10 i = 5, j = 1, and k = 2. Prove that A ( n, m ) = A ( m, n ). Answer: N/A Solution 1: We show that A ( n, m ) is equal to the the number of standard Young tableaux with n rows and m columns (i.e. fillings of an n × m matrix with the numbers 1 , 2 , ..., nm so that numbers are increasing in each row and column). Consider the procedure where every time a k appears in the sequences, you add a number to the leftmost empty spot of the k -th row. Doing this procedure will result in a valid standard Young tableau. The entries are increasing along every row because new elements are added from left to right. The elements are also increasing along every column. This is because the condition about the sequences implies that there will always be at least as many elements in row i as there are in row j for i < j . At the end of this procedure, the Young Tableaux has been filled because each of the n numbers have been added m times. Now, consider a n × m standard Young tableau. If the number p is in row k , you add a k to the sequence. This will produce a valid sequence. To see this, suppose that p appears in the entry ( x, y ). Then all of the entries ( q, y ) where q < x have already been added to the sequence because they must contain entries less than p . Thus, the numbers 1 through x − 1 have all already been added at least y times Then, when we process p , we are adding the y -th x , which is valid. At the end of this procedure, n numbers have been added m times to the sequence. The two procedures given above are inverses of each other. Thus, A ( n, m ) is equal to the number of n × m standard Young tableaux. For every n × m Tableaux, we can transpose it to form an m × n tableau. The number of such tableaux is A ( m, n ). Thus, A ( n, m ) = A ( m, n ). Solution 2: We can also form a direct bijection to show A ( n, m ) = A ( m, n ), as follows. Suppose that a = ( a , . . . , a ) is a sequence satisfying properties 1 and 2. We will define a sequence f ( a ) = 1 mn ( b , . . . , b ) satisfying the same properties 1 and 2, but with m and n switched. 1 nm The bijection f is simple: just define b , for 1 ≤ i ≤ nm , to be equal to the number of j with i 1 ≤ j ≤ i such that a = a . In other words, to obtain f ( a ) from a , replace the k th occurrence of j i each number with the number k . For example, if n = 2 and m = 5, then f (1 , 1 , 2 , 1 , 2 , 2 , 1 , 2 , 1 , 2) = (1 , 2 , 1 , 3 , 2 , 3 , 4 , 4 , 5 , 5). First, it is clear that f ( a ) satisfies property 1 with m and n switched. Indeed, it follows directly from the definition of f that for each pair ( k , k ) with 1 ≤ k ≤ n and 1 ≤ k ≤ m , there is exactly one 1 2 1 2 index i for which ( a , b ) = ( k , k ). This implies the desired result. i i 1 2 Second, we show that f ( a ) satisfies property 2 with m and n switched. For this, suppose that i, j, k are integers with 1 ≤ i ≤ nm and 1 ≤ j ≤ k ≤ m . Then, the number of times that k appears in the sequence ( b , . . . , b ) is exactly equal to the number of integers ℓ with 1 ≤ ℓ ≤ n such that ℓ appears at 1 i least k times in the sequence ( a , . . . , a ). Similarly, the number of times that j appears in the sequence 1 i ( b , . . . , b ) is exactly equal to the number of integers ℓ with 1 ≤ j ≤ n such that ℓ appears at least j 1 i times in the sequence ( a , . . . , a ). In particular, the number j appears in the sequence ( b , . . . , b ) at 1 i 1 i least as many times as k does. Now, we show that f is a bijection. We claim that f is actually an involution; that is, f ( f ( a )) = a . (Note in particular that this implies that f is a bijection, and its inverse is itself.) Fix an index i with 1 ≤ i ≤ mn . Let ℓ = a and k = b ; then, k is the number of times that the term ℓ i i appears in the sequence ( a , . . . , a ). It is enough to show that ℓ is the number of times that the term k 1 i appears in the sequence ( b , . . . , b ). First, note that by definition of f , the number of times k appears 1 i in the sequence ( b , . . . , b ) is equal to the number of integers j such that the sequence ( a , . . . , a ) 1 i 1 i contains the number j at least k times. Now, ℓ occurs exactly k times in the sequence ( a , . . . , a ). So by property 2, each j with j ≤ ℓ appears 1 i at least k times in the sequence ( a , . . . , a ). Furthermore, each j with j > ℓ appears at most k − 1 1 i times in the sequence ( a , . . . , a ) and thus appears at most k − 1 times in the sequence ( a , . . . , a ) as 1 i − 1 1 i well (because a = ℓ ). Therefore, the number of integers j such that the sequence ( a , . . . , a ) contains i 1 i the number j at least k times is exactly equal to ℓ . This shows the desired result. Note: The bijections given in solutions 1 and 2 can actually be shown to be the same.