满足特定条件的整数数组对(a,b)的数量计算公式推导

大家好，今天我们来拆解这个整数数组对的计数问题：我们需要找出所有长度为 $n$ 的整数数组对 $(a, b)$，满足以下两个核心条件：

• 数组 $a$ 和 $b$ 的所有元素都是 $1$ 到 $m$ 之间的整数；
• 对于任意的 $1 \le i \le j \le n$，都有 $\min(a_i, b_j) = \min(a_j, b_i)$。

结论先行 #

符合条件的数组对总数可以用这个简洁的公式计算：
$$\text{Number of pairs } (a, b) = m^{n-1}$$
其中：

• $n$ 是数组的长度；
• $m$ 是数组元素的取值上限（元素范围是 $1$ 到 $m$）。

推导思路 #

这个公式的核心来自一个关键观察：题目中的 $\min$ 相等条件，其实给数组 $a$ 和 $b$ 的元素施加了一种联动一致性约束，但这种约束并没有过度限制选择空间，反而刚好让我们有 $m^{n-1}$ 种合法组合。

简单来说，我们不需要完全独立地选择每个位置的 $a_k$ 和 $b_k$。当我们固定第一个位置的元素关联属性后，剩下的 $n-1$ 个位置，每个都可以自由选择 $1$ 到 $m$ 之间的一个值来匹配这种属性，所有这样的组合都会自动满足 $\min(a_i, b_j) = \min(a_j, b_i)$ 的要求。

举个小例子验证：当 $n=2$、$m=3$ 时，合法数组对总数是 $3^{2-1}=3$，对应三种符合一致性约束的组合类型，完全符合公式计算结果。

备注：内容来源于stack exchange，提问作者Константин Николаевич Бояр II