HMMT 二月 2014 · 团队赛 · 第 9 题

英文解析

9. [ 35 ] For integers m, n ≥ 1, let A ( n, m ) be the number of sequences ( a , · · · , a ) of integers satisfying
   1 nmthe 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 Youngtableaux with n rows and m columns (i.e. fillings of an n × m matrix with the numbers 1 , 2 , ..., nmso that numbers are increasing in each row and column). Consider the procedure where every timea k appears in the sequences, you add a number to the leftmost empty spot of the k -th row. Doingthis procedure will result in a valid standard Young tableau. The entries are increasing along everyrow because new elements are added from left to right. The elements are also increasing along everycolumn. This is because the condition about the sequences implies that there will always be at leastas 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 thesequence. 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 mustcontain entries less than p . Thus, the numbers 1 through x − 1 have all already been added at least ytimes 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 ofn × m standard Young tableaux. For every n × m Tableaux, we can transpose it to form an m × ntableau. 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. Supposethat 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 withi
   1 ≤ j ≤ i such that a = a . In other words, to obtain f ( a ) from a , replace the k th occurrence ofj ieach 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, kare integers with 1 ≤ i ≤ nm and 1 ≤ j ≤ k ≤ m . Then, the number of times that k appears in thesequence ( b , . . . , b ) is exactly equal to the number of integers ℓ with 1 ≤ ℓ ≤ n such that ℓ appears at
   1 ileast 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 itimes in the sequence ( a , . . . , a ). In particular, the number j appears in the sequence ( b , . . . , b ) at
   1 i 1 ileast 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 iappears in the sequence ( a , . . . , a ). It is enough to show that ℓ is the number of times that the term k
   1 iappears in the sequence ( b , . . . , b ). First, note that by definition of f , the number of times k appears
   1 iin the sequence ( b , . . . , b ) is equal to the number of integers j such that the sequence ( a , . . . , a )
   1 i 1 icontains 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 iat least k times in the sequence ( a , . . . , a ). Furthermore, each j with j > ℓ appears at most k − 1
   1 itimes in the sequence ( a , . . . , a ) and thus appears at most k − 1 times in the sequence ( a , . . . , a ) as
   1 i − 1 1 iwell (because a = ℓ ). Therefore, the number of integers j such that the sequence ( a , . . . , a ) containsi 1 ithe 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.