scientific article; zbMATH DE number 3627190
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.]
- Analyse combinatoire. \(k\)-distorsions de \([1,n]\) et de \({\mathbb{N}}\). (Combinatorial analysis. \(k\)-distortions of \([1,n]\) and of \({\mathbb{N}})\)
- On permutations involving pairs of twins
- Restricted 1-3-2 permutations and generalized patterns
- Statistics on pairs of permutations
- Enumeration of restricted permutation triples
- Counting pattern-free set partitions. I: A generalization of Stirling numbers of the second kind
- Asymptotic enumeration of lonesum matrices
- Mixed restricted Stirling numbers
- Block patterns in Stirling permutations
- Stirling permutations on multisets
- Simple permutations and pattern restricted permutations
- Toppling on permutations with an extra chip
- Multi-restrained Stirling numbers.
- scientific article; zbMATH DE number 2186873 (Why is no real title available?)
- Enumeration formulæ for pattern restricted Stirling permutations
- Toppleable permutations, excedances and acyclic orientations
- scientific article; zbMATH DE number 975364 (Why is no real title available?)
- Combinatorial properties of poly-Bernoulli relatives
- On the number of certain types of strongly restricted permutations
- scientific article; zbMATH DE number 5063547 (Why is no real title available?)
- Restricted permutations
- An asymptotic formula for the number of stabilized-interval-free permutations
- Some asymptotic bijections
- Stirling permutations, cycle structure of permutations and perfect matchings
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)