Дискретная математика. Элементы теории задачи и упражнения. Булгакова И.Н - 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 ладьи, ферзя и короля) на первой линии шахматной доски? 
различных видов: чёрных n 1=5, белых n2=4 и красных n3 =3. Всего фишек
                                                        12 !
n=12. Следовательно, по формуле (7) имеем Р(5,4,3)=               = 27720 (спо-
                                                       5 ! 4 !3 !
собов).

      Замечание 1. Для решения данной задачи можно было применить
рассуждения, подобные выводу формулы для числа сочетаний: Занумеру-
ем чёрные фишки числами 1,2,3,4,5; белые - числами 6,7,8, 9; красные -
числами 10,11,12. Имеем всего 12 предметов, которые можно расположить
в ряд 12! способами. Но все расположения фишек не меняются при всех
перестановках фишек с номерами 1-5 (все они одного вида), с номерами 6-
9 и с номерами 10-12. Поэтому число различных расположений равно
 12 !
           .
5 ! 4 !3 !
         Замечание 2. Если п1 =к, n2=n-к, то имеем
                                                  k
                                 P(k,n-k)= C n .

      Циклические перестановки. Рассмотрим задачу: Семь девушек во-
дят хоровод. Сколькими различными способами они могут встать в круг?
      Решение. Если бы девушки стояли на месте, то получилось бы 7!
способов перестановок в ряду. Но так как они кружатся, то их положение
относительно окружающих предметов несущественно, а важно только их
взаимное расположение. Поэтому перестановки, переходящие друг в друга
при кружении (циклическом сдвиге), нужно считать одинаковыми. Так как
из каждой перестановки циклическим сдвигом можно получить ещё 6 но-
вых, то количество интересующих нас перестановок (7!) : 7=6!.
      Эту задачу можно обобщить так. Если рассматривать перестановки n
предметов, расположенных не в ряд, а по кругу, и считать одинаковыми
перестановки, переходящие друг в друга при вращении, то число различ-
ных перестановок (n-1)!.

      Подсчёт числа беспорядков. Это так называемая задача “о числе
беспорядков”. Число N перестановок из цифр {1, 2, …,n} таких, что ника-
кая цифра не остаётся на своём месте, можно найти по следующей форму-
ле:
                                        n
                                                  1
                                N =n! ∑ ( −1) k                                   (8)
                                       k =0       k!



ЗАДАЧИ И УПРАЖНЕНИЯ


33.Сколькими способами можно расставить белые фигуры (2 коня, 2 сло-
   на, 2 ладьи, ферзя и короля) на первой линии шахматной доски?

Страницы