文档介绍：1组合数学例1:将8个“车”放在8×8的国际象棋棋盘上,如果它们两两均不能互吃,那么称8个“车”处于一个安全状态。问共有多少种不同的安全状态?解:8个“车”处于安全状态当且仅当它们处于不同的8行和8列上。用一个排列a1,a2,…,a8,对应于一个安全状态,使ai表示第i行的ai列上放置一个“车”。这种对应显然是一对一的。因此,安全状态的总数等于这8个数的全排列总数8!=40320。例4:n位客人在晚会上每人与他人握手d次,d是奇数。证明n偶数。证:由于每一次握手均使握手的两人各增加一次与他人握手的次数,因此n位客人与他人握手次数的总和nd是偶数—握手次数的2倍。根据奇偶性质,已知d是奇数,那么n必定是偶数。例4从1到2n的正整数中任取n+1个,则这n+1个数中,至少有一对数,其中一个是另一个的倍数。证设n+1个数是a1,a2,···,an+1。每个数去掉一切2的因子,直至剩下一个奇数为止。组成序列r1,r2,,···,rn+1。这n+1个数仍在[1,2n]中,且都是奇数。而[1,2n]中只有n个奇数,故必有ri=rj=r,则ai=2αir,aj=2αjr。若ai>aj,则ai是aj的倍数。例5设a1,a2,···,am是正整数,则至少存在一对k和l,0≤k<l≤m,使得和ak+1+ak+2+···+al是m的倍数。证设Sh=,Sh≡rhmodm,0≤rh≤m-1,h=1,2,···,,Sl≡,1≤rh≤m-=1,2,···,,故存在rk=rl,即Sk≡Slmodm,不妨设l>-Sk=ak+1+ak+2+…+al≡0modm例6设a1,a2,a3是任意三个整数,b1b2b3为a1,a2,a3的任一排列,则a1-b1,a2-b2,a3-:a1,a2,,不妨设为x;同样b1,b2,-b1,a2-b2,a3-,a2,…,a100是由数字1和2组成的序列,+ai+1+…+ai+9≤16,1≤i≤91。则存在h和k,k>h,使得ah+1+…+ak=39??jiia1??hiia12证令Sj=,j=1,2,…,100。显然S1<S2<…<S100,且S100=(a1+…+a10)+(a11+…+a20)+…+(a91+…+a100)根据假定有S100≤10×16=160作序列S1,S2,…,S100,S1+39,…,S100++39≤160+39由鸽巢原理,=Sh+39,k>h?Sk-Sh=39即ah+1+ah+2+…+ak=39例:1)求小于10000且的含1的正整数的个数2)求小于10000的含0的正整数的个数解:1)小于10000的不含1的正整数可看做4位数,×9×9×9-1=:9999-6560=3439个2)上述方法不可直接套用来计算“含0”数的个数。0019“含1”但“不含0”。不含0的1位数有9个,2位数有92个,