搜索
组合数学专题•两个基本计数原理•加法原理•乘法原理•排列问题•线排列从n个不同的元素中，取r个按次序排列，称为从n中取r个排列，其排列数记为P（n，r）•圆排列从集合S＝{a1,a2,…,an}的n个不同元素中，取出r个元素按照某种次序排成一个圆圈，称这样的排列为圆排列。•重排列：排列的一种，指从n个不同元素中取出m个元素，元素允许重复，按照一定的顺序排成一列，这种排列称为从n个不同的元素中每次取出M个重复的排列，由乘法原理可知其排列数为n×n×……×n＝n的m次方。错排公式某人写了n封信和n个信封，如果所有的信都装错了信封。求所有的信都装错信封,共有多少种不同情况。分析思路：1、当N=1和2时，易得解～，假设F(N-1)和F(N-2)已经得到，重点分析下面的情况：4、后者简单，只能是没装错的那封和第N封交换信封，没装错的那封可以是前面N-1封中的任意一个，故=F(N-2)*(N-1)3、前者，对于每种错装，可从N-1封信中任意取一封和第N封错装，故=F(N-1)*(N-1)2、当有N封信的时候，前面N-1封信可以有N-1或者N-2封错装得到如下递推公式：基本形式：d[1]=0;d[2]=1递归式：d[n]=(n-1)*(d[n-1]+d[n-2])这就是著名的错排公式鸽巢原理•鸽巢原理是组合数学中最简单也是最基本的原理，也叫抽屉原理。即“若有n个鸽子巢，n+1个鸽子，则至少有一个巢内有至少有两个鸽子。”•例１367人中至少有２人的生日相同。•例２10双手套中任取11只，其中至少有•两只是完整配对的。•例３参加一会议的人中至少有２人认识•的别的参加者的人数相等。练习•=2356•=3219•=1496•=2068•Hdoj:1517,1524,1525,1536,1564