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?