满足不同条件的映射的个数1、设BA,为有限集合,nBmA=,=,则(1)从A到B的映射有个;(2)若nm,则从A到B的单射有个;(3)若mn,则从A到B的满射有个.2、设BA,为有限集合,nBmA=,=,则(1)从A到B的映射有个;(2)若5nm,4,则从A到B的单射有个;(3)若4n5,m,则从A到B的满射有个.3、设集合4,6BA,则从A到B的满射的个数为______________,从A到B的映射的个数为_______________.4、集合},,,{dcba到集合}3,2,1{的映射有个,满射有个。基本的排列组合公式1、圆周上有n个点,这些点可以确定该圆的______条弦.如果这些弦中无三弦共点,则这些弦在该圆内确定了__________个交点.2、用3个1,2个2,5个3这十个数字能组成__________________个4位偶数.3、n元集的r-可重排列数为_________;n元集的r-无重排列数为__________;n元集的r-可重组合数为_________;n元集的r-无重组合数为___________;n元集的r-圆排列数为___________.4、集合},,,{dcba的3-可重排列有个,3-无重排列有个,3-可重组合有个,3-无重组合有多少个。5、口袋中有白球5个,红球3个,黑球2个,每次从中取出5个,有__________________种不同的取法.方程的正整数解与非负整数解的个数1、(1)方程rxxxn21的非负整数解的个数为(2)方程rxxxn21的正整数解的个数为2、(1)方程10621xxx的非负整数解的个数为(2)方程10621xxx的正整数解的个数为多项式展开式的项数与各项的系数1、多项式54321)(xxxx的展开式中共有_____________项,其中项4331xxx的系数为______________,展开式中各项系数的和为______________.2、多项式74321)(xxxx的展开式中一共有_______________项,其中项433221xxxx的系数为____________________.生成函数展开式1、nx)1(____________________________________________________.2、设幂级数nxxh)1()(的生成序列为0kka,则ka______,从而nxxh)1()(_____________________________________________.更列问题1、更列数nD________________________________________________.2、10个人寄存了帽子,在取回帽子时恰有4个人领会自己帽子的方式数是__________.3、八个字母A,B,C,D,E,F,G,H的全排列中只有4个元素不在原来位置上的排列数为.欧拉函数1、(1)设n为任意正整数,n的欧拉函数)(n为nS,,2,1中与n互素的整数的个数,则)(n_________.)120(_______,)180(___________.递推关系1、设平面上有n个椭圆,其中任意两个椭圆恰有两个交点,同时没有三个椭圆共点,这样的n个椭圆把平面分成na个区域,则序列1}{nna满足的递推关系为_________________________,其解为________________.容斥原理1、(1)有8个小孩排成一排,如果让他们交换座位,使得每个小孩的前边都不是原来他前边的孩子,则有______________种方法;(2)有8个小孩坐在旋转木马上,如果让他们交换座位,使得每个小孩的前边都不是原来他前边的孩子,则有______________种方法.2、在1和100之间既不是某个整数的平方,也不是某个整数的立方的整数有_____________个.Catalan序列与两类Stirling数1、第二类Sirtling数满足的递推关系和初始条件为______________.2、第一类Stirling数1(,)Snk满足的递推关系为___________________.3、Catalan序列的通项为nC。中国剩余定理1、除以3的余数为2,除以5的余数为1,除以7的余数为4的小于105的正整数为。Ramsey数1、Ramsey数)2,8(R,)3,3(R,)4,3(R,)3,3,3(R。组合恒等式1、证明nnnnnnn12111)1(22111.2、用三种方法证明下列组合恒等式102221100knnknnnnnnnkn3、用三种方法证明下列组合恒等式1)!1(!33!2211nnn!!4、用两种方法证明下列组合恒等式)1(,11)1(11nnnknknkk生成函数和容斥原理1、记mnS,为集合},,2,1{n到集合},,2,1{m上的满射的个数)(mn.(1)用生成函数为工具,计算mnS,.(2)用容斥原理计算mnS,.2、由3,2,1组成的n位数,要求3,2,1在其中每个至少出现1次,求所有这种n位数的个数n.(分别用生成函数法和容斥原理法求解)3、确定多重集}5,4,3{cbaS的10-可重组合的个数.(分别用生成函数法和容斥原理法求解)4、用1,2,3,4四个数字能组成多少个n位数,其中要求1出现2次或3次,2最多出现1次,3没有限制,4出现偶数次。特别地,满足条件的5位数有多少个?递推关系和容斥原理1、用nf表示用21棋盘完全覆盖n2棋盘的方式数,并规定10f.(1)建立序列0}{nnf的递推关系和初始条件;(2)用两种方法解这个递推关系.2、用nu表示由4,3,2,1的元组成的包含偶数个1的n位数的个数.(1)建立序列0}{nnu的递推关系和初始条件;(2)用三种方法解这个递推关系.3、设),,,(21naaa是},,2,1{n的一个全排列且niiai,,2,1,,求的个数nD.(分别用递推关系和容斥原理法求解)4、设平面上有n个椭圆,其中任意两个椭圆恰有两个交点,同时没有三个椭圆共点,这样的n个椭圆把平面分成na个区域,确定序列1}{nna满足的递推关系,并用特征方程法,迭代归纳法和母函数法求1}{nna的表达式.5、设在集合12,,,nAaaa上定义一个非交换非结合的乘法运算“”,求A的全体元作成的乘积的形式的个数nu.6、分别用特征方程法,迭代归纳法和母函数法解定解问题102(1)2nnuunu。7、设集合},,{cbaA,na表示A的a不相邻的n-可重排列的个数。写出0}{nna满足的递推关系,并解之。8、设),,,(21naaa是n,,2,1的一个全排列,且1,,2,1,11niaaii,计算这样的全排列的个数nQ,并给出nQ与更列数nD的关系。鸽巢原理1、将平面上的每一个点都以k种颜色中的任一种颜色染色,是一个正实数.证明存在这样的两个相似三角形,它们的相似比是,并且每一个三角形的三个顶点同色.2、用抽屉原理证明:每个包含1mn个不同项的实数序列121,,,mnaaa必有一1m项的递增子列或有一个1n项的递减子列.3、正方形被9条直线分割,每条直线都把该正方形分成面积比为3:2的两个梯形.证明:这9条线中至少有三条过同一个点.4、设m和n为互素的正整数,并令a和b为两整数且10ma以及10nb.证明存在一个正整数x,使得x除以m的余数为a,并且x除以n的余数是b,即x既可以写成apmx的同时又可以写成bqnx的形式,这里qp,是两个整数.