In the course of discussing another MO question we realized that we did not know the answer to a more basic question, namely:
Is it true that for every positive integer $k$ there exists a balanced bipartite graph with exactly $k$ perfect matchings?
Equivalently, as stated in the title, is every positive integer the permanent of some 0-1 matrix?
The answer is surely yes, but it is not clear to me how to prove it. Entry A089479 of the OEIS reports the number $T(n,k)$ of times the permanent of a real $n\times n$ zero-one matrix takes the value $k$ but does not address the question of whether, for every $k$, there exists $n$ such that $T(n,k)\ne 0$. Assuming the answer is yes, the followup question is, what else can we say about the values of $n$ for which $T(n,k)\ne 0$ (e.g., upper and lower bounds)?
Best Answer
The answer to the question is yes. Given $k$, the 0-1 matrix given by
$1$ $1$ $\dotsc$ $1$ $0$ $0$ $\dotsc$ $0$ $0$ $0$ $0$
$0$ $1$ $1$ $0$ $\dotsc$ $0$ $0$ $\dotsc$ $0$ $0$ $0$
$0$ $0$ $1$ $1$ $0$ $\dotsc$ $0$ $\dotsc$ $0$ $0$ $0$
$\dotsc$
$1$ $0$ $0$ $0$ $0$ $\dotsc$ $\dotsc$ $0$ $0$ $0$ $1$
where the first row has precisely $k$ entries equal to $1$, evidently has permanent equal to $k$.
For $k=1$ the matrix is ($1$). For $k=2$ the matrix is
$1$ $1$
$1$ $1$
For $k=3$ the matrix is
$1$ $1$ $1$
$0$ $1$ $1$
$1$ $0$ $1$.
For $k=4$ the matrix is
$1$ $1$ $1$ $1$
$0$ $1$ $1$ $0$
$0$ $0$ $1$ $1$
$1$ $0$ $0$ $1$
which evidently has permanent equal to $4$.
Please note that also, for each given $k$ and $1\leq \ell \leq k$, this construction can be tweaked to give an explicit $k\times k$ sized $0$-$1$-matrix having permanent precisely $\ell$, just by making the first row have precisely $\ell$ entries equal to $1$.
Please also note that my construction does not have any bearing on the interesting and apparently difficult question which was cited in the present OP: my construction is too wasteful: it utilizes a $k\times k$ matrix, which is far too large when it comes to meet the demands of the OP in said question.