МИНИСТЕРСТВО НАУКИ ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

РЕСПУБЛИКИ САХА (ЯКУТИЯ)

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ СРЕДНЕГО

ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

НЕРЮНГРИНСКИЙ ГУМАНИТАРНЫЙ КОЛЛЕДЖ

Краткий курс лекций и практических

заданий по разделу

«Комбинаторика».

учебно-методические материалы для самостоятельной работы студентов

технических специальностей

2009г.

Данные учебно-методические материалы предназначены для самостоятельной

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

раздела «Комбинаторика»: соединения и группы соединений, размещения без

повторений, размещения с повторениями, сочетания без повторений, сочетания с

повторениями, перестановки без повторений, перестановки с повторениями.

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

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

рекомендации

по

выполнению

самостоятельных

заданий

и

упражнения,

выполнение которых будет способствовать усвоению теоретических положений

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

методов и формул комбинаторных задач.

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

Яковенко Л. В. , преподаватель математики ГОУ СПО НГК

Рецензент:

Утверждено:

2

Содержание

Введение.........................................................................................................................

4

§1.

Соединения и группы соединений....................................................................

5

§2.

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

6

§3.

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

8

§4.

Сочетания без повторений..................................................................................

10

§5.

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

12

§6.

Перестановки без повторений.............................................................................

14

§7.

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

15

Рекомендации для выполнения самостоятельных заданий.......................................

17

Задачи для самостоятельного решения.......................................................................

18

Вопросы для самоконтроля..........................................................................................

20

Литература.....................................................................................................................

20

3

ВВЕДЕНИЕ.

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

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

заданных объектов. Другими словами, это раздел математики, в котором изучаются

задачи выбора элементов из заданного конечного множества и размещения этих

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

чисел можно написать с помощью цифр 1, 2, 3, 4?

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

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

необходимых временных затрат.

Задачи

подсчета

возможных

комбинаций

объектов,

удовлетворяющих

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

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

Многообразие таких задач не всегда удается описать с помощью математических

формул. Однако для стандартных распространенных ситуаций способы подсчета

вариантов определены.

Комбинаторный

анализ, или комбинаторика, - одна из наиболее успешно

применяемых в настоящее время областей математики. Прикладной характер

комбинаторики проявляется в ее применении в операционных исследованиях, в

статистике и др. В программировании она применяется при вычислении дискретных

конечных математических структур. В операционных исследованиях – для

составления

расписаний,

определения

последовательности

промышленных

операций, распределения материала, маршрутов транспортных средств и т.д.

4

§1. Соединения и группы соединений.

В переводе с латинского языка комбинация означает соединение. Соединением, или

комбинацией, называют группу предметов, безразлично каких. Например, группу

студентов в аудитории, совокупность каких – то букв, чисел, книг, стоящих на

полке, можно назвать соединением. Предметы, из которых состоят соединения,

называются элементами. Из элементов одного соединения можно составить другие

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

Например:

▪

для дежурства в аудитории необходимо выбрать трех студентов;

▪

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

конкурсе.

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

играет роли. Соединения будут отличаться друг от друга, только если хотя бы один

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

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

которые они заняли. Например, соединение:

Иванов – 1-е место, Петров – 2-е место, Сидоров – 3-е место

отличается отсоединения:

Петров – 1-е место, Сидоров – 2-е место, Иванов – 3-е место.

Учитывая различные варианты комбинаций, различаются три типа соединений:

▪

размещения,

▪

сочетания,

▪

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

5

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

Пусть имеется совокупность из n элементов. Из неё выбирают соединения,

каждое из которых содержит

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

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

(хотя бы одним),

либо порядком их расположения. Такие соединения

называются размещениями без повторений из n элементов по т.

Например, возьмем в качестве трех элементов цифры 1, 2, и 3, тогда n = 3.

Построим соединения из них, содержащие два элемента ( т = 2 ), которые будут

отличаться друг от друга либо элементами, либо порядком их расположения. Таких

соединений будет шесть (число размещений из трех по два)

Подсчитайте самостоятельно количество размещений из четырех цифр по две.

Сколько их?

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

имеющих большее число элементов, а это не просто, поэтому используем формулу

числа размещений.

Число размещений без повторений из n элементов по т в каждом обычно

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

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

(2.1)

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

Факториалом называется произведение n

натуральных чисел от 1

до n

включительно обозначается сокращенно n!, т.е.

1 · 2 · 3 · ... · (n – 1 ) · n

= n!

(2.2)

Принято считать, что 0! = 1

Пример 1: 7! = 1 · 2 · 3 · 4 · 5 · 6 · 7 = 5040.

6

Используя понятие факториала, формулу размещений без повторений (2.1)

можно представить так:

(2.3)

Пример 2:

Пример 3:

Пример 4:

Пример 5:

Задача.

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

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

этого замка.

Решение.

Возможных цифр всего десять (0, 1, 2, 3, 4, 5, 6, 7, 8, 9). Каждая набранная

комбинация кода отличается от другой комбинации либо хотя бы какой – то

цифрой, либо порядком набора одинаковых цифр. Так как цифры в коде по условию

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

формулу числа размещений без повторений (2.3).

Ответ: для кодового замка можно подобрать 5040 вариантов набора, если набирать

код последовательно и цифры в нем не повторяются.

7

Пример 6:

Задача.

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

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

вариантов, если учесть, что шансы быть избранным у всех членов совета

одинаковые?

Решение.

Каждая выбранная комбинация отличается либо набором студентов, либо

выбранными должностями. Следовательно, количество групп из 7 человек по 3

рассчитываем по формуле числа размещений без повторений (2.3).

Ответ: существует 210 различных вариантов выбора председателя совета, его

заместителя и секретаря из 7 студентов.

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

Выше описывались способы выбора соединений, при которых элементы в

одной группе не повторялись.

Рассмотрим случай, когда размещение из n элементов по т элементов может

содержать любой элемент сколько угодно раз от 1 до т включительно или не

содержать его совсем. Такое соединение называется

размещением с

повторениями.

Каждое размещение с повторениями из n элементов по т элементов может

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

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

Например, возьмем в качестве трех элементов цифры 1, 2 и 3, тогда n = 3. Построим

соединения из них, содержащие два элемента ( т = 2 ), которые будут отличаться

8

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

элемент может повторяться.

Таких соединений будет 9 (число размещений с повторениями из 3 по 2):

Подсчитайте самостоятельно количество размещений с повторениями из 4 цифр по 2. Сколько их?

Число размещение с повторениями из n элементов по т элементов будем

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

(с повт)

(с повт)

= n

т

(3.1)

Пример 7:

Задача.

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

этом цифры в коде могут повторяться. Требуется определить число возможных

кодов, которые можно подобрать для этого замка.

Решение.

Возможных цифр всего десять (0, 1, 2, 3, 4, 5, 6, 7, 8, 9). Каждая набранная

комбинация кода отличается от другой комбинации либо хотя бы какой – то

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

повторяться, поэтому для подсчета возможных комбинаций используем формулу

числа размещений с повторениями (3.1)

(с повт)

= 10

4

= 10000

Ответ: для кодового замка можно подобрать 10000 вариантов набора, если

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

Пример 8:

Задача.

9

Группе из 7 студентов поручили дежурить по колледжу 3 дня. Сколькими

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

студент и один и тот же студент может отдежурить один, два и все три дня.

Решение.

Количество групп из 7 человек по 3 рассчитываем по формуле числа

размещений с повторениями из 7 по 3. Выбранные студенты могут дежурить в

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

может отдежурить один, два и все три дня.

(с повт)

= 7

3

= 343

Ответ: существует 343 различных вариантов распределения дежурства.

§4. Сочетания без повторений.

Пусть имеется совокупность из n элементов. Из неё выбирают соединения,

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

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

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

Такие соединения называются

сочетаниями без повторений из n элементов по т.

Например, возьмем в качестве трех элементов цифры 1, 2 и 3, тогда n = 3.

Построим соединения из них, содержащие два элемента ( т = 2 ), которые будут

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

Таких соединений будет три (число сочетаний из трех по два):

Подсчитайте самостоятельно количество сочетаний из четырех цифр по две.

Сколько их?

В дальнейшем будем использовать для подсчета количества числа сочетаний

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

, формулу

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

10

где

(4.1)

Пример 9:

Задача.

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

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

замка.

Решение.

Возможных цифр всего десять (0, 1, 2, 3, 4, 5, 6, 7, 8, 9). Каждая набранная

комбинация кода отличается от другой комбинации хотя бы какой – то цифрой.

Порядок набора цифр не имеет значения т.к. цифры нажимаются одновременно.

Поэтому для подсчета возможных комбинаций кодов используем формулу числа

сочетаний без повторений (4.1)

Ответ: для кодового замка можно подобрать всего 210 вариантов набора, если

набирать цифры кода одновременно.

Пример 10:

Задача.

Из группы в которой учится 12 человек, необходимо выбрать 3 человека в

совет колледжа. Сколько существует различных способов такого выбора?

Решение.

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

возможных комбинаций выбора 3 студентов из 12 используем формулу числа

сочетаний без повторений (4.1)

Ответ: существует 220 различных способов выбора 3 студентов из 12.

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

11

§5

. Сочетания с

повторениями.

Рассмотрим случай, когда сочетание из n элементов по т элементов может

содержать любой элемент сколько угодно раз от 1 до т включительно или не

содержать

его

совсем.

Такое

соединение

называется

сочетанием

с

повторениями.

Каждое сочетание с повторениями из n элементов по т элементов может

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

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

Например, возьмем в качестве трех элементов цифры 1, 2 и 3, тогда n = 3. Построим

соединения из них, содержащие два элемента ( т = 2 ), которые будут отличаться

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

повторяться.

Таких соединений будет шесть (число сочетаний с повторениями из 3 по 2):

Подсчитайте самостоятельно количество сочетаний с повторениями из четырех

цифр по две. Сколько их?

Следует отметить, что если, например, два соединения по т

элементов отличаются

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

сочетаниями.

Число сочетаний с повторениями из n элементов по т элементов будем

1.

;

2.

;

3.

-

удобно применять при m >

;

4.

;

5.

12

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

(с повт)

(с повт)

=

(5.1)

Пример 11:

Задача.

В киоске продаются почтовые марки 5 различных типов. Необходимо

приобрести 10 марок. Учитывая, что марки одного типа неразличимы, определите

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

Решение.

Число вариантов выбора 10 марок 5 различных типов можно определить, используя

формулу числа сочетаний с повторениями, так как в одной покупке могут

встречаться марки одного и того же типа от 1 до 10 раз. Для вычисления числа

возможных вариантов используем формулу числа сочетаний с повторениями (5.1)

(с повт)

=

Ответ: существует 1001 различный способ покупки 10 марок.

Пример 12:

Задача.

Студент покупает 4 тетради. В магазине выставлены тетради 8 различных

видов. Студент может приобрести как одинаковые, так и разные тетради. Учитывая,

что

тетради одного типа

неразличимы,

определите

количество возможных

вариантов выбора покупки.

Решение.

Число вариантов выбора 4 тетрадей 8 различных типов можно

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

покупке могут встретиться тетради одного

и того же вида от 1 до 4 раз. Для

вычисления возможных вариантов выбора покупки используем формулу числа

сочетаний с повторениями (5.1)

13

(с повт)

=

Ответ: существует 330 различных способов покупки 4 тетрадей.

§6. Перестановки без повторений.

Перестановками без повторений

из

n

элементов называются такие

соединения, каждое из которых содержит

все n

элементов и которые

отличаются друг от друга лишь порядком расположения элементов.

Например, возьмем в качестве трех элементов цифры 1, 2 и 3, тогда n = 3. Построим

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

друга только порядком их расположения.

Таких соединений будет шесть (число перестановок из трех элементов):

Подсчитайте самостоятельно количество перестановок без повторений из четырех

цифр. Сколько их?

Число перестановок без повторений из n

элементов будем обозначать

символом

Р

п

Р

п

= 1 · 2 · 3 · ... · (n – 1 ) · n

=

n!

(6.1)

Пример 13:

Задача.

На книжной полке выставлены 8 книг разных авторов. Сколько способов

имеется для расстановки этих книг в разном порядке?

Решение.

14

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

состав изданий при каждом способе – неизменны. Следовательно, при решении этой

задачи необходимо рассчитать число перестановок из 8 элементов по формуле (6.1).

Р

8

= 8! =1 · 2 · 3 · 4 · 5 · 6 · 7 · 8 = 40320

Ответ: имеется 40320 способов переставить 8 книг в разном порядке.

§

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

Пусть имеется совокупность из n элементов, среди которых m элементов

первого, l – второго, k - третьего типов ( m + l + k = n). Элементы

повторяются α, β, γ раз соответственно. Такие соединения называются

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

Количество

возможных

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

с

повторениями

из

n

элементов

определяется по формуле:

Р

п (с повт.)

=

(7.1)

Например, возьмем в качестве элементов цифры 1 (повторяется 2 раза), 2

(повторяется 2 раза), тогда n = 2 + 2 = 4. Построим из них соединения, которые

будут содержать все 4 элемента и отличаться друг от друга только порядком их

расположения.

Таких соединений будет 6 (число перестановок с повторениями).

Для расчета числа возможных перестановок применим формулу (7.1).

Р

4 (с повт.)

=

.

15

Подсчитайте самостоятельно количество перестановок из четырех цифр, из

которых три семерки и одна пятерка. Сколько их?

Пример 14:

Задача.

Каждая буква слова

МАТЕМАТИКА написана на разных карточках.

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

Решение.

В слове МАТЕМАТИКА встречается буква А три раза, буквы Т и М по два

раза, буквы Е, И, и К по одному разу (n = 3 + 2 + 2 + 1 + 1 + 1 = 10). Способы

расстановки букв различаются только порядком, следовательно при решении этой

задачи необходимо рассчитать число перестановок с повторениями по формуле (7.1)

(с повт)

=

Ответ: имеется 151200 способов переставить буквы слова МАТЕМАТИКА в

разном порядке.

16

Рекомендации для выполнения самостоятельных заданий.

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

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

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

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

не важен, то для определения количества таких соединений используют формулу

числа сочетаний.

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

выполнения одинаковой работы. Если при выборе тех же студентов каждому их них

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

задания, что является существенным. В последнем случае следует использовать

формулу числа размещений.

Все комбинаторные операции удобно представить в следующей схеме:

Соединения

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

элементов

Выбор подмножества

элементов из множества

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

Сочетания

Размещения

Без повторений

Р

n

= n!

С повторениями

Без повторений

Без повторений

С повторениями

С повторениями

17

Задачи для самостоятельного решения.

1.

Сколькими способами можно расставить 6 различных книг на одной

полке?

2.

В соревнованиях принимают участие 16 команд. Сколькими способами

могут распределиться три первых места?

3.

В бригаде из 25 человек нужно выделить четырех для работы на

определенном участке. Сколькими способами это можно сделать?

4.

Имеется 5 видов конвертов без марок и 4 вида марок. Сколькими

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

5.

Из 9 человек надо выбрать 4 человека и разместить их на четырех

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

можно сделать?

6.

Сколькими способами можно составить команду из 4 человек для

соревнования по бегу, если имеется 7 бегунов?

7.

Сколькими способами можно обить 6 стульев тканью, если имеются

ткани 6 различных расцветок и все стулья должны быть разного цвета?

8.

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

6 ,7 и 9?

9.

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

различные трехзначные числа?

10.

Сколькими способами могут взойти 3 зерна пшеницы, если посажено 7

зерен?

11.

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

шахматной доски?

12.

Сколько различных двоичных чисел длиной 6 можно составить из цифр

0 и 1?

13.

В

группе

из

26

человек

выбирают

актив:

старосту,

физорга,

ответственного за дежурство и контролирующего пропуски. Сколькими способами

могут избрать актив группы?

14.

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

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

разыгрываются три медали: золотая, серебряная бронзовая?

15.

Сколькими способами в бригаде из 6 операторов можно разделить три

путевки в профилакторий, на турбазу и в дом отдыха?

16.

Для проведения итогов олимпиады по компьютерному моделированию

избрали жюри в составе председателя, заместителя председателя и трех членов

жюри. Сколькими способами можно выбрать жюри из 15 преподавателей кафедры

информатики?

18

17.

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

факультета программирования на различные должности в 5 вычислительных

центрах?

18.

Сколько существует различных шестизначных телефонных номеров?

19.

В библиотеке на книжной полке расставлены 10 книг различных

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

выбора книг можно осуществить?

20.

Паспорт гражданина Российской Федерации состоит из серии и номера.

Серия представляет собой 4 цифры, а номер – 6 цифр, расположенных в

произвольном порядке. Определите возможное количество различных паспортов,

которое может быть выдано гражданам Российской Федерации.

21.

В магазине имеется 15 видов различных коробок с конфетами.

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

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

конфетами могут быть и одинаковыми?

22.

Каждая буква слова СТАТИСТИКА написана на разных карточках.

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

23.

В киоске продавец музыкальных дисков предлагает организатору

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

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

случайного выбора 3 различных дисков?

24.

9 писем поступили в офис фирмы утренней почтой. Сколько существует

различных способов очередности вскрытия конвертов?

25.

На карточках разрезной азбуки написаны 33 буквы алфавита. 5 карточек

вынимают наугад и укладывают на стол в порядке появления. Сколько существует

способов составить разные слова из 5 букв?

26.

В ящике имеется 15 одинаковых деталей к конструктору, из них 10

деталей окрашены в красный цвет. Наугад извлекают 3 детали. Сколько

существует способов извлечения деталей, при которых все окажутся окрашенными

в красный цвет?

27.

Шифр сейфа состоит только из 6 цифр, которые должны набираться

последовательно и могут повторяться. Чему в этом случае равно общее число всех

возможных комбинаций шифра?

28.

Почтовый индекс состоит из 6 цифр. Сколько различных почтовых

отделений можно зашифровать с использованием индекса?

29.

На прилавке киоска выложены 10 различных журналов рекламирующих

компьютерную технику. У покупателя хватает денег на приобретение только 2 из

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

может осуществить покупатель?

19

30.

Выделены крупные суммы на выполнение 5 объектов строительных

работ. Сколько существует способов случайного распределения этих 5 объектов

между 7 возможными фирмами - подрядчиками?

Вопросы для самоконтроля.

2.

Что изучает комбинаторика?

3.

Назовите известные соединения в комбинаторике.

4.

Как называются соединения по m элементов, взятых из группы в n элементов,

каждое из которых отличается от другого либо хотя бы одним элементом,

либо порядком их расположения?

5.

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

каждое из которых отличается от других хотя бы одним элементом?

6.

Какие задачи решаются с помощью формул комбинаторики?

7.

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

друг от друга порядком элементов?

8.

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

повторениями?

Литература.

1.

А.С.Солодовников, Теория вероятностей: Учебное пособие для студентов

пед. институтов по матем. спец. - М.: Просвещение, 1983.

2.

П.В.Грес,

Математика

для

гуманитариев.

Учебное

пособие.

-

М:

Университетская книга, Логос, 2006.

3.

М.С.Спирина, Дискретная математика: учебник для студ. учреждений сред.

проф. образования / М.С.Спирина, П.А.Спирин – 2 -е изд. – М.: Издательский

центр «Академия», 2006.

4.

О.В.Максимова, Теория вероятностей и математическая статистика: Учебное

пособие для студентов средних специальных учебных заведений. – М.:

Издательско – торговая корпорация «Дашков и К

0

», 2006.

20

21