Дискретная математика. Элементы теории, задачи и упражнения. Часть 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! способами. Но все расположения фишек не меняются
при всех перестановках фишек с номерами 1–5 (все они одного вида), с но-
мерами 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
предметов, расположенных не в ряд, а по кругу, и считать одинаковыми
перестановки, переходящие друг в друга при вращении, то число различ-
ных перестановок (n–1)!.
Подсчёт числа беспорядков. Это так называемая задача «о числе
беспорядков». Число N перестановок из цифр {1, 2, …, n} таких, что ни-
какая цифра не остаётся на своём месте, можно найти по следующей фор-
муле:
N = n!
å
=
-
n
k
k
k
0
!
1
)1(
. (8) 
      Решение. Эта задача на перестановки с повторениями. Имеем фишки
3-х различных видов: чёрных n1 = 5, белых n2 = 4 и красных n3 = 3. Всего фи-
                                                              12 !
шек n = 12. Следовательно, по формуле (7) имеем Р(5,4,3) =              = 27 720
                                                             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 = k, n2 = n – k, то имеем
                                                  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!




                                       40

Страницы