Asymptotics of the permanents of some $(0,1)$-matrices

V. N. Shevchenko ; A. A. Pavlyuchenok

Diskretnaya Matematika, Tome 10 (1998) no. 1, pp. 82-86.

Résumé

Let $B_{nm}$ be a matrix whose columns are all possible distinct Boolean vectors of length $n$ containing exactly $m$ ones each. We consider the asymptotic behaviour of the permanents of the matrices $A(i_1,\ldots,i_k;n)$ constituted by $i_1$ copies of $B_{n1}$, $i_2$ copies of $B_{n2}$, etc., and finally, $i_k$ copies of $B_{nk}$. We demonstrate that $\operatorname{per} A(i_1,\ldots,i_k;n)$ is of order of magnitude $S_1^n$ as $n\to\infty$, where $$ S_1=S(i_1,\ldots,i_k;n)=\sum_{m=1}^k i_m\binom{n-1}{m-1}. $$ This research was supported by the Russian Foundation for Basic Research, grant 93–01–00491.