Перестановки без неподвижных точек
Беспорядок (субфакториал !n): каждый из n различных объектов уходит не на свой номер. Классика — шляпы в гардеробе, письма не в свои конверты. Раздел: комбинаторика.
Контроль: !0 = 1, !1 = 0, !2 = 1, !4 = 9, !5 = 44.
n целое от 0 до 15. Родитель математика.
!n = (n − 1) [!(n − 1) + !(n − 2)]
!n = (n − 1) [!(n − 1) + !(n − 2)]
Искомое — D. Страница считает рекурсией, не рядом «n! / e» как поле: букву e на сайте занимает основание логарифма, её нельзя класть в формулу как переменную.
Не n! и не круг
Не все перестановки n!. Не хоровод (n−1)!. Не P(n,k) с выбором k мест. Не сюръекции на k меток.
Как пользоваться
Одно поле n. Получите, сколькими способами перемешать n карточек так, чтобы ни одна не осталась на своём индексе. Для вероятности «случайная перестановка — беспорядок» делите D на n! в тетради.
Примеры
1. Пусто. !0 = 1.
2. Один. !1 = 0.
3. Двое. !2 = 1: только обмен.
4. Четверо. !4 = 9.
5. Пятеро. !5 = 44.
6. Запрет. n = 16.
Ещё задачи
Три конверта: !3 = 2. Циклы (123) и (132), не транспозиция одного письма.
Вероятность при большом n стремится к 1/e ≈ 0,367. Страница e не делит: !5 / 120 = 44/120 ≈ 0,367 уже близко.
Связь с n!: доля беспорядков !n / n!. Не подставляйте эту долю в поле n.
Частичный беспорядок «ровно k не на месте» — другое число, не эта страница. Здесь все n сдвинуты.
Не кладите k мест как во размещениях: беспорядок всегда на всех n.
!6 = 265. Проверка: 5×(44+9) = 265.
Карты колоды 52 страница не считает: n > 15.
Круг из 5 даёт 24, а !5 = 44. Разные запреты.
Одна размерность: число перестановок-беспорядков.
Два гардероба независимы: произведение двух !n, не сумма.
Шляпы и конверты
Чертёж: n крючков и n шляп, стрелки перестановки без петель длины 1.
Памятка: ни одной неподвижной точки, не вращение стола.
Хаб комбинаторики ставит !n рядом с n!, чтобы не выдать 120 вместо 44.
Итог: рекурсия, !0 = 1, !1 = 0, n ≤ 15.
Включение-исключение
Формула !n = n! Σ_{k=0}^{n} (−1)^k / k! даёт то же целое. Знаки плюс-минус: вычли тех, у кого хотя бы одна шляпа своя, вернули две свои, и так далее. Страница рекурсию, сумму в уме для проверки малых n: !2 = 2!(1 − 1 + 1/2) = 1.
Округление n!/e до ближайшего целого совпадает с !n при n ≥ 1. Это мнемоника, не поле ввода.
Родитель математика. Сосед по всем перестановкам: P(n,n).
Итог журнала: !n рекурсией, без неподвижных точек, не (n−1)!.
Контроль: 1; 0; 1; 9; 44. n = 16 нельзя.
Пример: !7 = 6×(265+44) = 1854.
Не подставляйте 5! = 120 как ответ «шляпы».
Рабочий пример: восемь писем !8 = 14833. Проверка рекурсией от !6 и !7.
Связь с C: член включения C(n,k) · !(n−k). Сумма даёт !n. Страница сумму не раскладывает по k.
Итог для отчёта: n карточек, запрет совпадения индекса, одно число D.
Финальный якорь: !5 = 44. !1 = 0. n = 16 нельзя.
Добор: не называйте беспорядок «круговой перестановкой».
Ещё якорь: !3 = 2. Два трёхцикла, транспозиции не подходят: у транспозиции третий на месте.
Журнал: секретный Санта на 6 человек без автоподарка: !6 = 265, если направленный цикл не требуют. Если нужен один цикл длины 6 — уже меньше и не эта страница.
Не путайте с анаграммами: там кратности букв, не запрет позиции.
Финальный блок: субфакториал, рекурсия, n ≤ 15, без e в полях.
Ещё контроль: !4 = 9. Список из четырёх: девять полных сдвигов.
Почему умножают на n−1? Первый элемент садится на чужое место n−1 способами, дальше два случая: обмен с хозяином или нет.
Итог абзаца: полный сдвиг номеров, ни одного совпадения.
Связь с n!: знаменатель вероятности, не ответ.
Две колоды мешают независимо — два !n.
Финальный добор: !n, не n!, не (n−1)!, не P(n,k), не сюръекции.
Отчёт: «сорок четыре» без n = 5 не отличить от других !n.
Стык с кругом: там отождествляют поворот, здесь запрещают петли длины 1.
Не кладите 0,5 в n.
Якорь: 1; 0; 1; 9; 44. Шестнадцать нельзя.
Приложение: 10 гостей сдают пальто: !10 = 1 334 961. Вероятность ≈ 0,3679.
Одинаковые шляпы ломают модель: объекты должны быть различными.
Повторный расчёт после того, как одного оставили на месте сознательно: это уже не полный беспорядок, считайте !(n−1) только если он точно на своём и остальные сдвинуты — нет: если один фиксирован, остальные должны быть беспорядком на n−1, но это «ровно один на месте», другое число.
Типичные ошибки
- Ответить n!.
- Ответить (n−1)! как круг.
- Путать с «хотя бы один не на месте».
- n > 15.
- Дробное n.
Соседи: факториал, размещения, круговые перестановки, сочетания, сюръекции.
Итог добора: субфакториал !n, никто на своём месте, рекурсия, n от 0 до 15.
Частые вопросы
- Сколько беспорядков из 5 элементов?
- !5 = 44. Рекурсия: 4 × (!4 + !3) = 4 × (9 + 2) = 44.
- Почему !0 = 1 и !1 = 0?
- Пустую перестановку считают беспорядком. Один элемент обязан остаться на месте — беспорядков нет.
- Это рассадка по кругу?
- (n−1)!. Вращения стола, не «никто напротив своей карточки».
- n больше 15?
- Страница не считает: держим точное целое. Дальше — в тетради.
- Где хаб?
- Комбинаторика.
Источники
- Школьная комбинаторика: P(n,k) = n!/(n−k)!, C(n,k) = n!/(k!(n−k)!), размещения с повторениями n^k, сочетания с повторениями C(n+k−1, k), полиномиальный коэффициент n!/(n₁! n₂! …).