# Sum of products over k-permutations

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.

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.