Дано:
- n - количество объектов (чисел) в перестановке.
Найти:
- количество перестановок, в которых хотя бы одно из чисел стоит на своём месте.
Решение:
Обозначим:
- A_i - событие, при котором i-е число стоит на своём месте.
Мы ищем количество перестановок, в которых хотя бы одно число находится на своём месте. Это количество можно найти с помощью формулы включений-исключений.
Количество перестановок, в которых хотя бы одно число стоит на своём месте, можно вычислить по следующей формуле:
|U| - |A_1 ∪ A_2 ∪ ... ∪ A_n|
где |U| - общее количество перестановок из n объектов (n!).
Для вычисления |A_1 ∪ A_2 ∪ ... ∪ A_n| используем принцип включений-исключений:
|A_1 ∪ A_2 ∪ ... ∪ A_n| = Σ |A_i| - Σ |A_i ∩ A_j| + Σ |A_i ∩ A_j ∩ A_k| - ... + (-1)^(n+1) |A_1 ∩ A_2 ∩ ... ∩ A_n|
Теперь рассмотрим каждое из событий:
1. |A_i| - количество перестановок, в которых i-е число стоит на своём месте. При фиксированном i мы можем переставить остальные (n-1) объектов. Таким образом, |A_i| = (n-1)!.
2. |A_i ∩ A_j| - количество перестановок, в которых i-е и j-е числа стоят на своих местах. При фиксированных i и j мы можем переставить (n-2) оставшихся объектов. Следовательно, |A_i ∩ A_j| = (n-2)!.
3. Аналогично, |A_i ∩ A_j ∩ A_k| = (n-3)! и так далее.
Поэтому можно выразить |A_1 ∪ A_2 ∪ ... ∪ A_n| через суммы:
|A_1 ∪ A_2 ∪ ... ∪ A_n| = C(n, 1)(n-1)! - C(n, 2)(n-2)! + C(n, 3)(n-3)! - ... + (-1)^(n)C(n, n)(0!)
где C(n, k) - биномиальные коэффициенты, равные n!/(k!(n-k)!).
Общее количество перестановок (n!) можно выразить как:
|U| = n!
Теперь подставим все это в формулу:
Количество перестановок, где хотя бы одно число стоит на своём месте:
n! - (C(n, 1)(n-1)! - C(n, 2)(n-2)! + C(n, 3)(n-3)! - ... + (-1)^(n)C(n, n)(0!))
Суммируя, мы получаем:
Количество перестановок, где хотя бы одно число стоит на своём месте = n! - (n!(1/1! - 1/2! + 1/3! - ... + (-1)^n/n!))
Итак, число перестановок, где хотя бы одно число стоит на своём месте:
n! * (1 - (1/1! - 1/2! + 1/3! - ... + (-1)^n/n!))
Ответ:
Количество перестановок, где хотя бы одно из чисел стоит на своём месте, равно n! * (1 - 1/e), где e - основание натурального логарифма.