前言

这一期是关于csp S组必考的排列组合。讲述了排列组合的基本概念。 ~~（这东西他们tm是真的难，老CS了）~~

1.排列（Permutation/Arrangement)

定义：从给定的 $n$ 个不同元素中，去出指定个数为 $m$ （ $m \le n$ ）的元素进行排序.

通俗来说就是从 $n$ 个不同的人中，叫那 $m$ 出来排队。

公式：

$ A_n^m = P_n^m = n*(n-1)*(n-2)*...*(n-m+1)=\frac{n!}{(n-m)!} $

别看那么复杂说白了就是从 $n$ 乘到 $(n-m+1)$ 。

例子：

A_5^3=P_5^3=5 * 4 * 3=60

注：$ A_n^m $ 和 $P_n^m$ 是一样的。只是因为排列的英文有两个(Permutation/Arrangement)

📘 例题（排列应用）

题目：

从 7 名不同学生（A、B、C、D、E、F、G）中，选出 4 人排成一列队形（顺序不同算不同队形）。问：共有多少种不同的排队结果？

答案：840

解析：

定义回顾：从给定的 $n$ 个不同元素中，去出指定个数为 $m$ （ $m \le n$ ）的元素进行排序.

题目中： $n$ =7, $m$ =4;

所以 $ A_7^4=7 * 6 * 5 * 4 =42 * 20 =840 $

特殊排列类型

全排列 (Full Permutation)
- 定义：从n个不同元素中取出全部n个元素，按照一定的顺序排成一列，所得到的排列称为全排列，全排列是排列数公式中 $m$ = $n$ 的情况。
- 公式：

A_n^n=P_n^n=n!

可重复排列 (Permutation with Repetition)
- 定义：从 $n$ 个不同元素中，每次允许重复选取元素，取出 $m$ 个元素进行排列。换句话说，就是 $n$ 个元素中的每个元素都可以无限量供应。
- 公式: 由于每次选取都有 $n$ 种选择，且可以重复，根据乘法原理，可重复排列的公式为：

n^m

举例：用0-9这10个数字组成一个4位数的密码，数字可以重复，则共有 $10^4=10000$ 种不同的密码。
有相同元素的排列
- 定义：在 $n$ 个元素中，若有 $k$ 种不同类型的元素，其中第一种类型有 $n_1$ 个相同元素，第二种类型有 $n_2$ 个相同元素，…，第 $k$ 种类型有 $n_k$ 个相同元素，且 $n_1+n_2+\cdots+n_k=n$ 。求这 $n$ 个元素进行全排列的方法数。
- 公式：

\frac{n!}{n_1!n_2!\cdots n_k!}

举例：单词success共有7个字母，其中s有3个，c有2个，u有1个，e有1个。则这些字母可以组成的不同排列数为：

\frac{7!}{3!2!1!1!}=420

圆排列（Circular Permutation）
- 定义：将 $n$ 个不同元素排成一个圆圈，由于旋转后视为同一种排列，因此圆排列的计数方式与直线排列不同。
- 公式：
  1. 从 $n$ 个不同元素中选 $m$ 个进行圆排列：

\frac{A_n^m}{m}=\frac{n!}{m(n-m)!}

2. $n$ 个不同元素进行全圆排列：

(n-1)!

错位排列（Derangement）
- 定义：将 $n$ 个元素进行排列，使得每个元素都不在它原来的位置上，这样的排列称为错位排列。通常用 $D_n$ 表示。
- 递推公式：

D_n=(n-1)(D_{n-1}+D_{n-2})

其中 $D_1=0,\ D_2=1$ 。

通项公式：由递推公式可推导出错位排列的通项公式：

D_n=n!\sum_{i=0}^{n}\frac{(-1)^i}{i!}

2、组合（Combination）

定义

组合的定义为：从给定的 $n$ 个不同元素中，取出指定个数为 $m(m\le n)$ 的元素不进行排序。

公式

从 $n$ 个不同元素中取出 $m$ 个元素的排列数 $A_n^m$ ，可以看作是先从 $n$ 个元素中选出 $m$ 个元素（组合），然后再将这 $m$ 个元素进行全排列。因此，排列数等于组合数乘以 $m$ 个元素的全排列数：

A_n^m=C_n^m\times m!

由此可得组合数公式：

C_n^m=\frac{A_n^m}{m!}=\frac{n!}{m!(n-m)!}

例如：

C_5^3=\frac{5!}{3!2!}=10

组合数的基本性质

互补性质

从 $n$ 个元素中选取 $m$ 个元素组成一个组合，等价于从 $n$ 个元素中选取 $(n-m)$ 个元素舍弃。因此，选取 $m$ 个元素的组合数与选取 $(n-m)$ 个元素的组合数相等。

C_n^m=C_n^{n-m}

例如：从5个数里面选3个数出来组合的方案数，等价于从5个数里面选2个数舍弃的方案数：

C_5^3=C_5^2=10

帕斯卡恒等式（递推）

帕斯卡恒等式揭示了组合数之间的递推关系，是构造杨辉三角（Pascal's Triangle）的基础。

C_n^m=C_{n-1}^{m-1}+C_{n-1}^m

公式推导：即对于第 $m$ 个元素分为选和不选两种情况。

组合数求和

从 $n$ 个元素中选取任意数量的元素（包括不选和全选）的所有组合数之和为：

\sum_{m=0}^{n}C_n^m=C_n^0+C_n^1+\cdots+C_n^n=2^n

公式推导：对于每个元素都有选和不选两种状态。

特殊类型的组合

可重复组合（多重集组合）

定义：从 $n$ 种不同元素中，允许重复选取，取出 $m$ 个元素组成一个组合。

公式（隔板法）：可重复组合数可以通过“隔板法”转化为普通组合问题。将 $m$ 个待选元素看作 $m$ 个“球”，将 $n$ 种不同元素之间的界限看作 $n-1$ 个“隔板”。问题转化为将 $m$ 个球和 $n-1$ 个隔板进行排列，总共有 $m+n-1$ 个位置，从中选择 $m$ 个位置放球（或选择 $n-1$ 个位置放隔板）。

C_{n+m-1}^{m}=C_{n+m-1}^{n-1}

举例：将5个完全相同的苹果分给3个不同的人，每人至少可以分到0个苹果，则共有：

C_{3+5-1}^{5}=C_7^5=21

种分法。

3、排列与组合的辨析

排列与组合的核心区别在于是否考虑元素的顺序：排列强调元素的顺序性，而组合则不考虑元素的顺序。简而言之，当“顺序重要”时，是排列问题；当“顺序不重要”时，是组合问题。二者的区别举例如下：

排列举例：从10名学生中选出1名班长和1名副班长。由于班长和副班长是不同的职务，顺序是重要的，因此是排列问题。
组合举例：从10名学生中选出2名学生组成一个委员会。委员会成员没有职务区别，顺序不重要，因此是组合问题。

排列与组合之间存在密切关系：一个排列可以看作是先进行组合，再进行全排列。即先从 $n$ 个元素中选出 $m$ 个元素（组合），然后将这 $m$ 个元素进行全排列。

习题1

(CSPJ2020) 5个小朋友并排站成一列，其中有两个小朋友是双胞胎，如果要求这两个双胞胎必须相邻，则有（）种不同排列方法？

答案与解析

答案：48

解析：把双胞胎捆绑成一个整体，则相当于 4 个元素全排列： $4!=24$ 。双胞胎内部还可以交换位置： $2!=2$ 。所以总数：

24\times2=48

(CSPJ2020) 10个三好学生名额分配到7个班级，每个班级至少有一个名额，一共有（）种不同的分配方案。

答案与解析

答案：84

解析：名额相同，班级不同，每个班至少 1 个。先给每个班 1 个，剩下 $10-7=3$ 个名额随便分。转化为 3 个球分给 7 个班，允许为 0：

C_{7+3-1}^{3}=C_9^3=84

(CSPJ2020) 有五副不同颜色的手套（共10只手套，每副手套左右手各1只），一次性从中取6只手套，请问恰好能配成两副手套的不同取法有（）种。

答案与解析

答案：120

解析：先选出恰好配成两副手套的 2 副： $C_5^2=10$ 。此时已经取了 4 只。剩下还要取 2 只，且不能再配成完整的一副。剩下 3 副手套中，每副只能取其中 1 只，并且不能取同一副的两只。先从 3 副中选 2 副： $C_3^2=3$ ，每副有左右 2 种选择： $2^2=4$ 。所以：

C_5^2\times C_3^2\times2^2=10\times3\times4=120

(CSPJ2021) 6个人，两个人组一队，总共组成三队，不区分队伍的编号。不同的组队情况有（）种。

答案与解析

答案：15

解析：先分组：

$$\frac{C_6^2C_4^2C_2^2}{3!}=\frac{15\times6\times1}{6}=15$$

(CSPJ2021) 由1,1,2,2,3这五个数字组成不同的三位数有（）种。

答案与解析

答案：18

解析：按三位数中数字组成分类：

三个数字都不同：从 1,2,3 中选 3 个，即 1,2,3，排列数 $3!=6$ 。
有两个 1：选 1,1,2 或 1,1,3。每种排列数 $\frac{3!}{2!}=3$ ，共 $2\times3=6$ 。
有两个 2：选 2,2,1 或 2,2,3。每种排列数 $\frac{3!}{2!}=3$ ，共 $2\times3=6$ 。

总数：

6+6+6=18

(CSPJ2024) 某公司有10名员工，分为3个部门：A部门有4名员工，B部门有3名员工，C部门有3名员工。现需要从这10名员工中选出4名组成一个工作小组，且每个部门至少要有1人。问有多少种选择方式？

答案与解析

答案：120

解析：每个部门至少 1 人，共选 4 人。人数分配只能是：

(2,1,1)

即某个部门出 2 人，另外两个部门各出 1 人。

A 出 2 人，B、C 各出 1 人： $C_4^2C_3^1C_3^1=6\times3\times3=54$
B 出 2 人，A、C 各出 1 人： $C_4^1C_3^2C_3^1=4\times3\times3=36$
C 出 2 人，A、B 各出 1 人： $C_4^1C_3^1C_3^2=4\times3\times3=36$

总数：

54+36+36=126

等等，这里再核对一下：A 出 2 人： $C_4^2=6$ ，B 出 1： $C_3^1=3$ ，C 出 1： $C_3^1=3$ ，得 54。
B 出 2 人： $C_3^2=3$ ，A 出 1： $C_4^1=4$ ，C 出 1： $C_3^1=3$ ，得 36。
C 出 2 人： $C_3^2=3$ ，A 出 1： $C_4^1=4$ ，B 出 1： $C_3^1=3$ ，得 36。
总：

54+36+36=126

所以答案应为 126。

(CSPJ2024) 有55个男生和33个女生站成一排，规定33个女生必须相邻。问有多少种不同的排列方式？

答案与解析

答案： $56!\times33!$

解析：把 33 个女生捆绑成一个整体，则相当于 55 个男生 + 1 个女生整体 = 56 个元素排列：

56!

女生内部还可以排列：

33!

所以总数：

56!\times33!

(CSPJ2025) 从5位男生和4位女生中选出4人组成一个学习小组，要求学习小组中男生和女生都有。有多少种不同的选择方法？

答案与解析

答案：120

解析：总选法：

C_9^4=126

没有男生，即全选女生：

C_4^4=1

没有女生，即全选男生：

C_5^4=5

所以男女生都有的选法：

126-1-5=120

(CSPJ2025) 一个 $8\times8$ 的棋盘，左上角坐标为(1,1)，右下角为(8,8)。一个机器人从(1,1)出发，每次只能向右或向下走一格。要到达(4,5)，有多少种不同的路径？

答案与解析

答案：56

解析：从 (1,1) 到 (4,5)，需要向下走 $4-1=3$ 步，向右走 $5-1=4$ 步，总共 7 步。选择其中 3 步向下：

C_7^3=35

等一下，重新算：总步数 $3+4=7$ ，选 3 步向下：

C_7^3=35

所以答案是 35。

(CSPS2019) 由数字1,1,2,4,8,8所组成的不同的4位数的个数是（）

答案与解析

答案：102

解析：按重复数字分类：

四个数字都不同：从 1,2,4,8 中选 4 个，只有一种组合，排列 $4!=24$ 。
有两个 1：选 1,1,2,4 或 1,1,2,8 或 1,1,4,8。每种排列 $\frac{4!}{2!}=12$ ，共 $3\times12=36$ 。
有两个 8：选 8,8,1,2 或 8,8,1,4 或 8,8,2,4。每种排列 $\frac{4!}{2!}=12$ ，共 $3\times12=36$ 。
两个 1 和两个 8：选 1,1,8,8，排列 $\frac{4!}{2!2!}=6$ 。

总数：

24+36+36+6=102

(CSPS2020) 从一个 $4\times4$ 的棋盘中选取不在同一行也不在同一列上的两个方格，共有（）种方法。

答案与解析

答案：72

解析：先选第一个方格：16 种。
第二个方格不能与第一个同行同列，剩下可选：

16-4-4+1=9

但两个方格无顺序，所以：

\frac{16\times9}{2}=72

(CSPS2021) 有8个苹果从左到右排成一排，你要从中挑选至少一个苹果，并且不能同时挑选相邻的两个苹果，一共有（）种方案。

答案与解析

答案：54

解析：设选 $k$ 个苹果。8 个苹果中选 $k$ 个且不相邻，相当于在剩下的 $8-k$ 个苹果形成的 $8-k+1$ 个空位中选 $k$ 个：

C_{8-k+1}^{k}

枚举 $k=1$ 到 $4$ ：

$k=1$ ： $C_8^1=8$
$k=2$ ： $C_7^2=21$
$k=3$ ： $C_6^3=20$
$k=4$ ： $C_5^4=5$

总数：

8+21+20+5=54

(CSPS2022) 小明希望选到形如"省A·LLDDD"的车牌号。车牌号在"之前的内容固定的5位号码中，前2位必须是大写英文字母，后3位必须是阿拉伯数字（L代表A至Z，D表示0至9，两个L和三个D之间可能相同也可能不同）。请问总共有多少个可供选择的车牌号。

答案与解析

答案： $26^2\times10^3=676000$

解析：前 2 位字母，每位 26 种：

26^2=676

后 3 位数字，每位 10 种：

10^3=1000

总数：

676\times1000=676000

(CSPS2023) 0,1,2,3,4中选取4个数字，能组成（）个不同四位数（注：最小的四位数是1000最大的四位数是9999）。

答案与解析

答案：96

解析：先不考虑 0 在千位的情况，从 5 个数字中选 4 个排列：

A_5^4=120

再减去 0 在千位的情况：千位固定为 0，剩下从 1,2,3,4 中选 3 个排列：

A_4^3=24

所以合法四位数：

120-24=96

(CSPS2024) 在一场比赛，有1010名选手参加，前三名将获得金、银、铜牌。若不允许并列，且每名选手只能获得一枚奖牌，则不同的颁奖方式共有多少种？

答案与解析

答案： $1010\times1009\times1008$

解析：金牌有 1010 种，银牌有 1009 种，铜牌有 1008 种：

1010\times1009\times1008

(CSPS2025) 有5个红色球和5个蓝色球，它们除了颜色之外完全相同。将这10个球拍成一排，要求任意两个蓝色球都不能相邻，有多少种不同的排列方法？

答案与解析

答案：6

解析：先排 5 个红球，形成 6 个空位：

\_ R \_ R \_ R \_ R \_ R \_

5 个蓝球必须放入这 6 个空位中，且每个空位最多放 1 个，否则蓝球相邻。所以从 6 个空位中选 5 个放蓝球：

C_6^5=6

红球和蓝球都完全相同，所以不需要再乘内部排列。答案 6。

习题2

[NOIP2016] 有7个一模一样的苹果，放到3个一样的盘子中，一共有（）种放法。

答案与解析

答案：8

解析：苹果相同，盘子相同，属于整数分拆。把 7 拆成不超过 3 个部分：

7=7=6+1=5+2=5+1+1=4+3=4+2+1=3+3+1=3+2+2

共 8 种。

[NOIP2017] 甲、乙、丙三位同学选修课程，从4门课程中，甲选修2门，乙、丙各选修3门，则不同的选修方案共有（）种。

答案与解析

答案：48

解析：

C_4^2\times C_4^3\times C_4^3=6\times4\times4=96

等等，再核对：甲选 2 门： $C_4^2=6$ ；乙选 3 门： $C_4^3=4$ ；丙选 3 门： $C_4^3=4$ 。总：

6\times4\times4=96

所以答案 96。

[NOIP2018] 设含有10个元素的集合的全部子集数为S，其中由7个元素组成的子集数为T，则T/S的值为（）。

答案与解析

答案： $\frac{15}{128}$

解析：

S=2^{10}=1024

T=C_{10}^7=C_{10}^3=120

所以：

\frac{T}{S}=\frac{120}{1024}=\frac{15}{128}

[NOIP2008] 书架上有4本不同的书A、B、C、D，其中A和B是红皮的，C和D是黑皮的。把这4本书摆在书架上，满足所有黑皮的书都排在一起的摆法有（）种。满足A必须比C靠左，所有红皮的书要摆放在一起，所有黑皮的书要摆放在一起，共有（）种摆法。

答案与解析

第一问答案：12

解析：黑皮书 C、D 捆绑成一个整体，与 A、B 共 3 个元素排列：

3!=6

黑皮内部 C、D 排列：

2!=2

所以：

6\times2=12

第二问答案：4

解析：红皮 A、B 捆绑，黑皮 C、D 捆绑，两个整体排列：

2!=2

红皮内部 A、B 排列，但要求 A 在 C 左边。先看两个整体：红皮整体和黑皮整体。
红皮整体在左时，A、B 内部有 2 种；黑皮整体在右时，C、D 内部有 2 种。但要求 A 比 C 靠左。
枚举：

红整体在左：A、B 可以是 AB 或 BA；黑整体在右：C、D 可以是 CD 或 DC。
A 比 C 靠左恒成立，因为红整体在左。共 $2\times2=4$ 种。
黑整体在左：C、D 在前，A、B 在后，A 不可能比 C 靠左。0 种。

所以共 4 种。

[NOIP2008] 书架上有21本书，编号从1到21，从其中选4本，其中每两本的编号都不相邻的选法一共有（）种。

答案与解析

答案： $C_{18}^4=3060$

解析：从 21 本书中选 4 本且不相邻，等价于在剩下的 17 本书形成的 18 个空位中选 4 个：

C_{18}^4=3060

[NOIP2017] 将7个名额分给4个不同的班级，允许有的班级没有名额，有（）种不同的分配方案。

答案与解析

答案： $C_{10}^3=120$

解析：7 个名额相同，4 个班级不同，允许为 0。隔板法：

C_{7+4-1}^{4-1}=C_{10}^3=120

[NOIP2011] 每份考卷都有一个8位二进制序列号。当且仅当一个序列号含有偶数个1时，它才是有效的。例如，00000000、01010011都是有效的序列号，而11111110不是。那么，有效的序列号共有（）个。

答案与解析

答案：128

解析：8 位二进制序列号共有 $2^8=256$ 个。含有偶数个 1 和含有奇数个 1 的序列号各占一半：

\frac{2^8}{2}=128

[NOIP2012] 在全国赛期间，主办单位为了欢迎来自全国各地的选手，举行了盛大的晚宴。在第十八桌，有5名大陆选手和5名港澳选手共同进膳。为了增进交流，他们决定相隔就坐，即每个大陆选手左右相邻的都是港澳选手、每个港澳选手左右相邻的都是港澳选手。那么，这一桌共有（）种不同的就坐方案。注意：如果在两个方案中，每个选手左边相邻的选手均相同，则视为同一个方案。

答案与解析

答案： $2\times(5!)^2=28800$

解析：圆桌交替坐。先排 5 名大陆选手围成一圈：

(5-1)!=4!

再在 5 个空位中排 5 名港澳选手：

5!

但港澳选手可以整体顺时针或逆时针插入，相当于两种交替方式。注意题目说“每个选手左边相邻的选手均相同则视为同一个方案”，这其实已经固定了方向。
标准圆桌交替排列数为：

2\times(5!)^2

计算：

2\times120\times120=28800

【NOIP2013】7个同学围坐一圈，要选2个不相邻的作为代表，有（）种不同的选法。

答案与解析

答案：14

解析：7 个同学围成一圈，选 2 个不相邻。总选法：

C_7^2=21

相邻的选法有 7 种（每对相邻）。所以不相邻：

21-7=14

【NOIP2014】由数字1,1,2,4,8,8所组成的不同的四位数的个数是（）

答案与解析

答案：102

解析：同习题1第10题。

【NOIP2016】从一个4x4的棋盘(不可旋转)中选取不在同一行也不在同一列上的两个方格，共有（）种方法。

答案与解析

答案：72

解析：同习题1第11题。

【NOIP2018】方程ab=(a or b)(a and b)，在a,b都取[0,31]中的整数时，共有（）组解。（*表示乘法；or表示按位或运算；and表示按位与运算）

答案与解析

答案：1024

解析：利用恒等式：

a+b=(a\text{ or }b)+(a\text{ and }b)

以及：

ab=(a\text{ or }b)(a\text{ and }b)

可以推出：

(a\text{ or }b)=(a\text{ and }b)

即：

a=b

因为如果两个数的按位或等于按位与，那么每一位都相同，所以 $a=b$ 。
$a,b\in[0,31]$ ，共有 32 种取值，所以解为：

32

等等，这里需要再仔细验证。实际上，对于每一位：

若 $a_i=b_i=0$ ，则 or=0，and=0；
若 $a_i=b_i=1$ ，则 or=1，and=1；
若 $a_i\ne b_i$ ，则 or=1，and=0。

原方程 $ab=(a\text{ or }b)(a\text{ and }b)$ 。
令 $x=a\text{ or }b$ ， $y=a\text{ and }b$ 。有 $x+y=a+b$ ，且 $x\ge y$ 。
原方程： $ab=xy$ 。

又 $a+b=x+y$ ，所以 $a,b$ 是方程：

t^2-(x+y)t+xy=0

的两个根。判别式：

\Delta=(x+y)^2-4xy=(x-y)^2

所以 $a,b$ 必为 $x,y$ 的某种排列。
而 $x=a\text{ or }b$ ， $y=a\text{ and }b$ ，这意味着 $a,b$ 必须满足：一个是 $x$ ，一个是 $y$ 。
但 $x$ 和 $y$ 的二进制关系： $y$ 的每一位是 $x$ 的子集。
这等价于 $a,b$ 中，每一位不能出现一个 1 一个 0 的情况吗？
实际上， $x=a\text{ or }b$ ， $y=a\text{ and }b$ ，那么 $x-y$ 的二进制中，1 的位置正是 $a,b$ 不同的位。

若 $a,b$ 是 $x,y$ 的排列，则 $a=x,b=y$ 或 $a=y,b=x$ 。
但 $y=a\text{ and }b$ 必须同时满足。
若 $a=x,b=y$ ，则 $a\text{ and }b=x\text{ and }y=y$ ，成立； $a\text{ or }b=x\text{ or }y=x$ ，成立。
若 $a=y,b=x$ ，同理成立。

所以任意 $x,y$ 满足 $y$ 是 $x$ 的子集即可。
$[0,31]$ 是 5 位二进制。每一位有三种状态：

$x_i=0,y_i=0$ ：对应 $a_i=b_i=0$ ；
$x_i=1,y_i=1$ ：对应 $a_i=b_i=1$ ；
$x_i=1,y_i=0$ ：对应 $a_i\ne b_i$ ，有两种分配。

所以对于每一位，若 $x_i=0$ ，则 $y_i=0$ ，只有 1 种；若 $x_i=1$ ，则 $y_i$ 可以是 0 或 1，对应 2 种或 1 种？
更直接：每一位上， $a_i,b_i$ 的组合有 4 种：

(0,0)：or=0,and=0，乘积 0；
(0,1)：or=1,and=0，乘积 0；
(1,0)：or=1,and=0，乘积 0；
(1,1)：or=1,and=1，乘积 1。

原方程左边 $ab$ 在这一位上的贡献？乘法不是按位独立的，所以不能逐位直接乘。
正确做法：枚举所有 $a,b\in[0,31]$ ，共有 $32\times32=1024$ 对。
满足 $ab=(a|b)(a\&b)$ 的解有多少？

我们可以用程序验证，但手算：
令 $a=b$ 时，左边 $a^2$ ，右边 $(a|a)(a\&a)=a\cdot a=a^2$ ，成立。
所以 $a=b$ 的 32 对都是解。

还有没有其他解？
设 $a\ne b$ 。令 $x=a|b$ ， $y=a\&b$ 。则 $x>y$ 。
原方程 $ab=xy$ 。又 $a+b=x+y$ 。
所以 $a,b$ 是方程 $t^2-(x+y)t+xy=0$ 的根，即 $t^2-(a+b)t+ab=0$ ，根为 $a,b$ 。
而 $x,y$ 也是根，所以 $\{a,b\}=\{x,y\}$ 。
但 $x=a|b$ ， $y=a\&b$ ，且 $x\ne y$ 。
若 $a=x,b=y$ ，则 $a|b=x|y=x$ ， $a\&b=x\&y=y$ ，成立。
若 $a=y,b=x$ ，同理成立。
所以只要 $a,b$ 满足：一个是另一个的按位超集，并且 $a|b=a$ ， $a\&b=b$ （或反过来）。
即 $b$ 的每一位都是 $a$ 的子集（ $b\&a=b$ ），且 $a\ne b$ 。
这样的 $(a,b)$ 有序对有多少？
对于每一位， $a_i,b_i$ 可取：

(0,0)
(1,0)
(1,1)

不能取 (0,1)，因为 $b$ 必须是 $a$ 的子集。
每一位 3 种，5 位共 $3^5=243$ 种。
其中包括 $a=b$ 的情况，即每一位 (0,0) 或 (1,1)，共 $2^5=32$ 种。
所以 $a\ne b$ 的有序对为 $243-32=211$ 种。

但注意，我们要求的是 $\{a,b\}=\{x,y\}$ ，有序对 $(a,b)$ 中， $a$ 是超集， $b$ 是子集。
满足这个的有序对数量是 $3^5=243$ 。
但原方程对 $a,b$ 是对称的，所以无序对是 $243$ 种？
实际上， $(a,b)$ 有序对中，满足 $b$ 是 $a$ 的子集的有 $

s's's's

前言

1.排列（Permutation/Arrangement)

定义：从给定的 $n$ 个不同元素中，去出指定个数为 $m$ （ $m \le n$ ）的元素进行排序.

通俗来说就是从 $n$ 个不同的人中，叫那 $m$ 出来排队。

公式：

例子：

题目：

答案：840

解析：

特殊排列类型

2、组合（Combination）

定义

公式

组合数的基本性质

互补性质

帕斯卡恒等式（递推）

组合数求和

特殊类型的组合

可重复组合（多重集组合）

3、排列与组合的辨析

习题1

习题2

状态

开发

支持

关于

s's's's

前言

1.排列（Permutation/Arrangement)

定义：从给定的nnn个不同元素中，去出指定个数为 mmm（ m≤nm \le nm≤n ）的元素进行排序.

通俗来说就是从nnn个不同的人中，叫那mmm出来排队。

公式：

例子：

题目：

答案：840

解析：

特殊排列类型

2、组合（Combination）

定义

公式

组合数的基本性质

互补性质

帕斯卡恒等式（递推）

组合数求和

特殊类型的组合

可重复组合（多重集组合）

3、排列与组合的辨析

习题1

习题2

状态

开发

支持

关于

登录

定义：从给定的 $n$ 个不同元素中，去出指定个数为 $m$ （ $m \le n$ ）的元素进行排序.

通俗来说就是从 $n$ 个不同的人中，叫那 $m$ 出来排队。