Дано:
- n — порядок перестановки.
Найти:
- a) Доказательство, что Q(n) — число перестановок порядка n без неподвижных точек.
- б) Рекуррентная формула вероятности p(n) о том, что случайно взятая перестановка порядка n не содержит неподвижных точек.
- в) Вероятность p(n, k) того, что в случайной перестановке порядка n ровно k неподвижных точек.
Решение:
a) Перестановка без неподвижных точек называется дерangements (перестановки, в которых ни один элемент не остается на своем месте). Для вычисления Q(n) можно использовать следующее соотношение:
Q(n) = n! * Σ(k=0, n) ((-1)^k / k!), где Σ — сумма от 0 до n.
Это выражение основано на принципе включения-исключения. Каждый элемент можно либо разместить на своем месте (в этом случае мы исключаем его из перестановки), либо поместить в какое-то другое место. Таким образом, Q(n) можно выразить через факториал n! и сумму по всем возможным неподвижным точкам.
b) Для вероятности p(n) о том, что случайно взятая перестановка порядка n не содержит неподвижных точек, используем соотношение:
p(n) = Q(n) / n!.
Согласно формуле для Q(n):
p(n) = (n! * Σ(k=0, n) ((-1)^k / k!)) / n! = Σ(k=0, n) ((-1)^k / k!).
Это выражение является рекуррентной формулой для вероятности, что перестановка не содержит неподвижных точек.
c) Вероятность p(n, k) того, что в случайной перестановке порядка n ровно k неподвижных точек можно найти следующим образом:
1. Выберем k неподвижных точек из n: C(n, k) = n! / (k! * (n - k)!).
2. Для оставшихся n - k элементов необходимо найти дерangements, т.е. Q(n - k).
3. Таким образом, вероятность p(n, k) можно выразить как:
p(n, k) = C(n, k) * Q(n - k) / n!.
Подставляем значения:
p(n, k) = (n! / (k! * (n - k)!)) * (Q(n - k)) / n!.
Таким образом, итоговая вероятность p(n, k):
p(n, k) = Q(n - k) / (k! * (n - k)!) для k неподвижных точек.
Ответ:
a) Q(n) = n! * Σ(k=0, n) ((-1)^k / k!).
b) Вероятность p(n) = Σ(k=0, n) ((-1)^k / k!).
c) Вероятность p(n, k) = Q(n - k) / (k! * (n - k)!).