Timeline for Secret Santa (expected no of cycles in a random permutation)
Current License: CC BY-SA 2.5
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 22, 2010 at 13:10 | comment | added | Peter Shor | @Qiaochu: I haven't verified it really carefully, but it looks like our answers agree, which is a good check on both of them. | |
| Dec 21, 2010 at 11:07 | history | edited | Qiaochu Yuan | CC BY-SA 2.5 |
deleted 64 characters in body
|
| Dec 21, 2010 at 11:06 | comment | added | Qiaochu Yuan | @Chris: I've updated with a generating function argument, but one can also reason heuristically: I believe the numbers X_r of r-cycles are asymptotically independent (and possibly there is a theorem in the literature to this effect) and so conditioning on the value of X_1 shouldn't affect the asymptotic behavior of the other X_i. The generating function computation supports this. | |
| Dec 21, 2010 at 10:55 | history | edited | Qiaochu Yuan | CC BY-SA 2.5 |
added 1928 characters in body
|
| Dec 21, 2010 at 10:46 | comment | added | Chris Taylor | Thanks Qiaochu. I suspect that with some careful accounting and a few judicious approximations, you can probably turn that argument into one which accounts for the conditioning on the number of 1-cycles, and derive the constant multiplicative factor. I'll have a crack at that if I get some spare time later today. | |
| Dec 21, 2010 at 10:34 | history | answered | Qiaochu Yuan | CC BY-SA 2.5 |