Permanent identities for special classes of matrices 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?
 A: 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.
A: A large class of matrices for which the permanent can be efficiently computed has been constructed by Klaus Meer:
An extended tree-width notion for directed graphs related to the computation of permanents: presentation and publication
A: This is somewhat of a digression, but I thought it worthwhile to point out that in the tropical case, actually the permanent (equivalently determinant) is much easier to compute, and requires solving an assignment problem. Specifically, 
(see pg. 19 of this book by Maclagan and Sturmfels, the tropical permanent is 
\begin{equation*}
  \text{tp}(X) := \bigoplus_{\pi \in S_n} x_{1\pi(1)}\odot \cdots \odot x_{n\pi(n)},
\end{equation*}
and this number is given by the solution to the minimization problem
\begin{equation*}
   \min\lbrace x_{1\pi(1)}\odot \cdots \odot x_{n\pi(n)} \mid \pi \in S_n\rbrace,
\end{equation*}
which can be computed in $O(n^3)$ time (Hungarian assignment method).
A: You of example is a particular case of a slightly more general well known(and almost equally simple) situation when the rank is bounded by a fixed constant.
