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?