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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

32
4
при k=4.
9. Из множества A = {a, b, c, d} составить:
а ) упорядоченные 2-выборки без повторений;
б) неупорядоченные 2-выборки без повторений.
Сколько их всего может быть?
Ответ : а ) 12; б) 6.
При решении комбинаторных задач, в которых требуется определить
количество некоторых выборок (комбинаций) из данного множества эле-
ментов, основным моментом является правильное определение типа (ха -
рактера ) выборок — упорядоченные это выборки или нет , с повторениями
или без повторений.
Комбинациям , которые встречаются в этих задачах, присвоены осо-
бые названия — размещения, сочетания и перестановки.
Размещения без повторений и с повторениями
Размещениями без повторений из п элементов по к называются
упорядоченные 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 (способов).
Заметим, что эту задачу можно решить иначе. Для выбора цвета пер-
                                             32 4 при k=4.

9. Из множества A = {a, b, c, d} составить:
        а) упорядоченные 2-выборки без повторений;
        б) неупорядоченные 2-выборки без повторений.
Сколько их всего может быть?
                                 Ответ: а) 12; б) 6.


      При решении комбинаторных задач, в которых требуется определить
количество некоторых выборок (комбинаций) из данного множества эле-
ментов, основным моментом является правильное определение типа (ха-
рактера) выборок — упорядоченные это выборки или нет, с повторениями
или без повторений.
     Комбинациям, которые встречаются в этих задачах, присвоены осо-
бые названия — размещения, сочетания и перестановки.



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


     Размещениями без повторений из п элементов по к называются
упорядоченные 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)
имеем
                      A 53 =      5!
                                       =5 ×4 ×3 = 60 (способов).
                               (5 −3)!
      Заметим, что эту задачу можно решить иначе. Для выбора цвета пер-

Страницы