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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

51
Задача 1. Сколькими способами можно разместить на плате 4 элемен-
та? P
4
= 4! = 24 .
Задача 2. Сколькими способами можно выстроить в линейку 10 чело-
век (5 девушек и 5 юношей) с условием, чтобы девушки и юноши чередова-
лись? 5 девушек можно разместить 5! способами, а 5 юношей аналогично
5!. Следовательно, всего способов (5!)
2
= = (120)
2
= 14400 .
3.2.1. Перестановка с повторением
Если рассматривать упорядоченные k-элементные наборы из множе-
ства М, которые состоят не только из различных элементов множества М,
но содержат некоторые повторяющиеся элементы, то получим перестанов-
ки с повторением.
Пусть М = {S
1
, S
2
, ..... S
n
} – множество из n элементов и i
1
, i
2
, ......i
n
–
натуральные числа, такие, что их сумма равна k,а k > n.
Каждый упорядоченный набор k элементов
⎯P
k
содержащий элемент
S
j
равно i
j
раз (1≤ j ≤ n) называется перестановками множества М с повто-
рением:
⎯
k
Р
~
=
!!......ii!i
k!
n
1
2
.
Примечание: при i
1
= i
2
=.......i
n
=1 получим перестановки множества из n элемен-
тов без повторений.
Пример. Сколько различных шестизначных чисел можно составить из
цифр 1, 1, 1, 5, 5, 9? Подставим в формулу
⎯P
6
= 6! / (3! 2! 1!)= 4×5×6 = 120
различных шестизначных чисел.
Задача 2. Сколько различных слов можно получить, переставляя бук-
вы слова «математика»?
Р
~
10
= 10! / (2! 3! 2!) = 151200.
3.2.2. Перестановки предметов, расположенных в круг
Задача 1. «Хоровод». Семь девушек водят хоровод. Сколькими раз-
личными способами они могут встать в круг (рис. 49,а)?
Если бы они стояли на месте, то количество способов – 7! = = 5040.
Но так как танцующие кружатся, то их положение относительно окружаю-
щих не имеет роли, следовательно, важно лишь взаимное расположение.
Поэтому перестановки, переходящие друг в друга, надо считать одинако-
выми. Но из каждой перестановки можно получить еще 6 путем вращения –
7 мест: 5040 : 7 = = 720 различных перестановок девушек в хороводе. 
      Задача 1. Сколькими способами можно разместить на плате 4 элемен-
та? P4 = 4! = 24 .
      Задача 2. Сколькими способами можно выстроить в линейку 10 чело-
век (5 девушек и 5 юношей) с условием, чтобы девушки и юноши чередова-
лись? 5 девушек можно разместить 5! способами, а 5 юношей аналогично
5!. Следовательно, всего способов (5!)2 = = (120)2 = 14400 .

                     3.2.1. Перестановка с повторением
      Если рассматривать упорядоченные k-элементные наборы из множе-
ства М, которые состоят не только из различных элементов множества М,
но содержат некоторые повторяющиеся элементы, то получим перестанов-
ки с повторением.
      Пусть М = {S1, S2, ..... Sn} – множество из n элементов и i1, i2, ......in –
натуральные числа, такие, что их сумма равна k,а k > n.
      Каждый упорядоченный набор k элементов⎯Pk содержащий элемент
Sj равно ij раз (1≤ j ≤ n) называется перестановками множества М с повто-
рением:
                        ~ =
                       ⎯Р
                                     k!         .
                          k
                              i1! i2!......i n!
       Примечание: при i1 = i2 =.......in =1 получим перестановки множества из n элемен-
тов без повторений.
     Пример. Сколько различных шестизначных чисел можно составить из
цифр 1, 1, 1, 5, 5, 9? Подставим в формулу ⎯P6 = 6! / (3! 2! 1!)= 4×5×6 = 120
различных шестизначных чисел.
     Задача 2. Сколько различных слов можно получить, переставляя бук-
вы слова «математика»?
                             ~ 10 = 10! / (2! 3! 2!) = 151200.
                             Р

            3.2.2. Перестановки предметов, расположенных в круг

      Задача 1. «Хоровод». Семь девушек водят хоровод. Сколькими раз-
личными способами они могут встать в круг (рис. 49,а)?
      Если бы они стояли на месте, то количество способов – 7! = = 5040.
Но так как танцующие кружатся, то их положение относительно окружаю-
щих не имеет роли, следовательно, важно лишь взаимное расположение.
Поэтому перестановки, переходящие друг в друга, надо считать одинако-
выми. Но из каждой перестановки можно получить еще 6 путем вращения –
7 мест: 5040 : 7 = = 720 различных перестановок девушек в хороводе.


                                         51

Страницы