Дискретная математика. Элементы теории, задачи и упражнения. Часть 1. Булгакова И.Н. - 40 стр.

UptoLike

Составители: 

40
Решение. Эта задача на перестановки с повторениями. Имеем фишки
3-х различных видов: чёрных n
1
= 5, белых n
2
= 4 и красных n
3
= 3. Всего фи-
шек n = 12. Следовательно, по формуле (7) имеем Р(5,4,3) =
!
3
!
4
!
5
!12
= 27 720
(способов).
Замечание 1. Для решения данной задачи можно было применить
рассуждения, подобные выводу формулы для числа сочетаний: Занумеру-
ем чёрные фишки числами 1, 2, 3, 4, 5; белые числами 6, 7, 8, 9; крас-
ные числами 10, 11, 12. Имеем всего 12 предметов, которые можно рас-
положить в ряд 12! способами. Но все расположения фишек не меняются
при всех перестановках фишек с номерами 15 (все они одного вида), с но-
мерами 6–9 и с номерами 10–12. Поэтому число различных расположений
равно
!
3
!
4
!
5
!12
.
Замечание 2. Если п
1
= k, n
2
= n k, то имеем
P(k,n k) =
.
k
n
C
Циклические перестановки. Рассмотрим задачу: Семь девушек во-
дят хоровод. Сколькими различными способами они могут встать в круг?
Решение. Если бы девушки стояли на месте, то получилось бы 7!
способов перестановок в ряду. Но так как они кружатся, то их положение
относительно окружающих предметов несущественно, а важно только их
взаимное расположение. Поэтому перестановки, переходящие друг в друга
при кружении (циклическом сдвиге), нужно считать одинаковыми. Так как
из каждой перестановки циклическим сдвигом можно получить ещё 6 но-
вых, то количество интересующих нас перестановок (7!) : 7 = 6!.
Эту задачу можно обобщить так. Если рассматривать перестановки n
предметов, расположенных не в ряд, а по кругу, и считать одинаковыми
перестановки, переходящие друг в друга при вращении, то число различ-
ных перестановок (n1)!.
Подсчёт числа беспорядков. Это так называемая задача «о числе
беспорядков». Число N перестановок из цифр {1, 2, , n} таких, что ни-
какая цифра не остаётся на своём месте, можно найти по следующей фор-
муле:
N = n!
å
=
-
n
k
k
k
0
!
1
)1(
. (8)