Question

consider an n???n matrix a consisting of all zeros. find the number of ways to fill this matrix with exactly n+2 ones such that the permanent of the matrix is zero. output your answer modulo 109+7.

Answer 1

There are n!
n
!
ways to place n
n
ones such that there is a one in every row and column, making the permanent non-zero. For each of these configurations, there are (n(n−1)2)
(
n
(
n
−
1
)
2
)
ways to add two more ones. If the two ones are placed at i,j
i
,
j
and k,l
k
,
l
and there are already ones at i,l
i
,
l
and k,j
k
,
j
, then the resulting configuration is also reached by adding ones at i,l
i
,
l
and k,j
k
,
j
with the ones at i,j
i
,
j
and k,l
k
,
l
already part of the original permutation. Otherwise, there is no other way to reach the same configuration. So of the n!(n(n−1)2)
n
!
(
n
(
n
−
1
)
2
)
configurations, we have to weight n!n(n−1)2
n
!
n
(
n
−
1
)
2
contributions by 12
1
2
because two of them correspond to the same result. Thus, the number of matrices with n+2
n
+
2
ones with non-zero permanent is n!((n(n−1)2)−n(n−1)4)
n
!
(
(
n
(
n
−
1
)
2
)
−
n
(
n
−
1
)
4
)
. The total number of matrices with n+2
n
+
2
ones is (n2n+2)
(
n
2
n
+
2
)
. Thus the number of matrices with n+2
n
+
2
ones with zero permament is

(n2n+2)−n!((n(n−1)2)−n(n−1)4).
Pls mark as brainliest