Given set $\mathcal T_n=\{0,1,\dots,2^n-1\}$ what is the minimum number of vertices $2m$ needed in a planar bipartite balanced graph such that at every $i\in\mathcal T_n$ there is a graph $G\in\mathcal G_{2m}$ (set of all bipartite planar balanced graphs on $2m$ vertices) with perfect matching count exactly $i$? Is there a tight upper bound or close form formula or at least is $m=O(n)$?
$\underline{\mbox{Conjectures}}$:
For every $\epsilon>0$ there is an $n_\epsilon\in\mathbb N$ such that $\forall n\in\mathbb N_{>n_\epsilon}$ we have $m\leq(1+\epsilon)n$ suffices.
Moreover given $n$ the graph representation is in $O(n)$ time.
It is easy to get $m=O(n^2)$ which says nothing about the difficulty of the problem. A lower bound of $m=\Omega(n)$ is shown easily from maximum number of perfect matchings on a planar graph.
I do not know how to do it. However I would think $m=2n$ might even be achievable easily.
I doubt we will solve this without number theoretic knowledge. There is something fundamental missing in representation of natural numbers.