m×m随机整数矩阵中从中心出发特定序列的出现概率求解

首先，我们先明确几个这类问题的常规前提（如果你的设定不同，可以随时调整）：

• 矩阵中每个元素是独立随机选取的，1到c中每个整数被选中的概率都是1/c。
• 路径采用四连通移动规则：只能向上下左右四个相邻格子移动，且路径中不能重复访问同一个格子（符合题目“不可重复使用同一矩阵元素”的要求）。
• 长度为k的序列指的是包含k个元素的有序序列，对应从中心出发的一条包含k个不同格子的路径（中心是序列的第一个元素，之后每一步移动到相邻未访问格子，直到凑够k个元素）。

接下来分两种常见的问题理解场景来计算概率：

场景1：随机选择一条符合条件的路径，其序列等于目标特定序列的概率 #

这种场景下，我们只需要考虑单条路径匹配目标序列的概率：
因为矩阵中每个元素的取值独立，路径上每个位置的元素恰好等于目标序列对应位置的概率是1/c，所以长度为k的路径完全匹配目标序列的概率是：

(1/c)^k

这个结果和路径总数无关——不管有多少条可选路径，随机选一条的话，它匹配目标序列的概率只取决于每个元素的独立随机性。

场景2：随机生成的矩阵中，存在至少一条符合条件的路径匹配目标序列的概率 #

这个场景更贴近“找到一条”的字面意思，计算起来会复杂一些，因为不同路径之间可能共享格子，它们的匹配事件不是互斥的，我们可以分两种情况讨论：

情况A：目标序列所有元素互不相同 #

如果目标序列S中的每个元素都不一样，那么两条不同的路径不可能同时匹配S（因为它们的路径格子序列不同，必然有某个位置的格子不同，而该格子需要同时等于S中两个不同的元素，概率为0）。

此时，所有路径的匹配事件是互斥的，总概率直接等于路径总数乘以单条路径的匹配概率：

• 路径总数：从中心出发，第1步只有1种选择（中心），第2步有4个方向可选，第3到第k步每一步都有3个新方向可选（因为不能走回上一步的格子，且题目规定m/2 > k，不会碰到矩阵边界），所以总路径数是4 × 3^(k-2)（当k≥2时；k=1时路径数为1）。
• 单条路径匹配概率：(1/c)^k

因此总概率为：

• 当k=1时：1 × (1/c) = 1/c
• 当k≥2时：4 × 3^(k-2) × (1/c)^k

情况B：目标序列存在重复元素 #

如果目标序列中有重复元素，不同路径可能同时匹配S（比如两条路径共享某些格子，且这些格子对应的序列位置值相同），这时候需要用容斥原理来精确计算：

P(存在匹配路径) = ΣP(A_i) - ΣP(A_i∩A_j) + ΣP(A_i∩A_j∩A_k) - ... + (-1)^(n+1)P(A_1∩...∩A_n)

其中：

• A_i表示第i条路径匹配目标序列的事件
• n是总路径数（即4 × 3^(k-2)，k≥2）
• ΣP(A_i)是所有单条路径匹配概率的和，即n × (1/c)^k
• ΣP(A_i∩A_j)是所有两两路径同时匹配的概率和：只有当两条路径的共享格子对应的序列位置值相等时，这个概率才不为0，否则为0。比如两条路径在某个格子上分别对应序列的第t和第s位，只有当S[t] = S[s]时，这个格子的取值才能同时满足两个路径的要求，否则交集概率为0。

当c很大时，不同路径同时匹配的概率会非常小，这时候可以用近似值忽略高阶项，直接用n × (1/c)^k来估算总概率，误差可以忽略不计。

内容的提问来源于stack exchange，提问作者sciencenewbie