Ryser has shown that the permanent of an $ n \times n$ matrix $ A=(a_{ij})$ can be expressed as

\begin{align} Perm(A) = (-1)^n \sum_{s \subset [n]} (-1)^{|s|} \prod_{i=1}^n \sum_{j \in s} a_{ij}, \end{align}

where $ [n]=\{1,2,\dots,n\}$ . This algorithm runs in $ \mathcal{O}(2^{n-1}n^2)$ time. I’ve been trying to derive this, but can’t quite get the result. Here’s my work so far.

The outer sum is over all non-empty subsets of $ [n]$ , of which there are $ 2^n-1$ . We recall that the number of subsets of size $ r$ is $ {n \choose r}=\frac{n!}{r!(n-r)!}$ .

For each set $ s$ in the outer sum we compute $ \sum_{j \in s} a_{ij}$ , which uses $ |s|-1$ additions. Next, this sum sees the product $ \prod_{i=1}^n$ , which takes $ n-1$ multiplications. This happens for each non-empty subset of $ [n]$ , so there are the following number of total additions:

\begin{align} \sum_{s \subset [n]} \left(|s|-1\right) &= \sum_{k=1}^n (k-1) {n \choose k} \ &= \sum_{k=1}^n k {n \choose k} – \sum_{k=1}^n {n \choose k} \ &= n \sum_{k=1}^n {n-1 \choose k-1} – \left(2^n – 1\right) \ &= n \left( 2^{n-1}-1 \right) – \left(2^n – 1\right) \ &=n2^{n-1} – 2^n -n +1. \end{align}

The total number of multiplications is $ (n-1)(2^n-1)$ .

There is also the $ (-1)^{|s|}$ , which takes another $ 2^n-1$ operations in total.

This gives us a grand total of $ n2^n + n 2^{n-1} – 2^n -2n+1$ , which is not correct. It looks like I’m off by a factor of $ n$ on the second term here. Where am I going wrong?