# Set of permanents over binary square matrices

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

-

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$.
@Mariano: certainly. For example it would be interesting, I think, to understand the function $n(k)$ - the minimal size of a matrix with permanent $k$. I only showed that $n(k)\le k$ but it may be much smaller than $k$. – Mark Sapir May 13 '12 at 3:01
or the function $l(n)$ which is the smallest number which is NOT a permanent of a $n\times n$-matrix. – Mark Sapir May 13 '12 at 3:10
Sequence $l(n)$ is A089477 in the Encyclopedia. – Mark Sapir May 13 '12 at 4:15