# Missing count in number of perfect matchings

Let $$f(G)$$ give number of perfect matchings of a graph $$G$$.

Denote $$\mathcal N_{2n}=\{0,1,2,\dots,n!-1,n!\}$$.

Denote collection of all $$2n$$ vertex balanced bipartite graph to be $$\mathcal G_{2n}$$.

There are many $$m\in\mathcal N_{2n}$$ that do not have a $$G\in \mathcal G_{2n}$$ such that $$f(G)=m$$ (refer Are all numbers from $1$ to $n!$ the number of perfect matchings of some bipartite graph?).

How many numbers do we hit or miss in $$\mathcal N_{2n}$$?

Can $$\bigg|{\big\{m\in\mathcal N_{2n}:f^{-1}(m)\cap\mathcal G_{2n}\neq\emptyset\big\}}\bigg|=O(2^{n^c})$$ hold for some fixed $$c\in(0,1)$$?

Conjecture (Update):

$$\bigg|{\big\{m\in\mathcal N_{2n}:f^{-1}(m)\cap\mathcal G_{2n}\neq\emptyset\big\}}\bigg|={n^{\Omega(n)}}$$ holds.

• Do you know answer for say $n=4$ and $n=5$? Or a fast algorithm for given $m$ to check. – kakia Sep 19 '16 at 9:46