排列组合

排列(n>=r)

对有n个元素的集合S中的其中r个元素进行排列(n >= r)可以用如下几种方法来理解:

排列描述1

每次从n个元素中取r个元素出来,那么一共有C(n,r)种取法。每种取法中的r个元素按顺序依次排列在r个位置上,这样第一个位置一共有r种方法,而第二个位置有r-1个方法,第r个位置则只有1种方法了,因此一共有 r * (r-1) * (r-2) * ... * 2 * 1种方法,也就是有r!种方法。每种取法有r!种放置的方法,那么总共就有 C(n,r) * r!种排列方法,因此:

A(n,r) = C(n,r) * r!

排列描述2

把n个元素放入到r个位置里面,且每个位置只能放置1个。那么第一个位置一共有n种放法,第二个位置一共有n-1种放法,因此第r个位置一共有n-r+1种放法,这样总共就有:n * (n-1) * (n-2) * ... * (n-r+1)种放法(或者说第一个位置一共可以放n个元素中的任意一个,第二个位置则可以放入n-1个元素中的任意一个,依次类推第r个位置就可以放入n-r+1个元素中的任意一个,这样排列完毕同时也只取了其中的r个元素)因此:

A(n,r) = n * (n-1)*(n-2) *...* (n-r+1)

排列描述3

如果对n个元素都进行排列那么一共有n!种排列的方法。那么当取r个元素进行排列时,可以反过来假设将r个元素放入到n个位置中去,这时候必定有n-r个位置是空的,也就是n-r个位置只有1种取值。而在n!种排列中(n-r)个位置一共有(n-r)!种排列,因此去除这(n-r)!种重复的排列,只保留一种那就得到了n个元素的r排列的公式:

A(n,r) = n! / (n-r)!

这种描述还可以将n!的计算描述为先从n个元素里面取r个进行排列,再将(n-r)进行排列,一共有(n-r)!种方法,这样二者相乘得到n!, 因此 A(n,r) * (n-r)! = n!

在实践中排列的另外一个表述就是把n个元素放入r个位置(n >=r), 并且要求每个位置至只放一个元素的方法数量。同样可以表述为将r个元素放入n个位置(n >= r),并且每个位置至多只放一个元素的方法数量。

排列(n<r)

前面考察的是将n个元素放入r的位置(n >=r)的情况,再来详细的考察n<r的情况。因为这种放置会产生空的位置,因此不能用A(n,r)来计算(第一个位置有n+1种方法,这其中包括不放。而第二个位置的方法则要根据第一个位置的放入情况,假如第一个位置没有放入,那么第二个位置就有n+1种放法;而假如第一个位置有放入则第二个位置有n种方法,因此这里不符合乘法规则)。这种情况下可以考虑增加(r-n)个相同的元素来填满r个位置中,这样就一共有r!种排列的方法了。又因为(r-n)个元素都是相同的元素,我们要去除重复的排列,一共有(r-n)!种。这样我们就得出排列公式:

A(n,r) = r! / (r-n)! (r > n)

而当r <= n 时则有:

A(n,r) = n!/(n-r)! (r<= n)

因此我们可以得出更加通用的排列公式:

A(n,r) = max(n,r)! / |n-r|!

上面可以看出当r > n时 我们计算A(n,r)的排列,其实就是A(r,n)的排列计算公式。

重复排列

n个元素的r重复排列(n >=r),也就是n个元素里面取r个元素,放置在r个位置上,每个位置至少放入一个,每个位置都可以重复放入相同的元素。这样第一个位置就可以放入n个元素中的任意一个元素,因此一共有n种放法,而第二个位置也同样可以放入n个元素中的任意一个元素,这样第r个位置也可以放入n个元素中的任意一个元素。经过r次放置后这n个元素里面最少是取了1个元素,而最多则是取了r个不同的元素。因此n的r重复排列的公式:

A(n,r) = n^r

在实践中的重复排列,我们一般把位置作为指数,而把元素个数作为底数。

那n个元素的r位置重复排列在n<r时又是如何计算呢?如果每个位置至少放入1个元素的话那么,每个位置都有n种方法,因此重复排列的公式也是一样的为: n^r。

对于重复排列来说,当考虑某个位置可以为空的情况时,那么就可以理解为我们多增加了一个元素,因此当位置可以放置为空时的排列公式为 :

A(n,r ) = (n+1)^r

这里依然可以用乘法公式的原因是每个位置的可放置的元素个数不依赖于前面的放置结果,每个位置都可以放置n+1种。因此对于重复排列来说元素的个数和位置的数量无论哪个大结果的公式都是一样的,都是 元素个数^位置个数

对于重复排列来说这种指数关系,也可以表示为可以放回排列,比如n个元素,放入r个位置。一个位置可以放n个中的任意一个,一共有n种。而第二个位置则一样可以放入n个中的任意一个一共也有n种。因此一共有 n ^ r 种。

举例来说把3个球放入4个位置,一共有多少种方法? 这里面表面上看元素是3位置是4,但是因为球不可重复因此不能用 3^4来描述。而且也不能用乘法因此第二个位置的放法要依赖于第一个位置,这里只能用不可重复的排列公式来进行计算。

组合

组合其实就是从n个元素里面取出r个元素(n >=r)的方法数。

组合描述1

因为只需要取出r个元素,因此不涉及到对r个元素进行排列的情况。同样组合可以看成是从一个有n个元素的集合S中取出含有r个元素的子集A的数量。我们知道从n个元素里面取r个元素进行排列的方法一共有A(n,r)种排列,假设我们取到了一个具有r个元素的集合A,那么在A中则一共有r!种排列方法,既然一个r元素的子集A的排列数量是r!, 而总的r个元素的排列数量是A(n,r). 那么也就是说有A(n,r)/r!个子集,因此组合的公式:

C(n,r) = A(n,r) / r!

组合描述2

组合还可以从另外一个维度考察,就是假设有n个位置,我们要取出r个位置的取法,因为每个位置可以是n中的任意一个位置,但总共只有r个位置。你可以把总位置当做元素的总数,r个位置则当做r个不同的元素,因此组合还可以用在位置。也就是说如果把r个相同的元素放入到n个位置里面的方法就是C(n,r)组合。而把r个不同元素放入到n个位置里面的方法就是P(n,r)排列。

这里再引申出重复排列的计算方法,假设有k种元素,每种元素的数量为ni (1 < i < k), 且 n1 + n2 + .. nk = n。 那么他的排列方式一共有几种? 我们知道一共有n个位置。要放置这k种元素。那么第一种元素a1 有n1个, 因为a1的每个元素都相同因此不考虑顺序问题,这就和上面的组合的另外一个维度的考察是一样的,因此一共有 C(n, n1)种方法。那么第二种类型a2则一共有n2个就有C(n-n1, n2)种方法,这里每一步骤都是独立的因此可以用乘法最后的结果是:

C(n,n1) * C(n-n1, n2) * C(n-n1-...nk-1, nk) = n! / (n1! * n2! * ...nk!)

而当只有2种元素a,b时那么就是 : C(n,n1) * (n-n1, n2) = (C,n1) = C(n,n2)*C(n-n2, n1) = C(n,n2) 。这个好理解就是假设只有2种元素时则每当a类型的位置确定后, b类型就只有1种方法了。因此只要确定a的就OK了。

排列和组合的区别

当把r个相同的元素放入到n个位置,每个位置至多只有一个的方法就是组合C(n,r); 而把r个不同的元素放入到n个位置,每个位置至多只有一个时的方法则是排列A(n,r)

而当把n个不相同的元素放入r个位置, 每个位置只放置1个的方法就是A(n,r); 而把n个相同的元素放入r个位置,每个位置只放入1个的方法就是1了。 这里的原因是组合时因为都是相同的而元素个数小于位置时因为有空位所有方法有多种,而元素个数大于位置时因为没有空位了所以只有一种。从而可以引申出的一个概念就是组合里面的放置方法其实就是空位数量的放置方法,因此有: C(n,r) = C(n, n-r)成立。

排列组合在实践中的区别是,排列是把x个元素放入y个位置的计数,而组合则是x个元素中取任意y个元素的计数,因为位置是有顺序的,而取出的数量则不需要考虑顺序的情况。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏武培轩的专栏

剑指Offer-数组中重复的数字

package Array; /** * 数组中重复的数字 *在一个长度为n的数组里的所有数字都在0到n-1的范围内。 * 数组中某些数字是重复的,但不...

32640
来自专栏ShaoYL

【C语言】指针

60260
来自专栏机器学习算法与Python学习

Python: 对迭代器的小结

迭代器 迭代器是在python2.2中被加入的,它为类序列对象提供了一个类序列的接口。有了迭代器可以迭代一个不是序列的对象,因为他表现出了序列的行为。当在pyt...

34360
来自专栏菩提树下的杨过

ruby学习笔记(2)--类的基本使用

ruby语言跟c#的一些重要差别在于: 1.ruby是动态语言,c#是静态语言--即对象在new出来以后,ruby还可以动态给对象实例添加一些属性或方法(jav...

19160
来自专栏闵开慧

java归并排序(最精简代码)

public class MergeSortTest { public void sort(int[] array, int left, int right)...

40750
来自专栏杂七杂八

简单的正则表达式

特殊字符 ^ $ * ? + {2} {2,} {2,5} | [] [^] [a-z] . \s \S \w \W [\u4E00-\u9FA5] ...

28960
来自专栏微信公众号:Java团长

Java:类与继承

  对于面向对象的程序设计语言来说,类毫无疑问是其最重要的基础。抽象、封装、继承、多态这四大特性都离不开类,只有存在类,才能体现面向对象编程的特点,今天我们就来...

10010
来自专栏python3

python 迭代器

一类是generator,包括生成器和带yield的generator function。

9710
来自专栏北京马哥教育

一文读懂Python可迭代对象、迭代器和生成器

14960
来自专栏ccylovehs

JavaScript 深入之从原型到原型链

在这个例子中, Person 就是一个构造函数,我们使用 new 创建了一个实例对象 person 。 很简单吧,接下来进入正题:

44340

扫码关注云+社区

领取腾讯云代金券