تعداد نشریات | 43 |
تعداد شمارهها | 1,658 |
تعداد مقالات | 13,563 |
تعداد مشاهده مقاله | 31,152,288 |
تعداد دریافت فایل اصل مقاله | 12,272,277 |
Conditional probability of derangements and fixed points | ||
Transactions on Combinatorics | ||
مقاله 3، دوره 12، شماره 1، خرداد 2023، صفحه 11-26 اصل مقاله (484.63 K) | ||
نوع مقاله: Research Paper | ||
شناسه دیجیتال (DOI): 10.22108/toc.2022.131705.1941 | ||
نویسندگان | ||
Sam Gutmann1؛ Mark D. Mixer* 2؛ Steven Morrow2 | ||
1Department of Mathematics, Northeastern University, 360 Huntington Ave, Boston, MA, USA. | ||
2School of Computing and Data Science, Wentworth Institute of Technology, 550 Huntington Ave, Boston, MA, USA. | ||
چکیده | ||
The probability that a random permutation in $S_n$ is a derangement is well known to be $\displaystyle\sum\limits_{j=0}^n (-1)^j \frac{1}{j!}$. In this paper, we consider the conditional probability that the $(k+1)^{st}$ point is fixed, given there are no fixed points in the first $k$ points. We prove that when $n \neq 3$ and $k \neq 1$, this probability is a decreasing function of both $k$ and $n$. Furthermore, it is proved that this conditional probability is well approximated by $\frac{1}{n} - \frac{k}{n^2(n-1)}$. Similar results are also obtained about the more general conditional probability that the $(k+1)^{st}$ point is fixed, given that there are exactly $d$ fixed points in the first $k$ points. | ||
کلیدواژهها | ||
derangement؛ fixed point؛ probability | ||
مراجع | ||
[1] T. Antonelli, A surprising link between integer partitions and Euler’s number e, Amer. Math. Monthly, 126 (2019) 418–429. [2] C. D. Evans, J. Hughes and J. Houston, Significance-testing the validity of idiographic methods: A little derangement goes a long way, British Journal of Mathematical and Statistical Psychology, 55 (2002) 385–390. [3] W. Feller, An Introduction to Probability Theory and Its Applications, 1, Third edition John Wiley & Sons, Inc., New York-London-Sydney, 1968. [4] P. C. Fishburn, P. G. Doyle and L. A. Shepp, The match set of a random permutation has the FKG property, Ann. Probab., 16 (1988) 1194–1214. [5] S. Fisk, The secretary’s packet problem, Math. Mag., 61 (1988) 103–105. [6] D. Hanson, K. Seyffarth and J. H. Weston, Matchings, derangements, rencontres, Math. Mag., 56 (1983) 224–229. [7] S. G. Penrice, Derangements, permanents, and christmas presents, Amer. Math. Monthly, 98 (1991) 617–620. [8] D. Rawlings, The poisson variation of montmort’s matching problem, Math. Mag., 73 (2000) 232–234. [9] L. Tak´acs, The problem of coincidences, Arch. Hist. Exact Sci., 21 (1979/80) 229–244. | ||
آمار تعداد مشاهده مقاله: 230 تعداد دریافت فایل اصل مقاله: 237 |