排列与组合：先按顺序数，再除掉重复的顺序

排列与组合 · Permutations & combinations

从 n 个里选 k 个，为什么是 n(n−1)…(n−k+1) 再除以 k!？杨辉三角只用加法，为什么得到的是同一批数？

把 k 个位置一个个填满，每一步剩几种选法就乘几：这样数出的是有顺序的排法。每一组不计顺序的组合都被它的 k! 种顺序各数了一次，所以要除掉。杨辉三角走另一条路得到同一个数：最后一个元素要么选进来，要么不选。

n

k

\binom{n}{k} = \dfrac{A_n^k}{k!}

k ≤ n成立：有组合可数

跟着走一遍

1一个位置一个位置地填
从 $5$ 个人里按顺序选 $3$ 个：第一个位置有 $5$ 种选法，第二个剩 $4$ 种，第三个剩 $3$ 种。每种选法都能接在前面任何一种之后，所以相乘： $5\times4\times3=60$ 种有序排法。
2除掉重复的顺序
像 $\{A,B,C\}$ 这样一组，在 $60$ 种排法里出现成 $ABC$ 、 $ACB$ 、 $BAC$ 、 $BCA$ 、 $CAB$ 、 $CBA$ ，它的 $3!=6$ 种顺序各一次。每一组都恰好被数了 $6$ 次，所以组合数是 $60\div6=10$ 。
3杨辉三角用加法
盯住最后一个人。含他的组合还要从其余 $4$ 人里再选 $2$ 个： $\binom42=6$ （蓝）。不含他的组合要从其余 $4$ 人里选满 $3$ 个： $\binom43=4$ （绿）。 $6+4=10$ ，正是高亮的那一格。整个三角形只用这条加法规则搭出来，没有用到乘法。
4选进来 = 剩下来
从 $7$ 人里选 $2$ 个出发，等于选出留下的 $5$ 个： $\binom72=\binom75=21$ 。所以三角形每一行正着读、倒着读都一样。
5边界情况
一个都不选只有一种做法，就是什么都不做，所以 $\binom n0=1$ ， $0!=1$ 。要选的比手上的多，某个位置就没得选：乘积里出现因子 $0$ ，结果是 $0$ 。

1
分步乘法计数原理
如果一件事分几步完成，第一步有 $m_1$ 种做法，而且不管第一步怎么做，第二步都有 $m_2$ 种，那么总共有 $m_1m_2$ 种做法： $m_1$ 种开头每种都分出 $m_2$ 个分支。本章的所有结论都只是认真地用这一条规则。
2
排列：顺序算数
从 $n$ 个不同的元素里取出 $k$ 个填进 $k$ 个位置。第一个位置有 $n$ 种选法，下一个 $n-1$ 种，每次少一种：
$A_n^k=n(n-1)\cdots(n-k+1)=\frac{n!}{(n-k)!}$
$k=n$ 时就是 $n!$ ，把 $n$ 个元素全部排成一列的方法数。
3
组合：把顺序除掉
把有序排法分两步来数：先选出一组，再给这一组排顺序。不管选出的是哪一组，第二步都有 $k!$ 种，所以由乘法原理
$A_n^k=\binom nk\cdot k!\qquad\Longrightarrow\qquad\binom nk=\frac{n(n-1)\cdots(n-k+1)}{k!}$
这也是为什么这个除法总能除尽：它只是把一次乘法还原回去。
4
杨辉三角的加法规则与行和
单独拿出一个元素。每一组 $k$ 个元素要么含它，要么不含它，不会两者都是：
$\binom nk=\binom{n-1}{k-1}+\binom{n-1}{k}$
画板上的三角形只用这条规则和 $\binom00=1$ 搭出来，高亮的格子始终和乘法公式算出的一致。
把一整行加起来，就是 $n$ 个元素所有子集的个数。每个元素选或不选， $n$ 次二选一，所以行和是 $2^n$ 。

Q01

从 $8$ 人中选出一名主席和一名秘书，有多少种选法？

Q02

求 $\binom nk$ 时为什么要除以 $k!$ ？

Q03

$\binom{10}{8}$ 等于多少？

把这个实验做成讲解视频以这个实验为脚本，生成一段可以分享的配音讲解视频。下面的提示词会带到视频生成器里，你可以先改再生成。

VIEW · 显示设置