Ассоциативные алгебры

kukina_eg


Задачи и незадачи


Previous Entry Share Next Entry
Подсчеты перестановок
Ассоциативные алгебры
kukina_eg
Задача снова из пробного вступительного экзамена в ШАД Яндекса.

Задача. Рассмотрим случайную перестановку на n элементах. Докажите, что данные k элементов окажутся в одном цикле с вероятностью 1/k.

Решение. Давайте просто посчитаем количество перестановок, в которых есть цикл, содержащий данные k элементов.
Общее количество перестановок мы знаем, это n!

Вопрос 1. Сколько существует циклов длины m на множестве из m элементов? Очевидно, (m-1)! Действительно, цикл -- это расстановка m элементов по кругу. Т.е. грубо говоря, любая расстановка этих чисел. Т.е. m! А теперь мы вспоминаем, что нам неважно, с какого элемента начинать. Поэтому надо разделить на m. (Варианты, полученные друг из друга поворотом круга считаются одинаковыми циклами, а поворотов как раз m штук).

Посчитаем, сколько перестановок есть, где данные k элементов входят в цикл длины k+t. Очевидно, если t элементов уже выбраны, то составить цикл из k+t элементов есть (k+t-1)! способов. Оставшиеся (n-k-t) элементов могут образовать любую перестановку (т.е. (n-k-t)! вариантов). Ну, и выбрать t элементов из оставшихся (n-k) можно Ctn-k способами. Итого, Ctn-k(k+t-1)!(n-k-t)! перестановок, содержащих цикл длины k+t, включающий данные k элементов.

А всего перестановок, включающие данные k элементов получается


Отдельно докажем такую формулу:


Ее будем доказывать из соотношения Cnk+Cnk+1=Cn+1k+1, которое можно доказать непосредственно.

В сумме заменим Сs0 на Сs+10 (они оба равны 1). Теперь первые 2 слагаемых сворачиваются Сs+10s+11s+21. Прибавляем третье слагаемое, опять сворачивается и т.д. В итоге получим то, что надо.

Поэтому и получается, что общее количество перестановок, содержахих цикл, включающий данные k элементов равно
(n-k)!(k-1)!С(k-1)+(n-k)+1n-k.
Остальное элементарно упрощаем. И искомое количество подстановок равно n!/k.
Что и требовалось.

  • 1
  • 1
?

Log in