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
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
0.7913233041763306
0 references
0.7757153511047363
0 references
0.7571494579315186
0 references
0.7546378970146179
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