|
对于两个有限集合M 问题一 棋盘上的方格如图1，一个m×n的棋盘（指有包含边界在内有m条竖线和n条横线）．  图1 （1）有多少个小正方形方格？ （2）有多少个“对顶”方格组（包括旋转对称后的形状）？ （1）解 设M是小正方形方格的集合，N是前m?1条竖线和n–1条横线形成的交点的集合．那么小正方形方格和N中的点是一一映射的，因此card(M)=card(N)=(m?1)(n?1). （2）解 设M是“对顶”方格组的集合，通过取两个小方格的公共点P以及形成方向τ，于是(P,τ)构成集合N．显然这也是一个一一映射，于是card(M)=card(N)=2(m?2)(n?2). 思考题 有多少个“犄角”方格组（包括旋转对称后的形状）呢？又有多少个“情侣”方格组（包括旋转后的形状）？（如图2）  图2 答案分别为4(m–2)(n–2)和(m?2)(n?1)+(m?1)(n?2)． 提示 对于“犄角”，可以取中心点和缺角方向；对于“情侣”，可以取中间的小竖线或小横线．
问题二 棋盘上的“方格”如图3，在一个m×n的矩形网格（指有包含边界在内有m条竖线和n条横线）中有多少个矩形？  图3 解 如图4，横线上的两个不同点和竖线上的两个不同点与矩形一一对应，于是所求矩形数为C2mC2n.  图4 思考题 如图5，在一个n级正三角网格中有多少个平行四边形呢？  图5 答案是3C4n． 提示 如图6，每条横线上的四个不同点都与平行四边形一一对应．  图6 问题三 圆周上的点（1）圆周上有n个点，用弦把它们连接起来，那么 （1）有多少条不同的弦？ （2）这些弦至多有多少个交点（指在圆内部的）？ （3）这些弦至多将圆分成多少个无公共部分的区域？ （1）解 如图7，圆上的两个无序点对与弦一一对应，因此数目为C2n；  图7 （2）解 圆上的四个无序点对与交点一一对应（圆内接四边形对角线的交点），因此数目为C4n；  图8 （3）解 新添一条弦l时，弦l与其他弦的交点将l分割为交点数加1条线段，每条线段都对应一个新增区域．因此所求数目为1+C2n+C4n． 思考题 空间有n个平面，这些平面都过点P，则这n个平面至多分空间为多少个部分？ 答案是n2–n+2．
问题四 圆周上的点（2）圆周上有2n+1个点，其中n+1个点上标“+1”，n个点上标“–1”，如果可以找到某个标有“+1”的点作为起点，当顺时针沿圆周前进时将所遇到的点（包括起点）上标的数相加得到的和始终为正数，就称这种标记法是好标记法． （1）求好标记法的总数． （2）圆周上有2n个点，以这些点为端点连互不相交的n条弦，求不同的连法总数． （1）解 对于任何一种标记法，我们将顺时针相邻的“+1”“–1”（指顺时针前进时先遇到“+1”后遇到“–1”）同时抹去，可以证明抹去的前后对标记法的好坏没有影响．不停的重复这一过程，则最后只剩一个标有“+1”的点，显然此时标记法为好的．因此所有的标记法都是好标记法，显然其数目为12n+1Cn2n+1=1n+1Cn2n. （2）解 通过对题（1）的进一步探索可知，每一种将圆周上2n+1个点标记为n+1个+1点，和n个–1点的方法唯一确定一个顺时针前进的方案（即起点）．我们将这个起点删去，剩下的2n个点在顺时针方向上一定为“+1”“–1”“+1”“–1”，…，此时将顺时针相邻的这些“+1”“–1”点用弦连接起来，就得到互不相交的n条弦．这样我们就建立了从弦的连法到好标记法的单射． 反过来，如果我们有了一种弦的连法，就可以从某条弦的端点出发顺时针前进，对每条弦的两个端点都是先遇到的端点标上“+1”，后遇到的端点标上“–1”，然后在最后回到出发点时添上一个标有“+1”的点．这样我们就建立了从好标记法到弦的连法的单射． 综上，所求的不同连法数为1n+1Cn2n． 注 注意考虑圆排列．
问题五 电影购票电影票每张50元，如果有m+n个人排队买票，其中m个人各持有50元面值的钞票1张，另外n个人各持有100元面积的钞票1张，而票房没有预备找零．有多少种方法可以将这m+n个人排成一列，顺序购票，使得无需因为需要等待找零而耽误时间？ 解 为了使得问题更加直观，这里给一个几何解释（集合中的W直线问题）．在一个m×n的网格中，左下角的原点O(0,0)出发，每次向右（表示接待的观众持有50元的钞票）或向上（表示接待的观众持有100元的钞票）移动，最终到达P(m,n)．我们需要找到在直线y=x下方（包括边界）的路径条数．  图9 由于第一步一定向右，也就是可以认为出发点为A(1,0)，如图9． 从反面考虑问题．设M为穿过直线y=x（表示会经过直线上方的点）的从A→P的的路径组成的集合，N为从A′(0,1)出发最终到达P(m,n)的路径组成的集合． 如图10，利用对称，不难构造从M到N的单射与从N到M的单射，因此card(M)=card(N)=Cn?1m+n, 于是所求的排列数为Cnm+n?Cn?1m+n.  图10 特别的，当m=n时有Cnm+n?Cn?1m+n=Cn2n–Cn?12n=1n+1Cn2n, 这个数称为卡特兰（catalan）数．
问题六 数的拆分（2012年北京市海淀区二模）将一个正整数n表示为a1+a2+?+ap（p∈N?）的形式，其中ai∈N?，i=1,2,?,p，且a1?a2???ap，记所有这样的表示法的种数为f(n)（如4=4，4=1+3，4=2+2，4=1+1+2，4=1+1+1+1，故f(4)=5）．对任意正整数n，比较f(n+1)与12[f(n)+f(n+2)]的大小，并给出证明． 解 f(n+1)?12[f(n)+f(n+2)]．只需要证明f(n+2)–f(n+1)?f(n+1)–f(n)，证明如下： 注意到在n的所有表示法前加上“1+”就可以得到(n+1)的表示法中以1为第一项的表示法，因此(n+1)的表示法中以1为第一项的有f(n)种，而不以1为第一项的有f(n+1)–f(n)种； 类似的，(n+2)的表示法中不以1为第一项的有f(n+2)–f(n+1)种；在(n+1)的表示法中所有不以1为第一项的表示法中的最后一项加上1就可以得到(n+2)的表示法中不以1为第一项的表示法，且这些表示法均不相同．这样就建立了从(n+1)的不以1为第一项的表示法到(n+2)的不以1为第一项的表示法的单射． 因此f(n+2)–f(n+1)?f(n+1)–f(n).
更多精彩请关注数海拾贝：
|
|
|
<='' p='' style='max-width: 650px; '>
