ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 16651
Скачиваний: 202
36
4.
Буквенно-цифровой код составляют следующим образом:
сначала в некотором порядке записывают четыре буквы а, b, c, d,
затем справа приписывают также в некотором порядке три цифры 1,
2, 3. Сколько всего существует таких кодов?
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
2.6 Перестановки с повторениями
Постановка задачи. Последовательность состоит из n элементов. В ней
содержится n
1
неразличимых между собой элементов вида а, n
2
элементов вида
b, …, n
k
элементов вида x. Очевидно, что
n = n
1
+ n
2
+ … + n
k
.
Одна из последовательностей, содержащая n элементов, имеет вид
1
2
...
...
...
...
.
элементов
элементов
элементов
k
a
a
a
a
b
b
b
b
x
x
x
x
n
n
n
Если некоторые буквы переставить местами, то получится другая после-
довательность. Сколько существует таких последовательностей, которые отли-
чаются одна от другой только порядком расположения элементов?
Число последовательностей равно n!, если все n элементов считать раз-
личными. Но среди них n
1
! перестановок неразличимы. Они состоят из повто-
ров буквы a. Неразличимы и n
2
! перестановок. В них входит только буква b.
И так далее до буквы x. Следовательно,
1
2
1
2
1
2
(
...
)!
!
,
! ! ...
!
! ! ...
!
k
n
k
k
n
n
n
n
Р
n n
n
n n
n
+
+ +
=
=
ɺ
(2.4)
где точка над знаком Р
n
обозначает перестановки с повторениями, то есть гово-
рит о том, что в перестановках есть повторяющиеся элементы.
· · · · · · · · · · · · · · · · · · · · · · ·
Пример 2.14
· · · · · · · · · · · · · · · · · · · · · ·
Сколько пятибуквенных слов можно составить из двух букв а и б, если в
каждом слове содержится точно три буквы а?
По условию: n
1
= 3, n
2
= 2, n = 5. Искомое число находим по форму-
ле (2.4):
5
5!
10.
3! 2!
=
=
⋅
ɺ
P
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
37
· · · · · · · · · · · · · · · · · · · · · · ·
Пример 2.15
· · · · · · · · · · · · · · · · · · · · · ·
Сколько различных слов можно составить, переставляя буквы слова обо-
роноспособность?
В этом слове 18 букв. Из них семь букв о, две буквы б, одна буква р, две
буквы н, одна буква п, три буквы с, одна буква т и один мягкий знак. Следова-
тельно,
n = 18, n
1
= 7, n
2
= 2, n
3
= 1, n
4
= 2, n
5
= 1, n
6
= 3, n
7
= 1, n
8
= 1.
Искомое число различных слов равно:
11
18
18!
1,03 10 .
7! 2! 1! 2! 1! 3! 1! 1!
P
=
≈
⋅
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅
ɺ
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Упражнения
1.
Сколько существует 10-значных двоичных чисел, в каждом
из которых единиц столько же, сколько и нулей? Числа могут начи-
наться с нуля.
2.
Сколько существует 10-значных двоичных чисел, в каждом
из которых единиц столько же, сколько и нулей, но числа с нуля
начинаться не могут.
3.
Сколько существует 6-значных троичных чисел, в которых
нет нулей?
4.
В 11-значном числе 4 двойки, 3 тройки, 1 четверка, 3 пя-
терки. Сколько существует таких чисел, которые могут быть обра-
зованы перестановкой этих цифр, если каждое число начинается с
последовательности 334 и оканчивается тремя двойками?
5.
Сколько новых слов можно получить путём перестановки
гласных букв в заданном слове из нижеприведённых, если все со-
гласные буквы остаются на своих местах без изменений (букву «й»
гласной не считать)?
а. Водопроводчик.
в. Авиационный.
д. Змееед.
б. Громоотвод.
г. Перестановочный.
е. Треска.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
38
2.7 Размещения без повторений
Постановка задачи. Множество А содержит n элементов. Из него пооче-
рёдно выбирают по одному элементу и образуют упорядоченную последова-
тельность длины m, где m ≤ n. Сколько существует таких последовательностей?
Так как элементы выбираются из множества, где нет повторов, то элемен-
ты в каждой из последовательностей не могут встречаться более одного раза.
Такие последовательности называют размещениями без повторений.
Очевидно, что размещения могут отличаться одно от другого не только
элементами, но и порядком записи элементов. Например, размещения 365 и
346, составленные из элементов множества
A = {1, 2, 3, 4, 5, 6},
(2.5)
являются различными, поскольку отличаются одно от другого наборами цифр.
Размещения той же длины 356 и 365, хотя и состоят из одних и тех же элемен-
тов множества А, но отличаются одно от другого порядком записи цифр, по-
этому также различны.
· · · · · · · · · · · · · · · · · · · · · · ·
Пример 2.16
· · · · · · · · · · · · · · · · · · · · · ·
Сколько существует размещений длины 3, которые можно составить из
элементов множества (2.5)?
Так как размещения – это упорядоченные последовательности, то для
нахождения их количества можно воспользоваться правилом произведения.
Первый элемент выбираем шестью способами. Останется пять элементов. Для
выбора второго элемента существует 5 способов, для третьего – 4. Искомое
число размещений равно: 6·5·4 = 120.
Выведем формулу числа размещений без повторений для общего случая.
Если множество содержит n элементов, то согласно правилу произведения пер-
вый элемент можно выбрать n способами, второй после него – n – 1 способами,
третий – n – 2 способами и так далее до элемента m, который можно выбрать
n – m + 1 способами. Следовательно,
m
n
A
= n(n – 1)(n – 2)…(n – m +1),
(2.6)
где
m
n
A
– число размещений из n элементов по m без повторений.
Умножим и разделим выражение (2.6) на (n – m)!:
(
1)(
2)...(
1) (
)!
(
)!
−
−
− + ⋅
−
=
=
−
m
n
n n
n
n
m
n
m
A
n
m
39
(
1)(
2) ... (
1)(
)(
1) ... 3 2 1
.
(
)!
−
−
− +
−
− −
⋅ ⋅
=
−
n n
n
n
m
n
m n
m
n
m
Числитель последней формулы представляет собой произведение нату-
ральных чисел от 1 до n без повторов и без пропусков сомножителей, следова-
тельно, формулу для числа размещений без повторений можно записать в виде:
!
.
(
)!
=
−
m
n
n
A
n
m
(2.7)
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
· · · · · · · · · · · · · · · · · · · · · · ·
Пример 2.17
· · · · · · · · · · · · · · · · · · · · · ·
Сколько существует трёхзначных десятичных чисел, в каждом из кото-
рых нет повторов цифр? С нуля числа не начинаются.
По правилу произведения: первую цифру можно выбрать из девяти цифр
(так как нулю запрещено занимать место старшего разряда), вторую – также из
девяти (поскольку нуль возвращён), третью – из восьми. Следовательно, иско-
мое число N равно:
N = 9·9·8 = 648.
С применением формулы для числа размещений эту задачу решим при
условии, что существует один элемент, с которого не должно начинаться ни
одно размещение. Запишем искомое число N в виде
1
1
,
−
−
=
−
m
m
n
n
N
А
A
(2.8)
где
m
n
А
– число всех возможных m-элементных размещений. Сюда входят и
те размещения, которые начинаются с отмеченного элемента;
1
1
−
−
m
n
А
– число только тех размещений, которые начинаются с отмеченного
элемента.
Запишем формулу (2.8) в развёрнутом виде:
!
(
1)!
(
1)!
(
1)!
.
(
)! [
1 (
1)]! (
)! (
)!
−
−
−
=
−
=
−
−
− −
−
−
−
n
n
n n
n
N
n
m
n
m
n
m
n
m
Выражение
)!
(
)!
1
(
m
n
n
−
−
вынесем за скобки:
(
1)! (
1)
.
(
)!
n
n
N
n
m
− ⋅
−
=
−
(2.9)
40
Возвращаемся к заданному примеру. По формуле (2.9) находим число
размещений при n = 10, m = 3:
(10 1)! (10 1) 1 2 3 4 5 6 7 8 9 9
648.
(10 3)!
1 2 3 4 5 6 7
N
− ⋅
−
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅
=
=
=
−
⋅ ⋅ ⋅ ⋅ ⋅ ⋅
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
· · · · · · · · · · · · · · · · · · · · · · ·
Пример 2.18
· · · · · · · · · · · · · · · · · · · · · ·
Сколько существует двухразрядных восьмеричных чисел, в которых нет
четных цифр и нет повторов? Привести список этих чисел. (Это пример задачи
на пересчёт и перечисление согласно [33].)
Искомые числа состоят только из нечётных цифр. В восьмеричной систе-
ме нечётными являются цифры: 1, 3, 5, 7. Согласно условию, n = 4, m = 2. По
формуле (2.7) определяем количество искомых чисел:
2
4
4!
1 2 3 4
12.
(4 2)!
1 2
⋅ ⋅ ⋅
=
=
=
−
⋅
A
Список искомых чисел имеет вид: 13, 15, 17, 31, 35, 37, 51, 53, 57, 71, 73,
75.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
· · · · · · · · · · · · · · · · · · · · · · ·
Пример 2.19
· · · · · · · · · · · · · · · · · · · · · ·
В библиотеке имеется по одному экземпляру 10 книг о приключениях.
Четырём читателям предлагается выбор. Каждый читатель может выбрать
только одну книгу. Сколько всего существует способов выбора книг этими че-
тырьмя читателями?
Пронумеруем книги: 0, 1, 2, 3, …, 9 и переформулируем задачу: сколько
существует четырехразрядных чисел, которые могут быть образованы из
10 цифр (без повторов), при условии, что числа могут начинаться с нуля?
Согласно новому условию,
n = 10, m = 4,
тогда искомое число способов распределения 10 книг между четырьмя читате-
лями равно:
4
10
10!
10!
7 8 9 10 5040.
(10 4)!
6!
=
=
= ⋅ ⋅ ⋅
=
−
A
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·