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

PUMaC 2012 — Combinatorics (Division A) — Problem 4

[ 4 ] How many (possibly empty) sets of lattice points { P , P , . . . , P } , where each point P = 1 2 M i ( x , y ) for x , y ∈ { 0 , 1 , 2 , 3 , 4 , 5 , 6 } , satisfy that the slope of the line P P is positive for each i i i i i j 1 ≤ i < j ≤ M ? An infinite slope, e.g. P is vertically above P , does not count as positive. i j

解析

Consider the general case for P = ( x , y ) ∈ Z , where here N = 7. For each value of M with i i i N ( ) N 0 ≤ M ≤ N , there are ways to pick each of the x- and y-coordinates of the M points, M 1 since the M x- and y-coordinates are distinct integers between 0 and N , inclusive. Hence, the answer is ( ) ( ) ( ) N 2 ∑ N 2 N 14 = = = 3432 M N 7 M =0 by Vandermonde’s identity. Alternatively, consider the following bijection to the number of paths from (0 , − 1) to ( N, N − 1) travelling only up or right at lattice points: keep travelling right until you reach one of the values of x , at which point you move up to P and repeat. i i Conversely, each such path corresponds to the set of points where an ‘up’ step transitions to (2 N )! a ‘right’ step. There are such paths. N ! N !