PUMaC 2012 · 组合（B 组） · 第 4 题

PUMaC 2012 — Combinatorics (Division B) — Problem 4

[ 4 ] For a set S of integers, define max( S ) to be the maximal element of S . How many non-empty subsets S ⊆ { 1 , 2 , 3 , . . . , 10 } satisfy max( S ) ≤ | S | + 2?

解析

For each value of | S | between 1 and N − 2, the subset S consists of | S | of the integers in ( ) | S | +2 { 1 , 2 , . . . , | S | + 2 } . Thus, there are possible subsets. Hence the answer is, with N = 10, | S | ( ) ( ) N − 2 ∑ i + 2 N + 1 N + 1 + = N + = 175 , 2 3 i =1 where we applied the hockey-stick identity. The hockey-stick identity comes with a combinatorial interpretation: instead we can think about choosing 3 distinct integers from { 1 , 2 , . . . , N + 1 } : the value of | S | + 3 and the two numbers in { 1 , 2 , . . . , | S | + 2 } to exclude from S . 1