映射、子集族与有限集合计数

子集与子集族

若 $|A|=n$，每个元素有“选入或不选入”两种选择，故幂集 $\mathcal P(A)$ 有 $2^n$ 个元素。由若干子集组成的子集族，本身是幂集的一个子集，因此这样的子集族共有 $2^{2^n}$ 个。

例如 $A=\{1,2\}$ 的子集为 $\varnothing,\{1\},\{2\},\{1,2\}$，共4个；子集族有16个，包括空族。$\varnothing$ 与 $\{\varnothing\}$ 不同，后者含一个元素。

所有映射、单射与双射

设 $|A|=m,|B|=n$，且 $m,n\ge1$。每个定义域元素独立选择一个像，所以映射数为 $n^m$。单射要求像互异，若 $m\le n$ 则有 $n!/(n-m)!$ 个；若 $m>n$ 则为零。

双射要求 $m=n$，此时有 $n!$ 个；若元素数不同则不存在。单射只限制不同输入的像，不要求陪域每个元素都被用到；满射则恰好要求全部用到。

满射与容斥

对 $m,n\ge1$，以“某个陪域元素没有被取到”为坏事件，容斥得到满射数

$\binom nj$ 选出禁用的 $j$ 个值，剩余每个输入有 $n-j$ 种像。若 $m<n$，结果为零；这也可直接由每个输入至多覆盖一个值看出。

例如从3元集到2元集共有 $2^3=8$ 个映射，减去两个常映射，得6个满射。

单射、满射的存在条件与分组解释

对非空有限集合 $|A|=m,|B|=n$，前面列出的计数公式还给出以下存在条件：

• 单射存在当且仅当 $m\le n$。必要性来自不同输入必须占用不同输出；充分性是从 $B$ 选出 $m$ 个不同元素依次配给输入。
• 满射存在当且仅当 $m\ge n$。必要性是 $m$ 个输入最多命中 $m$ 个输出；充分性是先指定 $n$ 个不同输入分别命中全部输出，余下输入任意指定。
• 双射存在当且仅当 $m=n$，因为它同时满足上述两个条件。

满射也对应有标号非空分组：每个 $b\in B$ 的原像 $f^{-1}(\{b\})$ 是一个非空组，这些组两两不交且覆盖 $A$。反过来，将每组元素映到组的标号，唯一恢复满射。因此满射的容斥公式同时给出这种分组的数量。

若允许空集，条件需另述：空映射总是单射，仅在陪域也为空时是满射；从非空集到空集不存在映射。这也说明仅凭 $m\ge n$ 不能在 $n=0<m$ 时断言满射存在。

有序集合族的并集条件：按每个元素的归属计数

设 $U$ 为 $n$ 元集，要求 $A_1\cup\cdots\cup A_k=U$，各 $A_i\subseteq U$ 有编号，并暂时允许空集。

对每个 $x\in U$，它属于哪些 $A_i$ 是 $\{1,\ldots,k\}$ 的一个非空子集，共 $2^k-1$ 种选择；不同 $x$ 的归属可独立决定。所以有序集合族的个数为

例如两个集合并成 $U$ 时，每个元素可“仅属第一集”“仅属第二集”“两者都属”，共 $3^n$ 对。若 $|U|=2$，共有 $9$ 对。

这不是“由 $k$ 个非空部分构成的无序覆盖”的计数。如果要求所有 $A_i$ 非空，还要对空部分作容斥：对 $n\ge1$，结果是

若改为两两不交，则每个元素只选一个编号，共 $k^n$；再要求各部分非空，得到 $\sum_{j=0}^k(-1)^j\binom kj(k-j)^n$。无序划分且恰有 $k$ 个非空部分时，才可再除以 $k!$，因为每个划分恰有 $k!$ 种编号方式。

有限集中的对合：固定点与二元组计数

设有限集合 $U$ 上的映射 $T$ 满足 $T(T(x))=x$。则 $T$ 为双射：若 $T(x)=T(y)$，再作用一次得 $x=y$；任意 $y$ 都是 $T(y)$ 的像。

每个元素要么是固定点 $T(x)=x$，要么与 $T(x)\ne x$ 组成一个二元组；这些组两两不交。若有 $f$ 个固定点、$p$ 个二元组，则 $|U|=f+2p$。

要求子集 $A\subseteq U$ 满足 $x\in A\Rightarrow T(x)\in A$，等价于每个组“全选或全不选”，共有 $2^{f+p}$ 种；非空的有 $2^{f+p}-1$ 种。

例如正整数集合要求对每个元素 $a$ 都包含 $2014-a$。正整数条件先迫使 $1\le a\le2013$；变换 $T(a)=2014-a$ 有一个固定点 $1007$ 和 $1006$ 个二元组。因此非空集合有 $2^{1007}-1$ 个。不能只算两两配对而漏掉固定点，也不能不先限制正整数范围。

迭代等于恒等映射：按循环长度计数

设 $k\ge1$ 为整数，有限集合 $A$ 有 $n$ 个元素，且 $f^{\circ k}(x)=x$ 对所有 $x\in A$ 成立。$f$ 的逆为 $f^{\circ(k-1)}$，因此它是一个置换。沿着 $x,f(x),f^{\circ2}(x),\ldots$ 行走，每个元素落在一个循环中；若最短循环长度为 $r$，把 $k$ 除以 $r$，余数必须为零，否则会提前返回。故允许的循环长度恰为 $k$ 的约数。

若 $f^{\circ2}=\operatorname{id}$，只有固定点和二元循环。设有 $j$ 个二元循环，先选出 $2j$ 个元素，再将其配成 $j$ 个无序对，得到

分母 $2^j$ 去掉每对内部交换，$j!$ 去掉各对之间的顺序。$n=6$ 时为 $1+15+45+15=76$。

若 $f^{\circ3}=\operatorname{id}$，只有固定点和三元循环。每三个指定元素有 $(3-1)!=2$ 个有向循环，因此

这里 $3^j$ 去掉每个循环的三种起点写法；反向循环通常不同，不能再除以 $2$。$n=6$ 时为 $1+40+40=81$。

奇偶子集：配对与总容量的区别

设 $S=\{1,\ldots,n\}$，子集的容量是其元素之和，空集容量为零。只要 $n\ge1$，对每个子集翻转元素 $1$ 是否被选，就使容量奇偶互换；此操作两次还原，给出奇子集与偶子集间的双射，所以两者各有 $2^{n-1}$ 个。

数量相等并不自动推出容量总和相等。例如 $n=1$ 时，奇子集总容量为 $1$，偶子集为 $0$。

若 $n\ge3$，对任意固定元素 $j$，在 $S\setminus\{j\}$ 中总能选到一个奇数（$1,3$ 至少留下一个）。在所有包含 $j$ 的子集中翻转这个奇数，将它们按容量奇偶等分，各有 $2^{n-2}$ 个。因此每个 $j$ 对奇子集总容量的贡献为 $j2^{n-2}$，相加得

偶子集总容量同样等于此数。证明包含两个不同配对：第一步统计子集数量；第二步固定一个元素后统计它在两类中的出现次数，不能用第一步代替第二步。

二值向量的距离：翻转不变、奇偶性与平均值

设 $A=(a_1,\ldots,a_n),B=(b_1,\ldots,b_n)$，各分量为 $0$ 或 $1$，定义

结果 $A\oplus B$ 仍是二值向量；符号 $\oplus$ 用来避免与通常向量减法混淆。

同时翻转不改变距离。 对固定 $C$ 的每个坐标：若 $c_i=0$，两个坐标不变；若 $c_i=1$，都变成 $1-a_i,1-b_i$，其差的绝对值仍为 $|a_i-b_i|$。相加得 $d(A\oplus C,B\oplus C)=d(A,B)$。

三个两两距离不可能全奇。 对每个坐标，三个二值数要么全同，给三个距离总和贡献 $0$；要么两同一异，贡献 $2$。所以 $d(A,B)+d(B,C)+d(C,A)$ 为偶数，不可能是三个奇数之和。

平均距离的界。 取 $m\ge2$ 个互异二值向量。第 $i$ 个坐标中有 $t_i$ 个 $1$、$m-t_i$ 个 $0$，这一坐标给无序向量对的总距离贡献 $t_i(m-t_i)\le m^2/4$。因此平均距离

等号要求每一列都恰有 $m/2$ 个 $1$，所以 $m$ 必须为偶数；若 $m$ 为奇数，可把每列的上界改成 $\lfloor m^2/4\rfloor$。这体现“按坐标计数贡献”，无需逐对展开长表达式。

不越界路径与卡特兰数

考虑从 $(0,0)$ 到 $(m,n)$、每步向右或向上一个单位且始终满足 $y\le x$ 的格路，其中整数 $m\ge n\ge0$。无约束路径有 $\binom{m+n}{n}$ 条。

对一条越界路径，找到第一次到达 $y=x+1$ 的位置，将此前的全部步骤左右、上下互换。原来的向上步比向右步多一，交换后终点变为 $(m+1,n-1)$。反向操作是在新路径中第一次达到 $x=y+1$ 时交换前缀。因此这是双射，坏路径有 $\binom{m+n}{n-1}$ 条（$n=0$ 时为零）。合法数为

特别地 $m=n$ 时得到卡特兰数

将右、上步换成左、右括号，就得到 $n$ 对合法括号的数量；$n=3$ 有 $5$ 种。用“第一对左括号的配对位置”分解，则内部与后续分别有 $j$ 对、$n-1-j$ 对，故

这是高中有限计数与映射的拓展，不需要生成函数。