排列组合公式及恒等式推导、证明(word版)及排列组合分房问题总结

排列组合公式及恒等式推导、证明（word版）说明：因公式编辑需特定的公式编辑插件，不管是word还是pps附带公式编辑经常是出错用不了。下载此word版的，记得下载MathType公式编辑器哦，否则乱码一堆。如果想偷懒可下截同名的截图版。另外，还有PPt课件（包含了排列组合的精典解题方法和精典试题）供学友们下载。一、排列数公式：推导：把n个不同的元素任选m个排次序或n个全排序，按计数原理分步进行：第一步，排第一位：有n种选法；第二步，排第二位：有（n-1）种选法；第三步，排第三位：有（n-2）种选法；┋第m步，排第m位：有（n-m+1）种选法；┋最后一步，排最后一位：有1种选法。根据分步乘法原理，得出上述公式。二、组合数公式：推导：把n个不同的元素任选m个不排序，按计数原理分步进行：第一步，取第一个：有n种取法；第二步，取第二个：有（n-1）种取法；第三步，取第三个：有（n-2）种取法；┋第m步，取第m个：有（n-m+1）种取法；┋最后一步，取最后一个：有1种取法。上述各步的取法相乘是排序的方法数，由于选m个，就有m!种排排法，选n个就有n!种排法。故取m个的取法应当除以m!,取n个的取法应当除以n!。遂得出上述公式。证明：利用排列和组合之间的关系以及排列的公式来推导证明。

将部分排列问题分解为两个步骤：第一步，就是从n个球中抽m个出来，先不排序，此即定义的组合数问题；第二步，则是把这m个被抽出来的球全部排序，即全排列。

根据乘法原理，即：组合公式也适用于全组合的情况，即求

C(n,

n)的问题。根据上述公式，C(n,

n)

=

n!/n!(n-n)!

=

n!

/

n!0!

=

1。这一结果是完全合理的，因为从n个球中抽取所有n个出来，当然只有1种方法。

三、重复组合数公式：重复组合定义:从n个不同的元素中每次取一个，放回后再取下一个，如此连续m次所得的组合。重复组合数公式：（m可小于、大于、等于n,n≥1）推导：可以把该过程看作是一个“放球模型”：n个不同的元素看作是n个格子，其间一共有（n-1）块相同的隔板，用m个相同的小球代表取m次；则原问题可以简化为将m个不加区别的小球放进n个格子里面，问有多少种放法；这相当于m个相同的小球和（n-1）块相同的隔板先进行全排列：一共有（m+n-1）！种排法，再由于m个小球和（n-1）块隔板是分别不加以区分的，所以除以重复的情况：m！*（n-1）！于是答案就是：四、不全相异的全排列在不全相异的n个物体中，假设有n1个物体是相同的，n2个五题是相同的，……，nk个物体是相同的。n个物体中不相同的物体种类数一共有k种。那么，这些物体的全排列数是n!/(n1!n2!…nk!)。可以想成：n个物体直接全排列，排列完了以后，去重，第一种物体有n1!种，第二种物体有n2!种，以此类推。例：有3个红球，2个白球，把这五个球排成一行，问有多少种排法？红球和红球没有区别，白球和白球没有区别。答：一共有10种，aaabb,aabab,aabba,abaab,ababa,baaab,baaba,abbaa,babaa,bbaaa。五、排列恒等式的证明：①证明：右边=左边=右边②②证明：右边=③左边=右边③证明：右边=左边=右边④④证明：右边=⑤ 右边⑤ 证明：右边=⑥⑥ 证明：左边=(2-1)1！+（3-1）2！+（4-1）3!+…（n+1-1）n!=2!-1!+3!-2!+4!-3!…(n+1)!-n!=(n+1)!-1！=右边六、组合恒等式的证明互补性质：取出有多少种，剩下就有多少种根据分类计数原理:要么含有新加元素要么不含新加元素分类计数原理互补性质：取出有多少种，剩下就有多少种根据分类计数原理:要么含有新加元素要么不含新加元素分类计数原理:要么含有新加元素要么不含新加元素①① 证明：② ②证明：右边=③③证明：右边= =左边⑤⑤ 证明：根据组合性质，左边各式可写成：左右两边相加即得：⑥⑥证明：用数学归纳法证明。

1）当n=1时，所以等式成立。

2）假设n=k时，（k≥1，k∈N*）时等式成立。

即：

当n=k+1时，

∴等式也成立由1)、2)得，等式对n∈N*都成立。也可用二项式定理证明（略）⑦⑦证明：用归纳法同上（略）也可利用上述结论证明（略）本课件尽量避开用二项式定理，但这比较简单，暂且用一下：设由（1+1）n可得：a+b=2n=2×2n-1由（1-1）n可得a-b=0∴a=b=2n-1(不懂的去学学二项式定理)⑧⑧证明：由可得:（还记得这个恒等式吗，不记得就回过头去看③的证明）左边注：同时利用了⑥的结论。

⑨r≤⑨r≤min{m,n}用二项式定理证明太麻烦了。能偷懒就不要太勤快了。观察左边的每一项，发现均是分别从m个不同素和n个不同元素中取r个元素的一个组合，其各项之和就是所有取法，即所有组合数。其所有组合数当然等于右边。 ⑩⑩还是用偷懒法：根据第⑨的结论并结合组合的互补性质，若r=m=n即得些结论。排列组合分房问题首先看一个例子：10个人进8个房间，有多少种进法？为什么是，因为甲，乙，丙，丁...这10个人要住A,B,C,D...这8个房，甲可以有8种选择，乙也可以有8种选择...但是如果房子A选人，有10种选择，房子B选人，有10种选择，房子A.B是不能同时选择甲，或乙的，因为一个人不能同时住两个或两个以上的房子，显然，让房子选人是错误的，一定是人选房子。总结：这就是住店法，要客去选择店，不能反过来。从例子中看，一个人是不能同时住多间房的，所以把这类不能重复的元素看做“客”，一间房子可以同时住多个人，把这类可以重复的元素看做“店”，然后让客去选店。练习：1.4名候选人中，评选出1名三好学生，1名优秀干部，1名先进团员，允许一人同时得几个称号，有多少种选法？如，甲乙丙丁4人，甲获得三好学生，乙获得优秀干部，丙获得先进团员;甲获得三好学生，优秀干部，乙获得先进团员答案：先分析一下，4个人评出三个奖项，说明每一个奖项都必有一名获得者，每一个人可以获得多个奖项，如果这里面让人去选奖项，第一个人有3种选择，第二个人有3种选择...此时可能出现第一个人，第二个人甚至第三，四人全部选了三好学生，这样显然是错误的，因为4个人要评出3个奖，不能出现所有人都得了一种奖的情况。所以，换个思维，同一个奖项不能同时被颁给所有的4个人（其实应该只能有是3个人或更少的人获奖），所以把奖项看做不能重复的元素“客”，但是一个人可以同时拥有多个奖项，（比如甲获得了所有奖项，那么三个人就无法获奖），所以把人看作是可以重复的元素“店”，然后让“客”选“店”，即让奖项选人，每个奖项选择的可能性是4种，答案为。汽车上有10名乘客，沿途设有5个车站，乘客下车的不同方式有多少种？答案：如果让人选车站，1个人可以有5种选择自己在哪个车站下车，如果让车站选人，如果车站A，车站B都选了人甲，甲不可能同时从两个车站下车，显然是错误的。这里面一个人不能同时从多个车站下车，是不可重复的元素，看做“客”，一个车站可以同时下多个人，是可以重复的，看做“店”，然后让客选店。3.5名学生争夺三项比赛冠军，获得冠军的可能情况种树是？答案：人选奖项，可能大家都选同一种，但是一共有三种，显然错误。这里同一个奖项不能同时颁给所有的参赛学生，是不可重复的元素，看做“客”，但是如果一个学生比较全能他可以一个人获得多个奖项，是可重复元素，看做“店”。4.8封信放入3个邮箱中，有多少不同结果？答案：信选邮箱，每个新可以有3种选择。如果让邮箱选信，邮箱A,B,C有可能都选了第一封信，显然一封信不能同时投递到多个邮箱中去，那么信就是不可重复元素，看做“客”，一个邮箱可以同时接纳多封信，是可重复元素，看做“店”