12
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Some Connections Between Cycles and Permutations that Fix a Set and Touchard Polynomials and Covers of Multisets

      Preprint

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          We present a new proof of a fundamental result concerning cycles of random permutations which gives some intuition for the connection between Touchard polynomials and the Poisson distribution. We also introduce a rather novel permutation statistic and study its distribution. This quantity, indexed by \(m\), is the number of sets of size \(m\) fixed by the permutation. This leads to a new and simpler derivation of the exponential generating function for the number of covers of certain multisets.

          Related collections

          Most cited references4

          • Record: found
          • Abstract: found
          • Article: found
          Is Open Access

          Permutations fixing a k-set

          Let \(i(n,k)\) be the proportion of permutations \(\pi\in\mathcal{S}_n\) having an invariant set of size \(k\). In this note we adapt arguments of the second author to prove that \(i(n,k) \asymp k^{-\delta} (1+\log k)^{-3/2}\) uniformly for \(1\leq k\leq n/2\), where \(\delta = 1 - \frac{1 + \log \log 2}{\log 2}\). As an application we show that the proportion of \(\pi\in\mathcal{S}_n\) contained in a transitive subgroup not containing \(\mathcal{A}_n\) is at least \(n^{-\delta+o(1)}\) if \(n\) is even.
            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            The Enumeration of Covers of a Finite Set

              Bookmark
              • Record: found
              • Abstract: not found
              • Article: not found

              Four random permutations conjugated by an adversary generateSnwith high probability

                Bookmark

                Author and article information

                Journal
                2017-01-17
                Article
                1701.04855
                7767df0a-e254-4a40-8878-0a8664452111

                http://arxiv.org/licenses/nonexclusive-distrib/1.0/

                History
                Custom metadata
                60C05, 05A05, 05A15
                math.PR

                Probability
                Probability

                Comments

                Comment on this article