Sum of products over k-permutations

Question

Let $A$ be a matrix of size $K \times N$, $K \leq N$. Let $n_1...n_K$ denote a $K$-permutation of integers $1...N$ (understood as a unique assignment of a column to every row in the matrix). How to most efficiently calculate the sum, over all $K$-permutations, of products $A[1,n_1] * A[2,n_2] * ... * A[k,n_K]$?

For example, let $K=3$ and $N=5$. One possible K-permutation is (5, 1, 3), and the corresponding product is $A[1,5] * A[2,1] * A[3,3]$. But what must be calculated is the sum of such products over all K-permutations, e.g.:

$$ A[1,1] * A[2,2] * A[3,3] + \\ A[1,1] * A[2,2] * A[3,4] + \\ A[1,1] * A[2,2] * A[3,5] + \\ A[1,1] * A[2,3] * A[3,4] + \\ A[1,1] * A[2,3] * A[3,5] + \\ A[1,1] * A[2,4] * A[3,5] + \\ ... $$

I am not even sure there is an efficient (polynomial time) solution, the most I have been able to come up with has about $2^M$ complexity which is unacceptable.

Answer 1

When $K = N$, the polynomial you are trying to compute is known as the permanent. The best algorithms for computing the permanent use $\tilde{O}(2^N)$ arithmetic operations, see Wikipedia. The VP≠VNP conjecture implies that the permanent cannot be computed using a polynomial number of operations.

For general $K$, your function is a known extension of the permanent. Ryser's algorithm, one of the $\tilde{O}(2^N)$ algorithms for the square case, extends to the rectangular case as well.