火车票要怎么卖

· · 个人记录

这节课我们来聊聊计数的前半部分。

加法原理与乘法原理

加法原理

如果完成一件事有n类方法，在第1类方法中有m_1种不同的方法，在第2类方法中有m_2，\cdots，在第n类方法中有m_n种不同的方法，那么完成这件事共有N=m_1+m_1+\cdots+m_n种不同的方法。又称分类加法计数原理。

乘法原理

如果完成一件事需要n个步骤，第1步有m_1种方法，第2步有m_2种方法，\cdots，第n步有m_n种不同的方法，那么完成这件事共有N=m_1\cdot m_2\cdots m_n种不同的方法。又称分类乘法计数原理。

排列数与组合数

排列与排列数

一般地，从n个不同元素中取出m(m\leqslant n)个元素，按照一定的次序排成一列，叫做从n个不同元素中取出m个元素的一个排列。从n个不同元素中取出m(m\leqslant n)个元素的所有排列的个数叫做从n个不同元素中取出m个元素的排列数，用符号\text{A}_n^m表示，利用分步乘法计数原理可以得到

\text{A}_n^m=n(n-1)\cdots(n-m+1)=\dfrac{n!}{(n-m)!}

这个公式称为排列数公式。n个不同的元素全部取出的排列叫做n个元素的一个全排列，有A_n^n=n!。

组合与组合数

一般地，从n个不同元素中取出m(m\leqslant n)个元素组成一组，叫做n个不同元素中取出m个元素的一个组合。排列与顺序相关，组合与顺序无关。从n个不同元素中取出m(m\leqslant n)个元素的所有组合的个数叫做从n个不同元素中取出m个元素的组合数，用符号\text{C}_n^m表示，从n个元素中取出m个元素的排列数可以由两个步骤得到：先求从n个不同元素中取出m个元素的组合数\text{C}_n^m，再对这m个元素全排列的排列数\text{A}_m^m，由乘法原理知

\text{A}_n^m=\text{C}_n^m\cdot\text{A}_m^m

从而有组合数公式

\text{C}_n^m=\dfrac{\text{A}_n^m}{\text{A}_m^m}=\dfrac{n!}{(n-m)!m!}

好，今天我们就聊到这里。