PUMaC 2013 · 组合（A 组） · 第 3 题

PUMaC 2013 — Combinatorics (Division A) — Problem 3

[ 4 ] How many tuples of integers ( a , a , a , a , a ) are there, with 1 ≤ a ≤ 5 for each i , so that 0 1 2 3 4 i a < a > a < a > a ? 0 1 2 3 4

解析

[ 4 ] How many tuples of integers ( a , a , a , a , a ) are there, with 1 ≤ a ≤ 5 for each i , so that 0 1 2 3 4 i a < a > a < a > a ? 0 1 2 3 4 Solution Denote by S ( n, k ) the number of tuples a < a > . . . a so 0 ≤ a , . . . , a ≤ 5 0 1 n 1 n − 1 and a = k . Then we have S (0 , 1) = S (0 , 2) = S (0 , 3) = S (0 , 4) = S (0 , 5). We next find that, n if a < k , either a < k − 1 or a = k − 1, giving 0 0 0 S (1 , k ) = S (1 , k − 1) + S (0 , k − 1) so S (1 , 1) = 0, S (1 , 2) = 1, S (1 , 3) = 2, S (1 , 4) = 3, S (1 , 5) = 4. In general, we find S (2 n + 1 , k ) = S (2 n + 1 , k − 1) + S (2 n, k − 1) S (2 n, k ) = S (2 n, k + 1) + S (2 n − 1 , k + 1) Then S (2 , 5) = 0, S (2 , 4) = 4, S (2 , 3) = 7, S (2 , 2) = 9, S (2 , 1) = 10 S (3 , 1) = 0, S (3 , 2) = 10, S (3 , 3) = 19, S (3 , 4) = 26, S (3 , 5) = 30 S (4 , 5) = 0, S (4 , 4) = 30, S (4 , 3) = 56, S (4 , 2) = 75, S (4 , 1) = 85. Summing the bottom row gives us the answer of 30 + 56 + 75 + 85 = 246 tuples.