Deriving the Time Complexity of Ryser's Algorithm for Evaluating the Permanent of a Matrix 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) &amp;= \sum_{k=1}^n (k-1) {n \choose k} \\
&amp;= \sum_{k=1}^n k {n \choose k} - \sum_{k=1}^n {n \choose k} \\
&amp;= n \sum_{k=1}^n {n-1 \choose k-1} - \left(2^n - 1\right) \\
&amp;= n \left( 2^{n-1}-1 \right) - \left(2^n - 1\right) \\
&amp;=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?
For a given $s$, you do $(|s|-1)n$ additions, not $|s|-1$ additions: you have to compute the inner sum for each $i\in [n]$. Thus, you are missing a factor of $n$.