Материал: Дискретная математика. Методичка. Кацаран

Положив далее

N

=

N

0

,

¯

N

=

N

( ¯

α

1

, . . . ,

¯

α

n

)

, из (3.5) получим равенство

¯

N

=

n

X

k

=0

(

−

1)

k

C

k

n

N

(

k

)

.

(3

.

7)

§ 9. Применение формулы включений и исключений

Рассмотрим множество чисел

{

1

,

2

, . . . , n

}

и найдем число

D

(

n

)

пе-

рестановок

(

a

i

1

, . . . , a

i

n

)

этих чисел, в которых ни одно из них не остается

на своем первоначальном месте

a

i

6

=

i

,

∀

i

= 1

, n

.

Обозначим через

α

i

свойство перестановки, заключающее в том,

что число

i

стоит на своем месте, а через

N

(

α

i

)

обозначим количество

перестановок, обладающих этим свойством.

Нетрудно заметить, что

N

(

α

i

) = (

n

−

1)!

,

∀

i

∈ {

1

, . . . , n

}

. Пусть

N

(

α

i

1

, . . . , α

i

k

)

— количество перестановок, в которых числа

α

i

1

, . . . , α

i

k

стоят на своих местах, тогда

N

(

α

i

1

, . . . , α

i

k

) = (

n

−

k

)!

.

Здесь мы имеем тот случай, когда величины

N

(

α

i

1

, . . . , α

i

k

)

не зависят

от характера свойств, а зависят только от их числа:

N

1

= (

n

−

1)!

, . . . , N

k

= (

n

−

k

)!

.

Число элементов

N

в рассматриваемом случае равно числу переста-

новок из

n

элементов:

N

=

N

0

=

n

!

. Подставляя найденные значения

для

N

k

,

k

= 0

, n

, а также выражения для

C

k

n

в формулу (3.7), получим

равенство

D

(

n

) =

n

!

n

X

k

=0

(

−

1)

k

k

!

.

(3

.

8)

В случае

n

= 3

из (3.8) находим, что число

D

(3)

перестановок, в кото-

рых числа

1

,

2

,

3

не стоят на своих местах, равно 2.

§ 10. Рекомендации к решению задач

При решении комбинаторных задач, в которых требуется опреде-

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

36

Добавим, что при решении задач комбинаторики можно пользо-

ваться терминологией:

элементы

(

объекты

),

из которых состоит

k

-

выборка, помещаются в

ячейки

.

Порядок заполнения

ячеек

мо-

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

Пример 1.

Сколько есть трехзначных чисел, делящихся на 4, в

записи которых не используются цифры 0, 4, 5, 6, 8, 9?

Решение.

Число делится на 4 тогда и только тогда, когда две по-

следние его цифры образуют число, делящееся на 4. В нашем случае это
числа 12, 32, 72. Для построения комбинации понадобятся две

ячей-

ки

: в первую можно поместить одну из цифр 1, 2, 3, 7; во вторую —

одну из ранее перечисленных двухзначных чисел. Первый объект можно
выбрать 4 способами, второй объект — 3 способами. По правилу произ-
ведения ответом на поставленный вопрос является число

4

·

3 = 12

.

Применяя правило произведения, следует обратить внимание на усло-

вие. Выбор каждого последующего элемента не должен зависеть от вы-
бора предыдущего. Следующий пример является иллюстрацией к этому
замечанию.

Пример 2.

Сколько есть шестизначных чисел, в каждом из которых

нет одинаковых цифр, а вторая и четвертая цифры нечетны?

Решение.

Очевидно, что надо взять шесть

ячеек

. Заполним эти

ячейки

. В первую

ячейку

поместим одну любую из 9 цифр (кроме

0

). Во вторую

ячейку

нужно поместить нечетную цифру. Так на-

пример, если на первое место мы поставили цифру 2, то на второе место
можно поставить одну из цифр

1

,

3

,

5

,

7

или

9

. Если

же на первом месте уже стоит цифра

9

, то на второе место можно

поставить только

1

,

3

,

5

или

7

. Указанный способ выбора

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

ячеек

: вторая, четвертая, первая, третья, пятая, шестая. Во вторую

поместить одну из 5 нечетных цифр, в четвертую — любую из 4 остав-
шихся нечетных цифр, в первую — одну из 7 (кроме

0

и тех двух, что

уже стоят, в третью — любую из 7 оставшихся, в пятую — любую из 6
оставшихся, в шестую — любую из 5 оставшихся. В результате получим

5

·

4

·

7

·

7

·

6

·

5 = 29 400

чисел, обладающих заданным свойством.

В некоторых случаях для того, чтобы найти число элементов конеч-

ного множества, обладающих требуемым свойством, удобно найти сна-
чала число элементов, не обладающих этим свойством, и затем вычесть
это число из общего числа элементов множества.

Пример 3.

Сколько есть пятизначных чисел, в записи которых есть

хотя бы одна четная цифра?

Решение.

Всего пятизначных чисел

9

·

10

·

10

·

10

·

10 = 90 000

, из них

37

5

·

5

·

5

·

5

·

5 = 3125

чисел, которые состоят только из нечетных цифр.

Поэтому количество требуемых чисел равно

86 875

.

Разберем типичные задачи на применение правила суммы и форму-

лы включений и исключений.

Пример 4.

Сколькими способами из

28

костей домино можно вы-

брать кость, на которой есть

1

или

6

?

Решение

. Выбрать кость, содержащую

1

, можно семью способа-

ми, содержащую

6

— тоже семью способами, но среди этих способов

есть один общий — это выбор кости

1 : 6

. В соответствии с пра-

вилом суммы общее число способов нужной кости можно осуществить

7 + 7

−

1 = 13

способами.

Пример 5.

Сколькими способами можно составить трехцветный

полосатый флаг, если имеется материал шести различных цветов?

Решение

. Нужно найти число 3-выборок из 6 элементов без повто-

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

A

3

6

=

6!

(6

−

3)!

= 6

·

5

·

4 = 120

(способов).

Данную задачу можно решить и другим способом. Для выбора цвета

первой полосы имеется 6 вариантов. После произведенного выбора цвет
для второй полосы можно выбрать 5 из оставшихся 5 способов. Далее
выбираем цвет для третьей полосы из 4 оставшихся — 4 способами. По
правилу произведения имеем:

6

·

5

·

4 = 120

способов.

Пример 6.

Сколько существует различных наборов длины 10 из

нулей и единиц?

Решение

. Так как набор состоит из десяти элементов, которые при-

нимают только два возможных значения

0

или

1

, то в этом наборе

будут присутствовать одинаковые значения элементов (т. е. элементы по-
вторяются). Следовательно, нужно найти число упорядоченных выборок
с повторениями:

e

A

10

2

= 2

10

= 1 024

(наборов)

.

Пример 7.

В магазине имеются в продаже мобильные телефоны

7 торговых марок. Сколькими способами можно купить: а) 5 аппаратов
разных торговых марок; б) 4 аппарата; в) 15 аппаратов?

Решение

. В случае а) нужно подсчитать число неупорядоченных 5-

выборок из 7 возможных без повторений (все телефонные аппараты раз-
ных торговых марок). Их число определяется по формуле:

C

5

7

=

7!

5!(7

−

5)!

=

6

·

7

1

·

2

= 21

(способ)

.

38

В случаях б) и в) нас интересуют неупорядоченные выборки из 7 эле-
ментов с повторениями длины 4 и 15 соответственно. Их значения опре-
деляются по формулам:

б)

H

4

7

=

C

4

7+4

−

1

=

10!

4!(10

−

4)!

=

10

·

9

·

8

·

7

2

·

3

·

4

= 210

(способов)

,

в)

H

15

7

=

C

15

7+15

−

1

=

21!

15!(21

−

15)!

= 54 264

(способа).

Пример 8.

Семь девушек водят хоровод. Сколькими различными

способами они могут встать в ряд?

Решение

. Если девушки стояли бы на месте, то получилось бы

7!

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

7!

/

7 = 6!

.

Пример 9.

В ходе экзаменационной сессии 1 студентов получили

оценки

отлично

, 12 —

хорошо

, 13 —

удовлетворительно

, 5 —

хорошо

и

отлично

, 7 —

хорошо

и

удовлетворительно

, 8 —

отлично

и

удовлетворительно

. У трех студентов все виды оценок.

Сколько студентов в группе, если известно, что все они сдали сессию?
Сколько отличников в группе? Сколько в группе чистых

троечников

?

Решение

. В условии задачи

n

1

= 12

,

n

2

= 12

,

n

3

= 13

,

n

12

= 5

,

n

13

= 8

,

n

23

= 7

,

n

123

= 3

. По формуле для правила суммы трех объек-

тов находим общее число студентов в группе:

12 + 12 + 13

−

5

−

8

−

7 + 3 = 20

;

число отличников в группе равно:

n

1

−

(

n

12

+

n

13

) +

n

123

= 12

−

(5 + 8) + 3 = 2

;

число чистых

троечников

равно:

n

3

−

(

n

13

+

n

23

) +

n

123

= 13

−

(8 + 7) + 3 = 1

.

Теперь рассмотрим комбинаторные задачи с

ограничениями на по-

рядок элементов

, когда на порядок элементов накладываются некоторые

дополнительные условия. В таких задачах удобно применять следующий
метод —

объединение нескольких одинаковых элементов в блоки

.

Затем рассмотрим задачи

на разбиения

, где требуется разделить эле-

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

метод введения перегородок

.

39

Пример 10.

Имеются предметы

k

сортов:

n

1

предметов одного

сорта,

n

2

предметов другого сорта,

. . .

,

n

k

предметов

k

-го сорта, где

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

Решение

. Из данных

k

сортов (блоков) можно сделать

P

(

k

) =

k

!

перестановок. Но еще можно переставить предметы внутри блоков

n

1

!

,

n

2

!

,

. . .

,

n

k

!

способами. Далее по правилу произведения имеем

n

1

!

·

n

2

!

·

. . .

·

n

k

!

·

k

!

перестановок.

Пример 11.

Сколькими способами можно переставить буквы слова

перелет

так, чтобы три буквы

е

не шли подряд?

Решение

. Объединим все буквы

е

в один блок

еее

. Число

перестановок, в которых все три буквы

е

идут подряд, равно чис-

лу перестановок из 5 объектов:

еее

,

п

,

р

,

л

,

т

, т. е.

P

(5) = 5! = 120

. Всего же перестановок с повторениями из букв дан-

ного слова можно составить

P

(3

,

1

,

1

,

1

,

1) =

3+1+1+1+1

3! 1! 1! 1! 1!

= 840

. Значит,

искомое число перестановок, где три буквы

е

не идут рядом, равно

N

= 840

−

120 = 720

.

Пример 12.

Сколькими способами можно расставить

m

нулей и

k

единиц, где

k

≤

m

+ 1

, так, чтобы никакие две единицы не стояли

рядом?

Решение

. Выпишем сначала

m

нулей. Для единиц получается

m

+1

место (одно место слева,

m

−

1

в промежутках между нулями и одно

справа). На любые из этих

m

+ 1

мест можно поставить одну из

k

еди-

ниц. Это можно осуществить

C

k

m

+1

способами. Если условие

k

≤

m

+ 1

не будет выполняться, то в результате расстановки две единицы в любом
случае будут стоять рядом.

Пример 13.

Найти число способов разбиения

n

одинаковых пред-

метов по

k

урнам (

n

и

k

— произвольные натуральные числа).

Решение

. Переименуем урны, расположив их в ряд. Между ними бу-

дет

(

k

−

1)

промежуток. Поставим в соответствии каждому разбиению

предметов по урнам последовательность из нулей и единиц следующим
образом: сначала последовательность имеет группу из

0

, число ко-

торых равно числу предметов в первой урне, затем ставим одну перего-
родку, обозначив ее за

1

; далее столько

0

, сколько предметов во

второй урне, и опять ставим

1

; затем столько

0

, сколько в тре-

тьей урне, и т. д., заканчивается последовательность группой

0

; их

столько, сколько предметов в последней урне. Следовательно, в такой
последовательности будет

n

нулей и

(

k

−

1)

единиц, всего

(

n

+

k

−

1)

цифр. Тогда число способов разбиения будет равно

C

k

−

1

n

+

k

−

1

.

40