Counting perfect matchings via inclusion-exclusion
The permanent of an n×n matrix is like the determinant but with all positive signs: perm(A) = Σσ∈Sn ∏ ai,σ(i). It counts weighted perfect matchings in bipartite graphs. Ryser's formula (1963) computes it in O(2n·n) time using inclusion-exclusion over subsets, far better than n! but still #P-hard in general.