Составители:
Рубрика:
17
При произвольном n имеем:
N(
n
) = N –
1
n
C
⋅ N(1) +
2
n
C
⋅ N(2) – ... + ( – 1)
n
⋅ N(n)
В последнем примере предыдущего параграфа мы использовали этот
частный случай главной теоремы комбинаторики. В общем случае при
перестановке n предметов количество расстановок, при которых ни один
предмет не находится на своем месте:
N(
n
) = n! –
1
n
C
⋅ (n – 1 )! +
2
n
C
⋅ (n – 2)!
– ... + ( – 1)
n
⋅ 0! = D
n
(10)
Полученное значение D
n.
иногда называют формулой полного беспо-
рядка или субфакториалом. Субфакториал D
n
можно представить и так:
()
1
111
! 1 ...
1! 2! 3! !
n
n
Dn
n
−
=−+−++
,
где выражение в [...] стремится к e
–1
при неограниченном возраста-
нии n.
Субфакториал имеет свойства, похожие на свойства обычного фак-
ториала. Например,
n! = (n–1)[(n–1)! + (n–2)!] – для обычного факториала,
D
n
= (n–1)[D
n–1
+D
n–2
] – для субфакториала.
Субфакториалы легко вычисляются по формуле
D
n
= nD
n–1
+ (–1)
n
.
Приведем некоторые начальные значения субфакториалов:
n 1 2 3 4 5 6 7 8 9
D
n
0 1 2 9 44 255 1784 14273 128456
Упражнения
1. Вычислите значения субфакториалов для n = 10, 11, 12.
2. Имеется 6 различных предметов. В каком числе перестановок
ровно 2 предмета остаются на своих местах, а остальные на чужих?
3. Имеется 10 разных предметов, расставленных в линию. Благо-
приятной перестановкой будем считать такую, при которой точно 4 лю-
бых предмета будут стоять на своих местах (а остальные – на чужих).
Сколько существует таких расстановок? Во сколько раз изменится чис-
ло благоприятных комбинаций, если на своих местах будут стоять 6
предметов?
Страницы
- « первая
- ‹ предыдущая
- …
- 15
- 16
- 17
- 18
- 19
- …
- следующая ›
- последняя »
