В случайной перестановке в среднем ровно одна «своя» позиция — при любом n

n писем и n конвертов. Сколько писем попадут «своему» адресату, если разложить наугад? Интуиция шепчет: чем больше n, тем больше совпадений. На деле среднее число неподвижных точек равно 1 — и для 5, и для 20, и для миллиона. Неподвижная точка перестановки π — позиция i, где π(i) = i. Пусть I_i = 1, если письмо i на своём месте, иначе 0. Тогда P(I_i = 1) = 1/n. Число совпадений X = I_1 + ... + I_n. Индикаторы зависимы: если 19 из 20 писем уже на местах, двадцатое тоже. Кажется, складывать нельзя. Но линейность матожидания не требует независимости: E[X] = E[I_1] + ... + E[I_n] = n · (1/n) = 1. Мы проверили на Python 3.13 (seed 20261012, 50 000 случайных перестановок): — при n = 20 среднее число неподвижных ≈ 0,996 (теория: 1); — дисперсия ≈ 0,994 (теория: 1 при n ≥ 2); — ровно 0 совпадений: ≈ 36,9% (теория → 1/e ≈ 36,8%); — ровно 1: ≈ 36,8%; — ровно 2: ≈ 18,3%; — три и больше: ≈ 8%; — при n = 5 среднее тоже ≈ 1,003 — та же константа. Чаще всего 0 или 1 совпадение. Много «своих» мест — редкость, хотя максимум в прогоне доходил до 8 из 20. Где это встречается в учёбе и IT: — анализ хеш-таблиц и коллизий: ожидаемое число попаданий считают суммой индикаторов; — randomized algorithms: «сколько фиксированных точек / совпадений в среднем»; — задачи на включения-исключения и беспорядки (доля перестановок без совпадений → 1/e); — matching и случайные назначения. Оговорка: среднее равно 1, но разброс тоже порядка 1. Не путай E[X] = 1 с «почти всегда ровно одно совпадение» — часто их ноль. И не путай с числом беспорядков !n: там считают перестановки без совпадений, здесь — среднее число совпадений. Проверь в одну строку: round(20 * (1 / 20), 4) Ответ: 1.0. Короче: зависимости между позициями пугают, а матожидание всё равно складывается. Поэтому «в среднем одна своя» — не баг интуиции, а линейность. #физмат