排列组合公式推导

只有明白公式推导，才能真正明白其中的数理，才会应用自如。

·                                

·                                

（注，公式中的A也用P来表示）

一、n种元素全排列的公式推导的原理：

解：必须分别选定n个（种）元素中的1个、2个、3个、…n个元素定位排列，形成一元、二元、三元……n元组合，以选的组合为作为参照，才能分别逐一确定出一元、二元、三元……n元组合的方法数目。并且，元数组合数集合= n个元素的全排列的序数集合1、2、3、…n——即必须顺次取此数列中的各数为元数（即：元素的数目必须按D=1的公差，从1开始顺次取n个元素的全排列的序数集合。注意：n个元素的序数常是无指定的，解题时自行安排）。确定一元、二元、三元……n元组合方法的数目后，即可用乘法求出总排列数。即：

设：一元、二元、三元……n元组合方法的数目分别为：P1、P2、P3……Pn——即元数集合为此数列中的序数集合（即为D=1的n集合，在计算时均可取实数，所以，不用字母表示）。并设n个元素中，选定作为组合元素之外的元素数目为m——即设：m=n-元数；

（1）一元组合（以首位为例）：即选定n个元素（n1、n2、n3、…n）中的任一个元素轮次排列在选定作为参照的数位上，以确定n个元素轮次排在选定作为参照的数位上的方法共有几种——当以首位为参照时即使n个元素轮次排列在的首位上。

因为n个元素的总数目为n，以首位为例的一元组合即单独使n1、n2、n3、…n轮次排列在首位，即共有n种组合方法——即P1= n；。因为一元组合的元数=1，则m=n-1。

比如：n=5时，共有A、B、E、F、O共5种轮次。

（2）二元组合：即在二元组合的基础上，选定n种元素中的任2个元素排在设定的参照数位 (n数列的首位）上，并确定n数列中前两个数位的元素组合方法的总数。二元组合顺次排列为：n1n2、n1n3、n1n4、…n1n——因为n1作为固定数，所以使n1与其他元素拼成二元组合的方法即必须从n2的序数2开始数到n的序数n——即共有n-1种组合方法——即Pn-1=n-1；并m=n-2。

比如：n=5，并选A排首位时，二元组合方法顺次为：AB、AE、AF、AO共4种——即共有n-1=5-1=4种；并m=n-2=3。

（3）三元组合：即在二元组合的基础上，选定n种元素中的任2个元素排在设定的参照数位 (n数列的首、次两个数位）上，并确定n数列中前三个数位的元素组合方法的总数。即顺次为：n1n2n3、n1n2n4、n1n2n5…n1n2n——因为n1、n2作为固定数，所以使n1、n2与其他元素拼成二元组合的方法即必须从n3的序数3开始数到n的序数n——即共有n-2种组合方法——即P3=n-2；并 m=n-3。

比如：n=5，并选排A首位时，二元组合方法顺次为：ABE、ABF、ABO共3种——即共有n-2=5-2=3种；并m=n-2=3。

以此类推……，则：

n-1元组合：即在n-2元组合的基础上，选定n种元素中的任n-2个元素排在设定的参照数位 (n数列的前n-2个数位）上，并确定n数列中前n-1个数位的元素组合方法的总数。因为n1、n2、n3、…nn-2作为固定数，则n集合中非选定的元素就只剩下最后的nn-1和n两个元素，所以，使n1n2n3…nn-2与其他元素拼成n-2元组合的方法只有两种，即顺次为：n1n2n3…nn-2nn-1、n1n2n3……nn-2n——即从nn-1的序数n-1开始数到n的序数n只有2种组合方法——即Pn-1=n-2。因为n-1元组合的元数=n-1，则m=n-（n-1）=1。

比如：n=5，并选排A首位时，n-1元组合即为选定n-2个元素排在设定的参照数位：n-2=5-2=3——即选定前3个元素A、B、E排在数列的前三位，那么就只剩下F、O这2个元素和两个数位可以自由组合——即只能有2种组合方法，顺次为：ABEF、ABEO——即Pn-1=1；并m=n-（n-1）=1。

n元组合：即在n-1元组合的基础上，选定n种元素中的n-1个元素排在设定的参照数位 (n数列的前n-1个数位）上，并确定n数列中前n个数位的元素组合方法的总数。因为n1、n2、n3、…nn-2 、nn-1都作为固定数，则n集合中非选定的元素就只剩下最后一个元素n，所以，使n1n2n3…nn-2nn-1与其他元素拼成n元组合的方法只有1种——即：n1n2n3…nn-2nn-1nn——即Pn=1；并m=n-n=0。

比如：比如：n=5，并选排A首位时，n元组合即为选定n集合中前面的n-1个元素A、B、E、F排在设定的n-1个参照数位，这就只剩下最后的O元素和1个数位可以自由组合——即只能有1种组合方法：ABEFO。并m=n-n=0。

求总和的方法：因为，以上所求P1、P2、P3、…P3、…Pn-1、 Pn的数值均为方法的数目（即为类数，而并非个数），全排列数的计算1、2、3、……n元组合中的任一组合分别与其他所有组合轮次组合成n个数位的排列总数P(n，n)，即必须使P1×P2×P3×…×P3×…Pn-1×Pn，即：

P(n，n)=P1×P2×P3×…×P3×…Pn-1×Pn

         = n×（n-1）×（n-2）×（n-3）…×2×1

用阶乘表示即为：

P(n，n)= n*（n-1）*（n-2）*（n-3）…*2*1= n！

即：P(n，n)= n！

特别说明：

（1） 用以上方法求n种元素的全排列，在确定n集合（n1、n2、n3、…n）中的1个、2个、3个…n-1个、n个的元素组合一元、二元、三元、n-1元、n元组合方法的数目时，只需要考虑用非选定元素顺次与顺次排列的选定的元素轮次组合出的组合数目即可，而不用再考虑选定元素的逆位排列组合的方法数目——因为再算即为重复。

比如：n=5时：二元组合数目只需要考虑AB、AE、AF、AO这几种情形，而不用再考虑它们逆位排列BA、EA、FA、OA的情形，因为逆位排列的BA、EA、FA、OA的组合方法会顺次出现在由以B、E、F、O为首位的一元、二元、三元、n-1元、n元组合中。

（2）用以上方法求n种元素的全排列，可以不考虑n元组合的方法数。因为，n元组合全选n种元素组合的方法，其实已经包含在一元、二元、三元、n-1元、n元组合中，再算其实是重复计算，所以n元组合的方法数目为Pn=1——任何数与1相乘时其数值均不变——即 n*（n-1）*（n-2）*（n-3）…*2*×1的数值不变。

比如：n=5时：ABEFO、BAEFO、EBAFO、FEBAO、OEBAF……即分别包含于以A、B、E、F、O为首位参照数时的一元、二元、三元、n-1元、n元组合中。