= Ryser's formula for the permanent
{c}
= Ryser formula
{c}
{synonym}
For an $n\times n$ <matrix> $A$, <Ryser's formula for the permanent> is
$$
\operatorname{perm}(A)=\sum_{S\subseteq\{1,\ldots,n\}}(-1)^{n-|S|}\prod_{i=1}^n\sum_{j\in S}a_{ij}.
$$
Expanding a product chooses one column for each row. The alternating subset sum cancels each choice that fails to use every column, by <inclusion-exclusion>; the surviving choices are exactly the <permutations> in the <permanent>.
For a two-by-two <matrix>, the formula becomes $(a+b)(c+d)-ac-bd=ad+bc$. Maintaining row sums while enumerating subsets in Gray-code order gives an $O(n2^n)$ arithmetic algorithm, much smaller than enumerating $n!$ permutations, although still exponential in $n$.
Back to article page
