HMMT 二月 2021 · 团队赛 · 第 4 题
HMMT February 2021 — Team Round — Problem 4
题目详情
- [60] Let k and n be positive integers and let k S = { ( a , . . . , a ) ∈ Z | 0 ≤ a ≤ · · · ≤ a ≤ n, a + · · · + a = k } . 1 k k 1 1 k Determine, with proof, the value of ( )( ) ( ) ∑ n a a 1 k − 1 · · · a a a 1 2 k ( a ,...,a ) ∈ S 1 k in terms of k and n , where the sum is over all k -tuples ( a , . . . , a ) in S . 1 k ◦ ◦ ◦
解析
- [60] Let k and n be positive integers and let k S = { ( a , . . . , a ) ∈ Z | 0 ≤ a ≤ · · · ≤ a ≤ n, a + · · · + a = k } . 1 k k 1 1 k Determine, with proof, the value of ( )( ) ( ) ∑ n a a 1 k − 1 · · · a a a 1 2 k ( a ,...,a ) ∈ S 1 k in terms of k and n , where the sum is over all k -tuples ( a , . . . , a ) in S . 1 k Proposed by: Milan Haiman ( ) ( ) k + n − 1 k + n − 1 Answer: = k n − 1 Solution 1: Let T = { ( b , . . . , b ) | 0 ≤ b , . . . , b ≤ k, b + · · · + b = k } . 1 n 1 n 1 n The sum in question counts | T | , by letting a be the number of b that are at least i . By stars and i j ( ) k + n − 1 bars, | T | = . k One way to think about T is as follows. Suppose we wish to choose k squares in a grid of squares with k rows and n columns, such that each square not in the bottom row has a square below it. If we divide the grid into columns and let b be the number of chosen squares in the j th column then we get that j T is in bijection with valid ways to choose our k squares. On the other hand, if we divide the grid into rows, and let a be the number of chosen squares in the i i th row (counting up from the bottom), then we obtain the sum in the problem. This is because we ( ) ( ) n a i − 1 have choices for the squares in the first row, and choices for the squares in the i th row, a a 1 i given the squares in the row below, for each i = 2 , . . . , k . Solution 2: Define ( ) ( ) ∑ n a k − 1 n a + ··· + a 1 k F ( x, y ) = · · · x y , k a a 1 k n,a ,...,a 1 k where the sum is over all nonegative integers n, a , . . . , a (the nonzero terms have n ≥ a ≥ · · · ≥ a ). 1 k 1 k n k Note that we are looking for the coefficient of x y in F ( x, y ). By first summing over a on the inside k k and using the Binomial theorem, we obtain ( ) ( ) ∑ n a k − 2 n a + ··· + a a 1 k − 1 k − 1 F ( x, y ) = · · · x y (1 + y ) . k a a 1 k − 1 n,a ,...,a 1 k − 1 Now, we repeat this by summing over a , then a , and so on. We obtain k − 1 k − 2 ∑ n k n F ( x, y ) = x (1 + y + · · · + y ) . k n ( ) k + n − 1 k k n So the answer is just the coefficient y in (1 + y + · · · + y ) . By stars and bars, this is . k Although we didn’t need it, another way to write F ( x, y ) is k 1 F ( x, y ) = . k k 1 − x − xy − · · · − xy Solution 3: Let ′ ′ S ( n, k, k ) = { ( a , . . . , a ) | 0 ≤ a ≤ · · · ≤ a ≤ n, a + · · · + a = k } , 1 k k 1 1 k and note that S ( n, k, k ) is the set S in the problem. Define ( )( ) ( ) ∑ n a a 1 k − 1 ′ f ( n, k, k ) = · · · . a a a 1 2 k ′ ( a ,...,a ) ∈ S ( n,k,k ) 1 k ′ Now, consider ( a , . . . , a ) ∈ S ( n, k, k ). We have 1 k ′ ia ≤ a + · · · + a = k . i 1 k ′ k ′ ′ So a ≤ . In particular, if k > k , then we have a = 0 for each k < i ≤ k . This means that i i i ′ ′ ′ ′ f ( n, k, k ) = f ( n, k , k ) if k > k . Now, let f ( n, k ) = f ( n, k, k ) be the answer. Splitting the sum based on the possible values of a gives 1 ( ) ∑ n f ( n, k ) = f ( a , k − 1 , k − a ) . 1 1 a 1 a 1 For k > 0, we must have a ≥ 1, which means 1 f ( a , k − 1 , k − a ) = f ( a , k − a , k − a ) = f ( a , k − a ) . 1 1 1 1 1 1 1 So, we obtain the recurrence ( ) ∑ n f ( n, k ) = f ( a , k − a ) . 1 1 a 1 a 1 ( ) k + n − 1 Now we claim f ( n, k ) = . We proceed by induction, with our base case being k = 1. The claim k is easy to verify for k = 1. In the inductive step, we obtain ( )( ) ( ) ∑ n k − 1 k + n − 1 f ( n, k ) = = , a k − a k 1 1 a 1 where we applied Vandermonde’s identity in the last equality. ◦ ◦ ◦