排列组合中的定序问题指的是从n个不同元素中选取r个元素并按照一定的顺序排列的方案数。例如,从1,2,3中选取2个元素并排列的方案数为6,分别是12,21,23,32,31,13。
排列组合定序问题的除法原理,也称为“分步乘法原理”,是指将一个问题分成几个子问题,然后将子问题的解乘起来获得原问题的解。对于定序问题,除法原理可以简单地理解为:
设有n个不同元素,要从中选取r个元素进行排列,根据乘法原理,第一个位置可以从n个元素中任选一个,第二个位置可以从剩下的n-1个元素中任选一个,以此类推,最后一个位置可以从剩下的n-r+1个元素中任选一个。根据乘法原理,这r个位置可以有n(n-1)(n-2)...(n-r+1)种不同的排列方式。
但是,这里的排列方式是带有顺序的,而实际上我们只是要从n个不同元素中选取r个元素,不考虑它们的排列方式。因此,要消除这些不必要的排列,需要将上述结果除以r!,即r的阶乘。因为r个元素可以有r!种排列方式,所以每种组合对应r!种排列方式,实际上只有一种组合,所以最终的方案数为:
n(n-1)(n-2)...(n-r+1) / r!
这就是排列组合定序问题的除法原理。
很简单,我们假设这样一道题,1222334可以组成多少个不数字不重复的7位数?答案是七个数7!/2!/3!。7表示7的阶乘,2是除掉的2个3的顺序,3是除掉3个2的顺序。你可以这样理解。我们把这七个数字都看成不同的。
那么1234567毫无疑问能够组成7!个数字不重复的七位数。然后我们假设6和7变成了2。于是这个数变成了1222345。在1234567中,267可以组成3!个不同的组合(267,276,672等等),但是当6和7变成2后,222只能算一种,于是3!要变成1就是除以3!。
同样,把1222345的5变成3,那么本来3和5有2!个组合,现在变成了1种,于是除以2!。所以,出现几个重复的,就是除以重复个数的阶乘。
所谓除法就是分组法。
我们在记数的时候,可以允许重复的记数,得到一个总数N。
把重复的分到一个组当中,一个组中有M的元组,则。总的组的数目就是N/M
例如:组合数就可以这样理解:A(n,m)是全部的排列数,而相同的元素组成的排列是同一组的。此时每组的排列个数就是A(m,m)。
组数C(n,m)=A(n,m)/A(m,m)