We all know what a permutation is. So, I remember a good problem from school. Let P be a permutation of 1, 2, 3, .... n. We define the function f(P) as the number of positions where P[i] = i (also known as fixed points I think). What is the expect value of f :)
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | Radewoosh | 3415 |
| 8 | Um_nik | 3376 |
| 9 | maroonrk | 3361 |
| 10 | XVIII | 3345 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 162 |
| 2 | adamant | 148 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 143 |
| 5 | errorgorn | 141 |
| 6 | cry | 138 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 10 | soullless | 133 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 21.05.2026 15:53:18 (g1).
Десктопная версия, переключиться на мобильную.
При поддержке
I think there is a O(n) solution using dp, let dp[i]: number of ways that i numbers can arrangue that there isn't a p[j]=j, then your answer is $$$\sum\limits_{i=2}^{n} (n-i)*dp[i]*comb(n, i)/n! + 1/n!$$$, and $$$dp[i]=(i-1)*(dp[i-1]+dp[i-2]), 2 \leq i$$$
As much as I remember there is also an O(1) solution, good dp :O
Let p(i) be the probability that i is a fixed point, then p = (n-1)!/n!. Using linearity of expectation, f(P) = sum of p(i)*1 = |P| * 1/|P| = 1
Nice :)
I know this works but this feels so unnatural to me.
It really feels like $$$E[X + Y] = E[X] + E[Y]$$$ should only work if $$$X$$$ and $$$Y$$$ are "independent" (in some sense). Abstractly not so much, but looking at this problem it just seems so weird like, that can't possibly be true.
Not really. Expected of sum is sum of expected even if the random variables are not independent. This is used really often in problems, where you "break" the expected into a sum of dependent but computable sub-problems. I think that what you meant is that
E(X and Y) = E(X) * E(Y)only and only if X and Y are independent probabilities. Check this for more infoNo, I'm very well aware of how elementary probability theory works.
All I'm saying is that intuitively, it does feel wrong.
When intuition gives incorrect answers, should we continue to trust it? or is there some way to fix intuition so that non-intuitive facts are intuitive?
Yes, if you work on something, solve problems etc for a while, your intuition will develop and correct its own mistakes.
ban