I am interested in the collection of possible values for permanents over square binary matrices. Consider $n \times n$ 0-1 matrices. The possible permanents for $n=1$ are $\{0,1\}$. For $n=2$ the possible permanents are $\{0,1,2\}$, and for $n=3$ the permanents are $\{0,1,2,3,4,6\}$. Note that $5$ is missing for $n=3$.


Let $p(n)$ denote the set of permanents for $n \times n$ binary matrices, and let $$p(\mathbb{N}) = \bigcup\_{n \in \mathbb{N}} p(n)$$ We can show at least that $n! \in p(\mathbb{N})$ for all $n$ and that $p(\mathbb{N})$ is closed under products. 


Is this set $p(\mathbb{N})$ well understood? A pointer would be welcome. If $\mathbb{N} \subset p(\mathbb{N})$, a construction proof would be appreciated. It is not clear how to extend the trivial rectangular matrix with permanent $k$ to a square matrix.


The following related integer sequence counts distinct permanents: <http://oeis.org/A087983>



Set of permanents over binary square matrices
That set consists of all natural numbers. Consider the $n\times n$-matrix $A=(a\_{ij})$ where all numbers on the diagonal, first row and first column are equal to 1, all the other entries are 0. Then the permanent of that matrix is $n$. Indeed, each non-zero summand in the definition of permanent should start with some $a\_{1,i}$. Then the $i$-th factor of that product, $i > 1$, cannot be $a\_{i,i}$. It must then be $a\_{i,1}$. Hence all the other factors in that product are from the diagonal. Therefore exactly one non-zero summand in the permanent contains $a\_{1,i}$, for every $i=1,...,n$. So the permanent contains exactly $n$ non-zero summands, and is equal to $n$.


