Timeline for What is the function defined by f(k) = #σ1({1,2,…,k})∩σ2({1,2,…,k})∩{1,2,…,k}, where σ1,σ2 are a uniformly random permutations of size N?
Current License: CC BY-SA 4.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 16, 2023 at 3:23 | comment | added | David Pechersky | So in the answer above (unlike my answer to your first question), I'm not intersecting with {1,2,3,...,k}. If we take the images of {1,2,3,...,k} under two random permutations and we also intersect this with {1,2,3,...,k}, this is the same (in distribution) as intersecting three random permutations. As per my answer above, this is concentrated around n*(k/n)^3, which matches what you got in your simulation. | |
| Jan 15, 2023 at 10:13 | comment | added | Alexander Chervov | Thank you very much for your excellent answers ! The only thing - simulation suggests the leading coefficient is x^3/N^2 - when we have two permutations. E.g. kaggle.com/code/alexandervc/… | |
| Jan 11, 2023 at 9:50 | vote | accept | Alexander Chervov | ||
| Jan 9, 2023 at 20:46 | history | answered | David Pechersky | CC BY-SA 4.0 |