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

UptoLike

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