# Number of permutations of items in a table where you may only select one item per column and row

I hope people will indulge me a potentially pretty easy problem.

I have a table like the following: \begin{array}{|c|c|c|c|} \hline & A & B & C \\ \hline D & 70 & 23 & 0\\ \hline E & 80 & 0 & 16 \\ \hline F & 40 & 86 & 0 \\ \hline \end{array}

The columns represent jobs, the rows represent candidates, and the numbers represent the percent match. For example, Candidate D is a 70% fit for Job A and a 23% fit for Job B, but isn't a fit in the least for job C.

The constraint, of course, is that you can only have one candidate per job - i.e. you can only select one item per row and one per column. If you assign Candidate D to job A, you can't also assign that candidate to Job B. Similarly, if you've already filled Job A, you can't assign, for example, Candidate E to it.

Note that this is specifically not limited to a 3x3 table like I show above - the problem is just some mxn table, where m and n may or may not be equal. (Obviously, $m, n \in \mathbb{N}$).

In this case, in the first step, you have $3$ choices. In the second step, you have $2$ choices. In the final step, you only have $1$ choice. This is true regardless of which job or candidate to start with. In this particular case, it just so happens that $3 + 2 + 1 = 3 * 2 * 1 = 3!$. if $n \le m$, there will be $n! = 3! = 3 * 2 * 1 = 6$ possible arrangements. This just happens to be true for a 3x3 table, though, so, in general it won't be the case that $n! = n + (n - 1) + (n - 2) + ... + 1$.

Am I correct in thinking that, if $n \le m$, this is just $$\frac{m!}{(m-n)!}$$

Or do I have to go with $$n + (n - 1) + (n - 2) + ... + 1$$ after all? (I was confusing myself horribly earlier and even tried $$n * (n + (n - 1) + (n - 2) + ... + 1)$$ at one point, but I don't think that that's correct).

For context (and this isn't what I'm asking about at this point), my ultimate goal is to come up with a way to identify which assignment of candidates to jobs will result the greatest satisfaction all around. In the case of the table I showed above, you should assign candidate D to job A, candidate E to job C, and candidate F to job B for a total "satisfaction rating" of $70 + 16 + 86 = 172$. For the sake of comparison, I'm trying to figure out the difficulty of a "brute force" algorithm - that kind of a solution would be fine for a small table like this, but if you had hundreds of jobs and candidates I'll probably want to be a little smarter than that.

• This is weighted bipartite matching. See the Hungarian method. – saulspatz Jul 19 '18 at 23:51
• It's not clear what your question is. The title seems to indicate that you want to know the number of possible selections; the text near the end rather suggests that you want an algorithm for optimizing over all selections. – joriki Jul 20 '18 at 5:19
• @joriki No, I'm just looking for an answer to the question in the title. The last paragraph is just context. – EJoshuaS Jul 20 '18 at 12:48
• @saulspatz Thanks, that's a very constructive piece of information - it could be very valuable. – EJoshuaS Jul 20 '18 at 16:07

You're right that the number of different selection for $m\ge n$ is
$$\frac{m!}{(m-n)!}\;.$$
There are $m$ possible selections in the first column, $m-1$ in the second, and so on, until the $n$-th column, where there are $m-n+1$ selections left. These are all independent and thus need to be multiplied, leading to your result.