We are given a set of distinct objects, e.g. $\{a,b,c\}$, and each object can be assigned to a mix of different positions, e.g.
$a$ can be in position $1,2$
$b$ can be in position $1,2,3$
$c$ can be in position $2,3$
Is their a formulaic way to determine total number of permutations without repetition? E.g.
$a-b-c$
$b-a-c$
I know a brute force way of doing this but would love to know an efficient way to count the total number of permutations.
Best Answer
One can succinctly express the count of possible matchings of items to allowed positions (assuming it is required to position each item and distinct items are assigned distinct positions) by taking the permanent of the biadjacency matrix relating items to allowed positions.
In the example above we would express the count, taking items $a,b,c$ as columns and $1,2,3$ as rows:
$$ \operatorname{perm} \begin{pmatrix} 1 & 1 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 1 \end{pmatrix} = 3 $$
Sadly the computation of a matrix permanent, even in the restricted setting of "binary" matrices (having entries $0,1$), was shown by Valiant (1979) to be $\#P-$complete. The topic was discussed in this previous Math.SE Answer. See also this slightly more recent Math.SE Question.
A naive approach to computing a permanent exploits the expansion by (unsigned) cofactors in $O(n!\; n)$ operations (similar to the high school method for determinants). A clever algorithm by H.J. Ryser (1963) allows the exact evaluation of an $n\times n$ permanent in $O(2^n n)$ operations (based on inclusion-exclusion).
A deterministic polynomial time algorithm for exact evaluation of permanents would imply $FP=\#P$, which is an even stronger complexity theory statement than $NP=P$. So the prospects for this appear extremely dim at present. Interest in boson sampling as a model for quantum computing draws upon a connection with evaluation of permanents.