Derangements, Permanents, and Christmas Presents (Q3983375)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 26700
Language Label Description Also known as
default for all languages
No label defined
    English
    Derangements, Permanents, and Christmas Presents
    scientific article; zbMATH DE number 26700

      Statements

      Derangements, Permanents, and Christmas Presents (English)
      0 references
      0 references
      27 June 1992
      0 references
      derangements
      0 references
      permanents
      0 references
      Christmas presents
      0 references
      van der Waerden's conjecture
      0 references
      Minc's conjecture
      0 references
      Let \(k\), \(n\) be integers and \(S\) be a set with \(| S|=kn\). Let \(\{T_ 1,\dots,T_ n\}\) be a partition of \(S\) with \(| T_ i|=k\) for \(i=1,\dots,n\). Let \(P_ k(n)\) be the probability that a random permutation \(\sigma\) will have the property that for all \(x\in S\) and for all \(i\in\{1,\dots,n\}\), if \(x\in T_ i\), then \(\sigma(x)\notin T_ i\). The standard derangement problem is the case \(k=1\), and the ``Christmas Gift Problem'' is the case \(k=2\). Using van der Waerden's conjecture [see \textit{G. P. Egorychev}, Adv. Math. 42, 299-305 (1981; Zbl 0478.15003) and \textit{D. I. Falikman}, Math. Notes 29, 475-479 (1981; Zbl 0475.15007)] and Minc's conjecture [see \textit{A. Schrijver}, J. Comb. Theory, Ser. A, 25, 80-83 (1978; Zbl 0391.15006)] the author gives a simple proof of the following result: \(\lim_{n\to\infty}P_ k(n)=e^{-k}\) for any fixed \(k\).
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references