MathLabs

第1题

设 n 为正整数。令 T 为满足 x,y 为非负整数且 x+y<n 的点 (x,y) 的集合。将 T 中每个点染成红色或蓝色,并要求若 (x,y) 为红色,则第一坐标不超过 x 且第二坐标不超过 y 的所有点也为红色。设 A 为选取 n 个横坐标互不相同的蓝点的方法数,B 为选取 n 个纵坐标互不相同的蓝点的方法数。证明 A=B. nn TT (x,y)(x,y) xx yy x+y<nx+y<n TT (x,y)(x,y) TT xx yy AA nn xx BB nn yy A=BA=B
第 2/3 步:逐个移去红点
通俗地说

通过对应的删除构造左下红色理想。

ax=by=n−x−y−1a_x=b_y=n-x-y-1
详细分析

先把所有点看成蓝色,再按适当的逆拓扑顺序构造左下红色理想。当 由蓝变红时,其所在列和行中剩余的蓝点数都为 ,所以从两个多重集中删去同一个数。起初两个多重集都是 ,故始终相同。 (x,y)(x,y) n−x−y−1n-x-y-1 {1,2,…,n}\{1,2,\ldots,n\}