The formula for the permanent I saw is $perm(A+B)$ = $\sum_{s,t} perm(a_{ij})_{i \in s, j \in t} perm(b_{ij})_{i \in \bar s, j \in \bar t} $.
I got confused as to why there's a complement bar over the subscripts of $b_{ij}$. Can anyone please show what that means computationally?
Think of the case where the matrices are diagonal matrices. In that case, the permanent is the product of the diagonal entries. In general, it will be the sum of product of entries one from each row and column, but the same principle applies to each one of the products.
So, for example, suppose $n=2$, then $(a_1+b_1)(a_2+b_2) = a_1a_2 + a_1b_2 + a_2b_1 + a_2b_2$. Notice how in each term of such a product expansion a subset of the factors are from $A$ and the rest are from $B$. That is where the complement bar comes from.