scientific article; zbMATH DE number 3627190

From MaRDI portal
Publication:4189281





A number of writers have been concerned with the following problem. Given \(n\) subsets \(A_1,\ldots, A_n\) of \(\{1,2,\ldots,n\}\), determine the number of permutations \(\pi\) such that \(\\pi(i)\in A_i\), for all \(i = 1,2, \ldots, n\). The problem is equivalent to enumerating the 1-factors of a bipartite graph and also to enumerating the permanent of a \(0,1\)-matrix. In particular, one may consider the restriction \(\vert \pi(i)-i\vert\le k\), \(1\le i<n\), where \(k\) is given. For \(k = \) constant this problem was discussed by \textit{D. H. Lehmer} [Permutations with strongly restricted displacements, Comb. Theory Appl., Colloq. Math. Soc. János Bolyai 4, 755--770 (1970; Zbl 0225.05009)]. The second author [Permutations with restriction of middle strength, Studia Sci. Math. Hung. 9(1974), 181--185 (1975; Zbl 0374.05004)] considered the values \(k\ge 1/2\) and obtained in particular the formula \(p(k) = \sum_{m=0}^k (m! S(k,m))^2\) \((n=2k)\), where \(S(k,m)\) is a Stirling number of the second kind. In the present paper an asymptotic formula is proved for \(p(k)\): I. The number \(p(k)\) is asymptotically equal to \[ (2\pi(1 - \ln 2))^{-1/2} (k!)^2 (\ln 2)^{-2k}. \] Using the same method it is also shown that the distribution of the numbers \(m' S(k,m)\), \( m = 1,\ldots, k\) is asymptotically normal. [For the entire collection see Zbl 0378.00007.]











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4189281)