蒟蒻论排列与组合

转载

我上来一个黑手转载 话说这个人讲故事真的很??

喵

原文链接：LINK

说故事一来是为了更好的理解数学概念，二来是为了形成长期的记忆，以后通过故事来记忆起这个概念。

故事会有点长，但是只用看一次而且无需死记硬背就能长期理解了!

排列组合
先说维基百科和百度百科上查到概念描述，如果看懂了概念性描述就无需继续看故事啦。

排列：是指从给定个数的元素中取出指定个数的元素进行排序。

组合：是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。

区别：被选中元素的顺序是否会影响结果。

1.排列：
In mathematics, permutation is the act of arranging the members of a set into a sequence or order, or, if the set is already ordered,

假设7个程序员中有3个会秃顶，秃顶程度分为，全秃，半秃，微秃。

那么7个程序员里选1个全秃的程序员，为了公平起见，大家都有秃顶的机会，那么就有7种情况；

接下来从剩下6个程序员里选1个半秃的，有6种情况；
继续下去的话就是5选1，则是5种情况；

那么一共有7x6x5情况。

如果我狠心点，希望所有程序员都秃顶，只是秃顶的程度都不一样（三七分的秃，斑点秃······）。那么上面说的7个程序员就有7x6x5x4x3x2x1秃顶情况。

但是我善良！从7个程序员里指定3个程序员必定秃顶，其他4个不会秃，那么怎么才可以拯救这些程序员呢？

对比上面两个公式，可以看出是把4x3x2x1去掉嘛，就有了 (7x6x5x4x3x2x1)/(4x3x2x1)，即
( 7 ! ) / ( 4 ! ) (7!)/(4!)
(7!)/(4!)

以此类推得到以下推论：从n个（程序员）元素里选k个（秃顶）排序，就有P种情况
P = ( n ! ) / ( n ? k ) ! = P ( n , k ) P=(n!)/(n-k)!=P(n,k)
P=(n!)/(n?k)!=P(n,k)

2.组合
In mathematics, a combination is a selection of items from a collection, such that (unlike permutations) the order of selection does not matter.

上述的故事是让程序员们各式各样的秃，但是我觉得太残忍，所以还是希望秃顶的程序员无发可脱，统一的光头吧！

接下来的第二个故事就是7个程序员选定3个是光头！

那么和第一个故事一样是7选1，6选1，5选1吗？不！区别在于选出来的人秃的不统一！

2.1 第一个故事是，当我希望选中的第一个是微秃的，第二个半秃，第三个全秃，那么大家都抢着报名第一个秃，因为害怕被选中全秃和半秃嘛。选择全秃，半秃，未秃的过程是有顺序的。

2.2 第二个故事是，选择让他们都是光头，他们被选择出来后，是没有任何顺序的。反正都秃成光头，别人不在乎第几个被选到了。

故事的变化是，让3个程序员秃顶程度不一样变成让3个程序员都变成光头。

那么第二个故事就可以在第一种故事的基础上，排除3个秃的不一样的程序员，怎么排除呢？之前7个排除4个都是用除法，这里也是。但是这里不是排除4个不秃的！

而是排除3个秃的不一样的人。这里有些人会直接认为只有3个秃顶的人只有3种情况，但是这3个人秃顶情况的也是要继续排列的！所以就会有3x2x1情况，最后结果就是：

( 7 ! ) / ( 4 ! 3 ! ) (7!)/(4!3!)
(7!)/(4!3!)

以此类推得到以下推论：从n个（程序员）元素里选k个（秃顶）,无需排序，就有C种情况
C = ( n ! ) / ( n ? k ) ! k ! = C ( n , k ) C=(n!)/(n-k)!k!=C(n,k)
C=(n!)/(n?k)!k!=C(n,k)

然而我又来了个转载，这是虎哥的，数论基础：喵