The permanent $P(M)$ of a matrix $M$ of size $n$ is defined to be:
$$
P(M) := \sum\_{\sigma \in S\_n}\prod\_{i=1}^n M\_{i\sigma(i)}
$$


If you have a matrix of the form
$$
M\_{ij} := A\_i + B\_j
$$
where $A$ and $B$ are indexed sets of numbers and if $x\_k(S)$ is the sum of all products of $k$ elements taken from the set $S$, then:
$$
P(M) = \sum\_{k=0}^n k! (n-k)! x\_k(A) x\_{n-k}(B)
$$


This gives a polynomial-time algorithm for computing the Permanents of matrices such as:
$$
\begin{bmatrix}
1 & 2 & 3 \\
4 & 5 & 6 \\
7 & 8 & 9
\end{bmatrix}
$$
Here, $A\_i = i$ and $B\_i = 3\*(i-1)$, and the Permanent is $450$.


What other classes of matrices are known to have efficiently computable or otherwise interesting formulas for their Permanents?



Permanent identities for special classes of matrices
The permanent of the biadjacency matrix of a bipartite graph counts the number of perfect matchings of that graph. By the biadjacency matrix, I mean the matrix with rows indexed by one of the independent sets and the columns indexed by the other. An entry is 1 if the vertex represented by the row and the vertex represented by the column are adjacent and 0 otherwise. 


It is known that counting the number of perfect matchings of planar bipartite graphs is computable in polynomial time. So computing the permanent of any matrix representing a planar bipartite graph when viewed as a biadjacency matrix can be done in polynomial time.


