Дискретная математика. Комбинаторика. Ерош И.Л. - 6 стр.

UptoLike

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

Рубрика:

3. Время работы агрегата в сутки задается часами, минутами и се-

кундами. Сколько разных временных интервалов может быть задано

для работы агрегата? (86400)

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

Рассмотрим задачу: Сколько разных 5-разрядных чисел можно за-

писать с помощью десяти цифр при условии, что в числах не использу-

ются одинаковые цифры?

Перенумеруем разряды:

1 2 3 4 5

В первый разряд можно поставить одну из 10 цифр (0, 1, 2, 3, 4, 5, 6, 7,

8, 9). Независимо от того, какая цифра помещена в первый разряд, во

втором можно поставить только одну из 9 цифр, в третий – одну из 8

цифр и т. д. Всего существует 10 ⋅ 9 ⋅ 8 ⋅ 7 ⋅ 6 = 30240 различных пятираз-

рядных чисел, в каждом из которых нет двух одинаковых цифр.

В общем случае, если имеется k позиций и n разных предметов, при-

чем каждый представлен в единственном экземпляре, то количество

разных расстановок:

A = n(n – 1)(n – 2)...(n – k+1) = n!/(n – k)! ( 3 )

В формуле (3) s! означает факториал числа s, т. е. произведение

всех чисел от 1 до s. Таким образом, s! = 1 ⋅ 2 ⋅ 3 ⋅ …s.

П р и м е р. Из группы в 25 человек требуется выбрать старосту,

заместителя старосты и профорга. Сколько вариантов выбора руко-

водящего состава группы? Старосту выбрать можно одним из 25

способов. Поскольку выбранный староста не может быть своим за-

местителем, то для выбора заместителя старосты остается 24 ва-

рианта. Профорга выбирают одним из 23 способов. Всего вариан-

тов: 25 ⋅ 24 ⋅ 23 = 25!/22! = 13800.

Упражнения

1. Из коллектива работников в 25 человек нужно выбрать председа-

теля, заместителя, бухгалтера и казначея. Каким количеством спосо-

бов это можно сделать? (25 ⋅ 24 ⋅ 23 ⋅ 22 = 25!/(25 – 4)! = 303600)

2. В парламент нового независимого государства нужно предста-

вить для рассмотрения варианты флагов (для определенности – три