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

UptoLike

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

34
рактера) выборок упорядоченные это выборки или нет, с повторениями
или без повторений.
Комбинациям, которые встречаются в этих задачах, присвоены осо-
бые названия размещения, сочетания и перестановки.
Размещения без повторений и с повторениями
Размещениями без повторений из п элементов по k называются
упорядоченные k-выборки из п элементов без повторений. Их число
обозначается
k
n
A
и вычисляется по формуле :
k
n
A
= n
´
(n 1)
´
(n 2)
´
´
(n k + 1) =
)!(
!
kn
n
-
, k
£
n. (2)
Обычно размещения без повторений из n элементов по n называются
перестановками из n элементов. Их число обозначается P
n
и вычисляется
по формуле:
P
n
=
n
n
A
= n! (3)
Пример 7. Сколькими способами можно составить трехцветный по-
лосатый флаг, если имеется материал пяти различных цветов?
Решение. Нужно найти число 3-выборок из 5 элементов без повто-
рений (все цвета различны); порядок, в котором располагаются выбранные
цвета, существенен. Следовательно, нужно найти число упорядоченных
выборок, т.е. число размещений из 5 по 3 без повторений. По формуле
(2) имеем
3
5
A
=
)!35(
!5
-
= 5
´
4
´
3 = 60 (способов).
Заметим, что эту задачу можно решить иначе. Для выбора цвета пер-
вой полосы имеется 5 вариантов. После произведенного выбора цвет для
второй полосы можно выбрать 4-мя способами из 4-х оставшихся. Далее
выбираем цвет для третьей полосы флага из имеющихся 3-х цветов. Это
можно сделать 3-мя способами. По правилу произведения всего имеем
5
´
4
´
3 = 60 (способов).
Пример 8. Та же задача из примера 7, но среди полос одна обяза-
тельно должна быть красной.
Решение. Красную полосу можно расположить 3-мя способами, т. к.
флаг трехполосный. После выбора красной полосы, остался материал 4-х
цветов, из которых нужно выбрать два цвета. Этот выбор можно осуществить
2
4
A
=
!
2
!4
= 4
´
3 = 12 (способами) , так как 2-выборки упорядоченные
без повторений. По правилу произведения окончательно имеем 3
´
2
4
A
= 36
(способов).
рактера) выборок – упорядоченные это выборки или нет, с повторениями
или без повторений.
     Комбинациям, которые встречаются в этих задачах, присвоены осо-
бые названия – размещения, сочетания и перестановки.

               Размещения без повторений и с повторениями

     Размещениями без повторений из п элементов по k называются
упорядоченные k-выборки из п элементов без повторений. Их число
обозначается    A nk   и вычисляется по формуле :
          A nk = n � (n – 1) � (n – 2) � … � (n – k + 1) =      n!
                                                                       , k � n.   (2)
                                                             (n � k )!
     Обычно размещения без повторений из n элементов по n называются
перестановками из n элементов. Их число обозначается Pn и вычисляется
по формуле:
                                     Pn =   Ann = n!                              (3)

      Пример 7. Сколькими способами можно составить трехцветный по-
лосатый флаг, если имеется материал пяти различных цветов?
      Решение. Нужно найти число 3-выборок из 5 элементов без повто-
рений (все цвета различны); порядок, в котором располагаются выбранные
цвета, существенен. Следовательно, нужно найти число упорядоченных
выборок, т.е. число размещений из 5 по 3 без повторений. По формуле
(2) имеем
                        A53 =      5!
                                         = 5 � 4 � 3 = 60 (способов).
                                (5 � 3)!
     Заметим, что эту задачу можно решить иначе. Для выбора цвета пер-
вой полосы имеется 5 вариантов. После произведенного выбора цвет для
второй полосы можно выбрать 4-мя способами из 4-х оставшихся. Далее
выбираем цвет для третьей полосы флага из имеющихся 3-х цветов. Это
можно сделать 3-мя способами. По правилу произведения всего имеем
                           5 � 4 � 3 = 60 (способов).
     Пример 8. Та же задача из примера 7, но среди полос одна обяза-
тельно должна быть красной.
     Решение. Красную полосу можно расположить 3-мя способами, т. к.
флаг трехполосный. После выбора красной полосы, остался материал 4-х
цветов, из которых нужно выбрать два цвета. Этот выбор можно осуществить
              4!
      A42 =      = 4 � 3 = 12 (способами) , так как 2-выборки упорядоченные
              2!
                                                                2
без повторений. По правилу произведения окончательно имеем 3 � A4 = 36
(способов).

                                            34