Timeline for Non-enumerative proof that there are many derangements?
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 23, 2012 at 21:50 | comment | added | Brendan McKay | Yes, the wording was poor. I changed it. The two operations need to be inverse. A more formal treatment would be to define a (multi-)relation between the sets {permutations with 0 fixed points} and {permutations with 1 fixed points} then count the pairs of the relation in two ways. | |
| Jan 23, 2012 at 21:44 | history | edited | Brendan McKay | CC BY-SA 3.0 |
tweaks
|
| Jan 23, 2012 at 19:24 | comment | added | Timothy Chow | In case anyone trips over the same mental block I had: I found Step 2 easier to follow when I replaced the last few words by, "...that create it from a permutation with no fixed points." | |
| Jan 21, 2012 at 0:10 | history | edited | Brendan McKay | CC BY-SA 3.0 |
add irrelevant comment
|
| Jan 21, 2012 at 0:09 | comment | added | Brendan McKay | @Johan, Yes, to get a lower bound switching just two elements will suffice. Switching three gives easier counting if bounds in both directions are required. | |
| Jan 20, 2012 at 17:14 | vote | accept | Terry Tao | ||
| Jan 20, 2012 at 17:14 | comment | added | Terry Tao | Thanks, this is exactly the sort of thing I was looking for - among all the methods proposed, this seems to be the most robust (in particular, it seems to easily give the second claim in the question, namely that l random permutations generate a 2l-regular graph with probability bounded away from zero, by switching away the problematic edges). | |
| Jan 20, 2012 at 16:33 | comment | added | Barry Cipra | @Johan, I think what you're saying is along the lines of what I added to my answer after seeing Brendan's solution. | |
| Jan 20, 2012 at 16:13 | comment | added | Johan Wästlund | I guess you rotate three elements (instead of just 2) so that the claim in (2) will hold for all permutations, not just almost all? But this is not necessary in order to reach the conclusion in (3). I was thinking about swapping the first element with the unique fixed point, and inversely swapping the first element to its proper place. This provides an almost-bijection between derangements and permutations with exactly one fixed point. | |
| Jan 20, 2012 at 12:26 | history | answered | Brendan McKay | CC BY-SA 3.0 |