Компьютерная математика: Часть 1. Теория множеств и комбинаторика. Волченская Т.В - 69 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

69
N(a
1
a
3
) = . . ; N(a
2
a
3
) =. . . ; N(a
1
a
2
a
3
) =. . . ; N = 32.
N(a
1
’a
2
’a
3
’) = N – N(a
1
) – N(a
2
) – N(a
3
) + N(a
1
a
2
) +
+ N(a
1
a
3
) + N(a
2
a
3
) – N(a
1
a
2
a
3
) = . . . . .
Ответ: . . . . . . . . . .
3.8. Комбинаторные задачи с ограничениями
3.8.1. Задачи с ограничением на порядок
До сих пор мы рассматривали задачи, в которых на порядок элемен-
тов в комбинациях не накладывалось никаких ограничений или дополни-
тельных условий. Либо (как в сочетаниях) порядок вообще не учитывался.
Рассмотрим задачи с ограничением.
Задача 1. Укротитель хищных зверей хочет вывести на арену 5 львов
и 4 тигра, при этом нельзя, чтобы два
тигра шли друг за другом. Сколькими
способами он может расположить зверей?
Обозначим львов буквой Л. Для тигров имеется 6 мест.
_____Л
1
_____Л
2
_____Л
3
____Л
4
_____Л
5
______
Львов можно расположить 5! способами, т. е. 120. На шести местах для
тигров их можно расположить А
4
6
= 6×5×4×3 = 360 способами.
Общее число способов 120
×360 = 43200.
Для задачи в общем виде, если имеется k тигров и n львов.
P
n
A
k
n+1
= n!(n+1)n(n-1) ×.....× (n–k), но так как A
k
n
= P
k
C
k
n
, то
n!k!(n+1)! n!(n+1)!
P
n
P
k
C
k
n+1
= = .
k!(n+1–k)! (n–k+1)!
Это возможно лишь при условии, что n – k + 1
≥ 0, или
k
≤ n + 1.
Задача 2. Строится лестница из точки А в точку В. Расстояние АС =
4,5 м, ВС = 1,5 м. Высота ступеньки 0,3 м, ши-
рина – 0,5 м или кратное 0,5 (рис. 57). Скольки-
ми способами можно построить лестницу?
Из условия видно, что лестница должна
иметь 1,5/0,3 =5 ступеней, при этом имеется 10
мест, где можно устроить ступеньку: 4,5/0,5 = 9
ступеней и одна крайняя
.
Следовательно, надо выбрать 5 мест для
Рис. 57 
     N(a1a3) = . . ;        N(a2a3) =. . . ;  N(a1a2a3) =. . . ;   N = 32.
     N(a1’a2’a3’) = N – N(a1) – N(a2) – N(a3) + N(a1a2) +
     + N(a1a3) + N(a2a3) – N(a1a2a3) = . . . . .
     Ответ: . . . . . . . . . .

         3.8. Комбинаторные задачи с ограничениями
               3.8.1. Задачи с ограничением на порядок
       До сих пор мы рассматривали задачи, в которых на порядок элемен-
тов в комбинациях не накладывалось никаких ограничений или дополни-
тельных условий. Либо (как в сочетаниях) порядок вообще не учитывался.
Рассмотрим задачи с ограничением.
       Задача 1. Укротитель хищных зверей хочет вывести на арену 5 львов
и 4 тигра, при этом нельзя, чтобы два тигра шли друг за другом. Сколькими
способами он может расположить зверей?
       Обозначим львов буквой Л. Для тигров имеется 6 мест.
       _____Л1_____Л2_____Л3____Л4_____Л5______
       Львов можно расположить 5! способами, т. е. 120. На шести местах для
тигров их можно расположить А46 = 6×5×4×3 = 360 способами.
       Общее число способов 120×360 = 43200.
       Для задачи в общем виде, если имеется k тигров и n львов.
       PnAkn+1 = n!(n+1)n(n-1) ×.....× (n–k), но так как Akn = PkCkn, то
                    n!k!(n+1)!      n!(n+1)!
             k
       PnPkC n+1=            =            .
                     k!(n+1–k)! (n–k+1)!
       Это возможно лишь при условии, что n – k + 1 ≥ 0, или
 k ≤ n + 1.

     Задача 2. Строится лестница из точки А в точку В. Расстояние АС =
                         4,5 м, ВС = 1,5 м. Высота ступеньки 0,3 м, ши-
                         рина – 0,5 м или кратное 0,5 (рис. 57). Скольки-
                         ми способами можно построить лестницу?
                               Из условия видно, что лестница должна
                         иметь 1,5/0,3 =5 ступеней, при этом имеется 10
                         мест, где можно устроить ступеньку: 4,5/0,5 = 9
                         ступеней и одна крайняя.
         Рис. 57
                               Следовательно, надо выбрать 5 мест для

                                        69

Страницы