Лекция

Тема: «Комбинаторные задачи»

Перечень вопросов, рассматриваемых в теме:

1.

Элементы комбинаторики – комбинации без повторений

1.1. Размещения

1.2. Перестановки

1.3. Сочетания

2. Основные правила комбинаторики

2.1. Правило суммы

2.2. Правило умножения

3. Элементы комбинаторики – комбинации с повторениями

3.1. Размещение с повторениями

3.2. Сочетание с повторениями

3.3. Перестановки с повторениями

4. Примеры и разбор решения заданий тренировочного модуля

1. Элементы комбинаторики – комбинации без повторений

Комбинаторными задачами называются задачи, в которых необходимо подсчитать,

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

1.1. Размещения. Пусть имеется множество, содержащее n элементов. Каждое его

упорядоченное подмножество, состоящее из m элементов, называется размещением из n

элементов по m элементов:

𝑨

𝒏

𝒎

=

𝒏

!

(

−

𝒏 𝒎

)

!

,

где

𝒏

! =

∙

∙

∙ … ∙

𝟏 𝟐 𝟑

𝒏

Пример 1. Группа учащихся изучает 7 учебных дисциплин. Сколькими способами можно

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

различных урока?

Решение. Число способов равно числу размещений из 7 элементов по 4, т.е. равно

𝐴

7

4

.

Получаем

𝐴

7

4

=

7!

(

7−4

)

!

=

3!∙4∙5∙6∙7

3!

=

4 ∙ 5 ∙ 6 ∙ 7 = 870.

Ответ: 870 способов.

1.2. Перестановки. Размещения из n элементов по n элементов называются

перестановками из n элементов:

𝑃

𝑛

=

𝐴

𝑛

𝑛

=

𝑛

!

(

−

𝑛

𝑛

)

!

=

𝑛

!

0!

=

!

𝑛

𝑷

𝒏

=

!

𝒏

Пример 2. Сколько шестизначных чисел, кратных пяти, можно составить из цифр 1, 2, 3, 4,

5, 6 при условии, что в числе цифры не повторяются?

Решение. Цифра 5 должна стоять на последнем месте. Остальные пять цифр могут стоять на

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

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

5! = 1 ∙ 2 ∙ 3 ∙ 4 ∙ 5 = 120.

Ответ: 120 чисел.

Пример 3. Возьмем буквы Б, А, Р. Какие перестановки из этих букв можно получить?

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

Решение. Получатся наборы: БАР, БРА, АРБ, АБР, РАБ, РБА.

По формуле

𝑃

𝑛

=

!

𝑛

получаем:

𝑃

3

= 3! = 1 ∙ 2 ∙ 3 = 6

наборов.

Ответ: 6 наборов.

1.3. Сочетания. Пусть имеется множество, состоящее из n элементов. Каждое его

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

элементов:

𝑪

𝒏

𝒎

=

𝒏

!

𝒎

!

(

−

𝒏 𝒎

)

!

.

Пример 4. Сколько матчей будет сыграно в футбольном чемпионате с участием 16

команд, если каждые две команды встречаются между собой один раз?

Решение. Матчей состоится столько, сколько существует двухэлементных подмножеств

у множества, состоящего из 16 элементов, т.е. их число равно:

𝐶

16

2

=

16!

2!

(

16−2

)

!

=

14!∙15∙16

2!∙14!

=

15∙16

2

=120.

Ответ: 120 матчей.

Свойства сочетаний:

C

C

m

n

n

m

n





C

C

C

m

n

m

n

m

m

n











1

1

2. Основные правила комбинаторики

2.1.

Правило

суммы (правило

«или»)

—

одно

из

основных

правил

комбинаторики.

Если элемент

𝐴

можно

выбрать

𝑚

способами,

а

элемент

𝐵

можно

выбрать

𝑘

способами,

то

выбрать

𝐴

или

𝐵

можно

𝑚

+

𝑘

способами.

Пример 5. Выбрать книгу или диск из

𝟏𝟎

книг и

𝟏𝟐

дисков можно

𝟏𝟎

+

=

𝟏𝟐

𝟐𝟐

способами.

2.2. Правило умножения (правило «и») — одно из основных правил комбинаторики. Если

элемент

𝐴

можно

выбрать

𝑚

способами,

и

при

любом

выборе

𝐴

элемент

𝐵

можно

выбрать

𝑘

способами, то пару

(

,

𝐴 𝐵

)

можно выбрать

𝑚

+

𝑘

способами. Естественным образом обобщается

на произвольное количество независимо выбираемых элементов.

Пример 6. Выбрать книгу и диск из

10

книг и

15

дисков можно

10 ∙ 15 = 150

способами.

3.Элементы комбинаторики – комбинации с повторениями

3.1. Размещение с повторениями или упорядоченная выборка с возвращением — это

размещение

«предметов» в

предположении,

что

каждый

«предмет»

может

участвовать

в

размещении несколько раз. Если при выборке

𝑚

элементов из

𝑛

– элементы возвращаются

обратно

и

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

то

это

размещения

с

повторениями или упорядоченная

выборка с возвращением.

Число размещений с повторениями из

𝑛

по m, обозначаемое

𝐴

̅

𝑛

𝑚

, равно:

𝑨

̅

𝒏

𝒎

=

𝒏

𝒎

Пример 7. Например, количество вариантов 3-значного кода, в котором каждый знак

𝐴

̅

𝑛

𝑚

является цифрой от 0 до 9 и может повторяться, равно:

𝐴

̅

10

3

= 10

3

= 1000.

Пример 8. Сколько можно составить «слогов» по 2 буквы с повторениями из 4 элементов:

𝑎

,

𝑏

,

𝑐

,

𝑑

?

Количество таких «слогов» по 2 буквы равно

4

2

= 16.

Эти размещения следующие:

𝑎𝑎

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

.

𝑎𝑏 𝑎𝑐 𝑎𝑑 𝑏𝑎 𝑏𝑏 𝑏𝑐 𝑏𝑑 𝑐𝑎 𝑐𝑏 𝑐𝑐 𝑐𝑑 𝑑𝑎 𝑑𝑏 𝑑𝑐 𝑑𝑑

3.2. Сочетание с повторениями или неупорядоченная выборка с возвращением — это

сочетание

«предметов»

в

предположении,

что

каждый

«предмет»

может

участвовать

в

размещении несколько раз. Если при выборке

𝑚

элементов из

𝑛

– элементы возвращаются

обратно

без

последующего

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

то

говорят,

что

это

сочетания

с

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

Число сочетаний с повторениями из n по m, обозначаемое

С

̅

𝑛

𝑚

, равно:

С

̅

𝒏

𝒎

=

𝑪

𝒏

+

−

𝒎 𝟏

𝒎

=

(

+

− )!

𝒏 𝒎 𝟏

(

− )!

!

𝒏 𝟏 𝒎

3.3. Перестановки с повторениями

Число перестановок c повторениями (

𝑚

различных элементов, где элементы могут повторяться

𝑚

1

,

𝑚

2

, … ,

𝑚

𝑘

раз и

𝑚

1

+

𝑚

2

+

+ 𝑚

⋯

𝑘

=

,

𝑛

где

−

𝑛

общее количество элементов)

вычисляется по формуле:

𝑷

𝒏

(

𝒎

𝟏

,

𝒎

𝟐

, … ,

𝒎

𝒌

)

=

𝒏

!

𝒎

𝟏

! ∙

𝒎

𝟐

! ∙ … ∙

𝒎

𝒌

!

Пример 9. Возьмем буквы Б, А, Р. Какие перестановки из этих букв можно получить?

Сколько таких наборов получится, если буква А повторяется два раза?

Решение.

Получатся наборы: БАРА, БРАА, БААР, ААРБ, ААБР, АБАР, АРАБ, АРБА, АБРА, РАБА, РААБ,

РБАА.

По формуле

𝑃

𝑛

(

𝑚

1

,

𝑚

2

, … ,

𝑚

𝑘

)

=

𝑛

!

𝑚

1

!∙

𝑚

2

!∙…∙

𝑚

𝑘

!

,

получаем:

𝑃

4

(

1,1,2

)

=

4!

1!∙1!∙2!

=

1∙2∙3∙4

1∙1∙2∙1

= 3 ∙ 4 = 12

наборов.

Ответ: 12 наборов.