组合公式推导过程

组合公式推导过程

组合公式的推导是由排列公式去掉重复的部分而来的。组合数公式是指从n个不同元素中，任取m（m≤n）个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合；从n个不同元素中取出m（m≤n）个元素的所有组合的个数，叫做n个不同元素中取出m个元素的组合数。用符号c（m,n）表示。
具体推导如下：
1. 排列公式是建立一个模型，从n个不相同元素中取出m个排成一列（有序），第一个位置可以有n个选择，第二个位置可以有n-1个选择（已经有1个放在前一个位置），则同理可知第三个位置可以有n-2个选择。
2. 以此类推，第m个位置可以有n-m+1个选择，则排列数为n(n-1)(n-2)...(n-m+1)，而组合公式对应另一个模型，取出m个成为一组（无序），由于m个元素组成的一组明显可以有m!种不同的排列（全排列），组合的总数就是。
递推公式：c（m,n）=c（m-1,n-1）+c（m,n-1）
推导过程：等式左边表示从n个元素中选取m个元素，而等式右边表示这一个过程的另一种实现方法：任意选择m中的某个备选元素为特殊元素，运作从n中选m个元素可以由此特殊元素的被包含与否分成两类情况，即m个被选择元素包含了特殊元素和m个被选择元素不包含该特殊元素。前者相当于从n-1个元素中选出m-1个元素的组合，即c（m-1,n-1）；后者相当于从m个元素中选出n-1个元素的组合，即c(m,n-1)。2024-07-16