排列组合

定义

1.排列组合是组合数学中的基础。排列就是指从给定个数的元素中取出指定个数的元素进行排序；

2.组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序；

3.排列组合的中心问题是研究给定要求的排列和组合可能出现的情况总数；

4.排列组合与古典概率论关系密切;

5.在高中初等数学中，排列组合多是利用列表、枚举等方法解题；

加法原理

1.完成一个工程可以有$n$类办法，$a[i]（1<=i<=n）$代表第i类方法的数目，那么完成这件事共有$S=a[1]+a[2]+……+a[n]$种不同的方法；

乘法原理

1.完成一个工程需要分$n$个步骤，$a[i]（1<=i<=n）$代表第i个步骤的数目，那么完成这件事共有$S=a[1]*a[2]*……*a[n]$种不同的方法；

排列与组合基础

排列数

1.从$n$个不同元素中，任取$m（m<=n，m$与$n$均为自然数，下同）个元素按照一定的顺序排成一列，叫做从$n$个不同元素中取出$m$个元素的一个排列；

2.从$n$个不同元素中取出$m（m<=n）$个元素的所有排列的个数，叫做从$n$个不同元素中取出$m$个元素的排列数；

全排列：

1.$n$个人全部来排队，队长为$n$，第一个位置可以选$n$个，第二位置可以选$n-1$个，以此类推得：

$=n(n-1)(n-1)……3*2*1=n!$；

2.全排列是排列数的一个特殊情况；

组合数

1.从n个不同元素中，任取$m<=n$个元素组成一个集合，叫做从n个不同元素中取出$m$个元素的一个组合；

2.从$n$个不同元素中取出$m<=n$个元素的所有组合的个数，叫做从$n$个不同元素中取出$m$个元素的组合数；

3.组合数也被称为「二项式系数」；

插板法

插板法$（Stars and bars）$是用于求一类给相同元素分组的方案数的一种技巧，也可以用于求一类线性不定方程的解的组数；

正整数和的数目

1.问题一：现有$n$个完全相同的元素，要求将其分为$k$组，保证每组至少有一个元素，一共有多少种分法？

1.考虑拿$k-1$块板子插入到$n$个元素两两形成的$n-1$个空里面；

2.因为元素是完全相同的，所以答案就是：

$$\binom{n-1}{k - 1}$$

3.本质是求$x[1]+x[2]+……x[k]=n$的正整数解的组数；

非负整数和的数目

1.问题二：如果问题变化一下，每组允许为空呢？

1.显然此时没法直接插板了，因为有可能出现很多块板子插到一个空里面的情况，非常不好计算；

2.我们考虑创造条件转化成有限制的问题一，先借$k$个元素过来，在这$n+k$个元素形成的$n+k-1$个空里面插板，答案为：

$$\binom{n + k - 1}{k - 1} = \binom{n + k - 1}{n}$$

3.虽然不是直接求的原问题，但这个式子就是原问题的答案，可以这么理解： 开头我们借来了$k$个元素，用于保证每组至少有一个元素，插完板之后再把这$k$个借来的元素从 组里面拿走。因为元素是相同的，所以转化过的情况和转化前的情况可以一 一对应，答案也就是相等的；

由此可以推导出插板法的公式：

$$\binom{n + k - 1}{n}$$

本质是求$x[1]+x[2]……+x[k]=n$的非负整数解的组数（即要求$x[i]>=0$）；

原文：

# 排列组合
## 定义

1.排列组合是组合数学中的基础。排列就是指从给定个数的元素中取出指定个数的元素进行排序；

2.组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序；

3.排列组合的中心问题是研究给定要求的排列和组合可能出现的情况总数；

4.排列组合与古典概率论关系密切;

5.在高中初等数学中，排列组合多是利用列表、枚举等方法解题；

## 加法原理

1.完成一个工程可以有$n$类办法，$a[i]（1<=i<=n）$代表第i类方法的数目，那么完成这件事共有$S=a[1]+a[2]+……+a[n]$种不同的方法；

## 乘法原理

1.完成一个工程需要分$n$个步骤，$a[i]（1<=i<=n）$代表第i个步骤的数目，那么完成这件事共有$S=a[1]*a[2]*……*a[n]$种不同的方法；

## 排列与组合基础

### 排列数

1.从$n$个不同元素中，任取$m（m<=n，m$与$n$均为自然数，下同）个元素按照一定的顺序排成一列，叫做从$n$个不同元素中取出$m$个元素的一个排列；

2.从$n$个不同元素中取出$m（m<=n）$个元素的所有排列的个数，叫做从$n$个不同元素中取出$m$个元素的排列数；

#### 全排列：

1.$n$个人全部来排队，队长为$n$，第一个位置可以选$n$个，第二位置可以选$n-1$个，以此类推得：

$=n(n-1)(n-1)……3*2*1=n!$；

2.全排列是排列数的一个特殊情况；

### 组合数

1.从n个不同元素中，任取$m<=n$个元素组成一个集合，叫做从n个不同元素中取出$m$个元素的一个组合；

2.从$n$个不同元素中取出$m<=n$个元素的所有组合的个数，叫做从$n$个不同元素中取出$m$个元素的组合数；

3.组合数也被称为「二项式系数」；

## 插板法

插板法$（Stars and bars）$是用于求一类给相同元素分组的方案数的一种技巧，也可以用于求一类线性不定方程的解的组数；

### 正整数和的数目

1.问题一：现有$n$个完全相同的元素，要求将其分为$k$组，保证每组至少有一个元素，一共有多少种分法？

1.考虑拿$k-1$块板子插入到$n$个元素两两形成的$n-1$个空里面；

2.因为元素是完全相同的，所以答案就是：

$$\binom{n-1}{k - 1}$$

3.本质是求$x[1]+x[2]+……x[k]=n$的正整数解的组数；

### 非负整数和的数目

1.问题二：如果问题变化一下，每组允许为空呢？

1.显然此时没法直接插板了，因为有可能出现很多块板子插到一个空里面的情况，非常不好计算；

2.我们考虑创造条件转化成有限制的问题一，先借$k$个元素过来，在这$n+k$个元素形成的$n+k-1$个空里面插板，答案为：

$$
\binom{n + k - 1}{k - 1} = \binom{n + k - 1}{n}
$$

3.虽然不是直接求的原问题，但这个式子就是原问题的答案，可以这么理解：
开头我们借来了$k$个元素，用于保证每组至少有一个元素，插完板之后再把这$k$个借来的元素从  组里面拿走。因为元素是相同的，所以转化过的情况和转化前的情况可以一 一对应，答案也就是相等的；

### 由此可以推导出插板法的公式：

$$
\binom{n + k - 1}{n} 
$$

本质是求$x[1]+x[2]……+x[k]=n$的非负整数解的组数（即要求$x[i]>=0$）；