Dear community,

I have the following combinatorial question which I will explain in short first and then with some more detail. At the end you will find a very simple example.

## Short version

Le $A \in \mathbb{N}_0^{n \times n}$ be a symmetric matrix with zeros on the diagonal, whose row- and column-sums add up to some fixed, positive integer $c$. In how many ways can we write $A$ as a sum of permutation matrices, ignoring the order of summation?

## Detailed version

Suppose you have a quadratic matrix $A$ of dimension $n$ with non-negative integral entries whose row- and column-sums add up to some common number $c$. Then it is known that $A$ can be written as a sum of $c$ permutation matrices, i.e. we have that
$$A = P_{\sigma_1} + P_{\sigma_2} + \ldots + P_{\sigma_c},$$
where each $P_{\sigma_i}$ is a permutation matrix representing a
permutation $\sigma_i \in S_n$, $S_n$ being the symmetric group of
order $n$. Let's call the set $\{ \sigma_1, \sigma_2, \ldots, \sigma_n
\}$ a *decomposition* for $A$.

If we add the property that the diagonal of $A$ vanishes (i.e. contains only zeros), the permutation matrices $P_{\sigma_i}$ of any decomposition as above will have vanishing diagonals, too, i.e. the corresponding permutations $\sigma_i$ will have no fixed points.

If we add another property to $A$, namely that it is symmetric, we get decompositions with even more structure. Either all matrices of a decomposition are symmetric themselves (which in this framework is the case, if and only if the cycles of the corresponding permutations are all of length two), or the non-symmetric matrices add up to something which is symmetric. This is for example the case if for a given permutation $\sigma_i$, the permutation $\sigma_i^{-1}$ (inverse in $S_n$, i.e. with respect to composition) is also in the decomposition, because $P_{\sigma_i^{-1}} = P_{\sigma_i}^T$ and $P_{\sigma_i} + P_{\sigma_i}^T$ is symmetric, but this condition is not necessary.

My **question** is the following: How many decompositions are there in total?

## Example

Let me give you a very simple example for the situation in the case $n=3$.

If $$A = \begin{pmatrix} 0 &1 &1 \\ 1 &0 &1 \\ 1 &1 &0 \end{pmatrix} $$

the only possible way to write this as a sum of permutation matrices (up to order of summands) is

$$ A = \begin{pmatrix} 0 &0 &1 \\ 1 &0 &0 \\ 0 &1 &0 \end{pmatrix} + \begin{pmatrix} 0 &1 &0 \\ 0 &0 &1 \\ 1 &0 &0 \end{pmatrix}, $$ and the corresponding decomposition is $\{ (1 3 2), (2 3 1) \}$.

Thanks for your help,

Simon