计算可得到非零对角线的行置换数量

嘿，这个问题刚好戳中了组合数学里一个经典的概念，咱们结合你提到的直觉一步步拆解：

首先，你的两个思路完全找对了方向，咱们先把问题和你熟悉的模型对应上：

对应n-rooks（n车）问题 #

你可以把二进制矩阵A看成一个n×n的棋盘：A[i][j]=1的位置就代表棋盘上第i行第j列的格子可以放车，A[i][j]=0的位置则不能放。那你要找的行置换数量，本质上就是在这个棋盘上放置n个互不攻击的车（每行每列恰好一个）的合法方式总数——每一种合法的放法，就对应一个满足条件的置换矩阵P：把A的行重新排列后，PA的对角线刚好就是每个车所在的位置（全为1）。

对应有向图模型 #

你提到的有向图思路也非常准确，咱们把它落地：
构造一个有向图G，顶点集是{1,2,...,n}（对应矩阵的行和列），如果A[i][j]=1，就从顶点i到顶点j画一条有向边。那你要找的置换数量，就是这个图中覆盖所有顶点的置换分解的数量——换句话说，就是能把所有顶点分成若干个不相交的有向环的方式数，每个环上的边都对应A中的1元素。

正式的数学定义：积和式（Permanent） #

上面两种模型对应的计数结果，其实就是矩阵A的积和式，记为perm(A)。它的定义是：
$$perm(A) = \sum_{\sigma \in S_n} \prod_{i=1}^n A[i][\sigma(i)]$$
这里的$S_n$是n个元素的所有置换集合，求和式里的每一项$\prod_{i=1}^n A[i][\sigma(i)]$只有当所有$A[i][\sigma(i)]=1$时才等于1，否则为0，所以整个求和的结果就是满足条件的置换σ的总数——也就是你要找的置换矩阵P的数量。

补充个小细节：积和式和行列式长得很像，但行列式会给每个置换加符号（根据置换的奇偶性），而积和式是直接求和，这也导致积和式的计算是#P-难的（简单说就是大n的情况下没有高效的多项式时间算法），不过小n的话可以直接枚举或者用递推公式计算。

举两个简单例子验证下：

• 如果A是n阶单位矩阵，只有恒等置换满足条件，所以perm(A)=1；
• 如果A是全1矩阵，所有置换都满足条件，所以perm(A)=n!。

备注：内容来源于stack exchange，提问作者graphitump