Помощь по Теле2, тарифы, вопросы

1

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

Комбинаторика – раздел математики, посвященный подсчету
количеств разных комбинаций элементов некоторого, обычно
конечного, множества
Го́тфрид Ви́льгельм Ле́йбниц
(21июня1646-14 ноября 1716) -
немецкий философ, математик,
логик, физик, юрист, языковед,
историк, дипломат
Блез Паска́ль
(19 июня 1623 - 19 августа 1662) -
французский математик, механик, физик,
литератор и философ
2

Задачи

1) Сколькими способами 6 разных папок с документами можно
расставить на полке?
2) При расследовании хищения установлено, что у преступника
шестизначный номер телефона, в котором все цифры различны
и нет нулей. Следователь, полагая, что перебор этих номеров
достаточно будет одного - двух часов, доложил о раскрытии
преступления. Прав ли он?
3) На иномарке, скрывшейся с места ДТП, был трехзначный
номер, в котором первая цифра 2. Сколько номеров
необходимо проверить по картотеке ГИБДД, чтобы найти
нарушителя?
3

Принципы комбинаторики Принцип сложения

Основные принципы комбинаторики:
Принцип сложения.
Принцип умножения.
Принцип сложения
Задача 1: В группе 7 девушек и 8 юношей. Сколькими
способами можно выбрать 1 человека для работы у доски?
Решение: 7+8=15
Задача 2: В группе 7 человек имеют «5» по математике, 9
человек – «5» по философии. В сессии 2 экзамена. Известно,
что 4 человека сдали сессию отлично. Сколько человек
имеют хотя бы одну пятерку в сессии?
Решение: 7+9-4=12
4

Принцип сложения

Принцип сложения: Если объект a можно получить n
способами, объект b можно получить m способами,
то объект «a или b» можно получить n+m-k
способами, где k – это количество повторяющихся
способов.
Теоретико-множественная формулировка
A B A B A B
5

Принцип умножения

Задача: На вершину горы ведут 5 дорог.
Сколькими способами можно подняться на гору и
спуститься с нее?
Решение: 5∙5=25.
Принцип умножения: если объект a можно получить
n способами, объект b можно получить m
способами, то объект «a и b» можно получить m∙n
способами.
Теоретико-множественная формулировка
A B A B
6

Задачи

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

3 5 7 105
7

Задачи

От дома до школы существует 6 маршрутов.
Сколькими способами можно дойти до школы
и вернуться, если дорога «туда» и «обратно»
идет по разных маршрутам?
Решение. По принципу умножения
6 5 30
8

Задачи

В корзине лежат 7 различных яблок и 5 апельсинов.
Яша выбирает из нее яблоко или апельсин, после чего
Полина берет яблоко и апельсин. В каком случае
Полина имеет большую свободу выбора: если Яша взял
яблоко или если он взял апельсин?
Решение. Если Яша взял яблоко, то по принципу
умножения Полина может осуществить свой выбор
6 5 30
способами. Если Яша взял апельсин,
то способами.
7 4 28
В первом случае у Полины свобода выбора большая.
9

Задачи

В классе 24 человека. Из них 15 человек изучают
английский язык, 12 – немецкий язык, 7 – оба языка.
сколько человек не изучают ни одного языка?
Решение. По принципу сложения 2 получим
количество людей, изучающих английский или
немецкий 15+12-7=20. Из общего числа учеников
класса вычтем полученное количество людей.
24-20=4. 4 человека не изучает ни одного языка.
15
7
12
10

Замечание

n!
читается «n факториал» и вычисляется по формуле
Например,
n! 1 2 3 ... n.
3! 1 2 3 6,
5! 1 2 3 4 5 120.
Считают, что 0!=1
11

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

Определение 1
Перестановкой n элементного множества называется
упорядоченный набор неповторяющихся элементов этого
множества длины n.
А а; b; с;
Пример:
перестановки: a; b; c ; b; a; c ; a; c; b ; b; c; a ; c; a; b ; c; b; a
Число размещений n – элементного множества обозначают Pn и
вычисляется по формуле:
Pn n!
Задача: В команде 6 человек. Сколькими способами можно
осуществить построение?
P6 6! 720
12

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

Определение 2
Число перестановок n – элементов, в котором
типа (i 1, k) вычисляется по формуле
Pn (n1 , n2 ,..., nk)
ni элементов i –того
(n1 n2 ... nk)!
n1!n2 !.... nk !
Задача: Сколько слов можно составить, переставив буквы в слове
«экзамен», а в слове «математика»?
Решение:
7! 5040
10!
151200
2! 3! 2! 1! 1! 1!
13

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

Определение 3
k -размещением без повторений n–элементного множества
называется упорядоченный набор длины k попарно различных
элементов данного множества.
A a; b; c - 2 размещения: a; b ; a; c ; b; c ; b; a ; c; a ; c; b
Число k- размещений n элементного множества обозначается
Ank
и вычисляется по формуле:
Пример:
n!
A
n k !
k
n
Задача: В соревновании участвуют 12 команд, сколькими
способами они могут занять призовые места?
А123
12!
12 11 10 1320
9!
14

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

Определение 4
k – размещением с повторениями n–элементного множества называется
упорядоченный набор длины k элементов данного множества.
А а; b; с
Пример
2- размещения с повторениями:
a; b ; b; a ; a; c ; c; a ; b; c ; c; b ; a; a ; b; b ; c; c
Число k – размещений с повторениями вычисляется по формуле:
Аnk n k
Задача: Сколько существует номеров машин?
А103 А123 123 103
15

Решение задач

16

Задачи

1)Сколькими способами можно составить список из
8 студентов, если нет полного совпадения ФИО?
Решение
P8 8! 40320
17

Задачи

2)Сколькими способами можно составить список 8
студентов, так, чтобы два указанных студента
располагались рядом?
Решение
Можно считать двоих указанных студентов за один
объект и считать число перестановок уже 7
объектов, т.е.
P7 7! 5040
Так как этих двоих можно переставлять местами друг
с другом, необходимо умножить результат на 2!
P7 2! 7! 2! 5040 2 10080
18

Задачи

3) Сколькими способами можно разделить 11 спортсменов
на 3 группы по 4, 5 и 2 человека соответственно?
Решение. Сделаем карточки: четыре карточки с номером 1,
пять карточек с номером 2 и две карточки с номером 3.
Будем раздавать эти карточки с номерами групп
спортсменам, и каждый способ раздачи будет
соответствовать разбиению спортсменов на группы. Таким
образом нам необходимо посчитать число перестановок 11
карточек, среди которых четыре карточки с одинаковым
номером 1, пять карточек с номером 2 и две карточки с
номером 3.
P(4,5,2)
11!
6 7 8 9 10 11
6930
4!5!2! 1 2 3 4 1 2
19

Задачи

4) Сколькими способами можно
вызвать по очереди к доске 4
учеников из 7?
Решение. Задача сводится к
подсчету числа размещений из 7
элементов по 4
7!
7!
A
4 5 6 7 840
(7 4)! 3!
4
7
20

Задачи

5)Сколько существует четырехзначных чисел, у которых
все цифры различны?
Решение. В разряде единиц тысяч не может быть нуля, т.е
возможны 9 вариантов цифры.
В остальных трех разрядах не может быть цифры,
стоящей в разряде единиц тысяч (так как все цифры
должны быть различны), поэтому число вариантов
вычислим по формуле размещений без повторений из 9 по
3
A93 9 8 7 504
По правилу умножения получим
9 A93 4536
21

Задачи

6)Сколько существует двоичных чисел, длина
которых не превосходит 10?
Решение. Задача сводится к подсчету числа
размещений с повторениями из двух элементов
по 10
10
2
A 2 1024
10
22

Задачи

7)В лифт 9 этажного дома зашли 7 человек. Сколькими
способами они могут распределиться по этажам дома?
Решение. Очевидно, что на первом этаже никому не надо
выходить. Каждый из 7 человек может выбрать любой из 8
этажей, поэтому по правилу умножения получим
8
8
...
8 87 2097152
7
Можно так же применить формулу для числа размещений с
повторениями из 8 (этажей) по 7(на каждого человека по
одному этажу)
7
8
A 87
23

Задачи

8)Сколько чисел, меньше 10000 можно написать с
помощью цифр 2,7,0?
Решение. Так как среди цифр есть 0, то, например
запись 0227 соответствует числу 227, запись 0072
соответствует числу 72, а запись 0007
соответствует числу 7. Таким образом, задачу
можно решить, используя формулу числа
размещений с повторениями
4
3
A 34 81

В пособии излагаются основы комбинаторики и комбинаторных алгоритмов.
Предназначено для студентов I, II курсов математических специальностей.
Подготовлено на кафедре систем телекоммуникаций.

Введение в комбинаторику. Некоторые области применения задач комбинаторики.
Представителям самых различных специальностей и профессий приходится решать задачи, в которых рассматриваются те или иные комбинации, составленные из букв, цифр, объектов. Вот некоторые примеры:
задача составления расписания;
в химии: рассмотрение всевозможных связей между атомами и молекулами;
решение транспортных задач;
планы реализации какой-либо продукции;
задачи составления и декодирования шифров.

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

Содержание
Лекция 1. Введение в комбинаторику. Некоторые области применения задач комбинаторики. Прямое произведение множеств. Правило суммы и правило произведения для конечных множеств. Принцип Дирихле. Размещения без повторений, размещения с повторениями, сочетания без повторений, сочетания с повторениями, перестановки. Мультимножество
Введение в комбинаторику. Некоторые области применения задач комбинаторики
Прямое произведение множеств
Правило суммы и правило произведения
Принцип Дирихле
Размещения, сочетания, перестановки
Мультимножество
Лекция 2. Основные тождества, связанные с числом сочетаний. Бином Ньютона. Следствия из теоремы о биноме Ньютона. Свойства биномиальных коэффициентов
Основные тождества, связанные с числом сочетаний
Бином Ньютона
Следствия из теоремы о биноме Ньютона
Свойства биномиальных коэффициентов
Лекция 3. Треугольник Паскаля. Некоторые свойства треугольника Паскаля. Свойства шестиугольника для треугольника Паскаля. Разбиение множеств. Числа Стирлинга второго рода
Треугольник Паскаля
Некоторые свойства треугольника Паскаля
Свойства шестиугольника
Разбиения множества
Числа Стирлинга второго рода
Лекция 4. Числа Белла. Числа Стирлинга первого рода. Беззнаковое число Стирлинга первого рода
Число Белла
Числа Стирлинга первого рода
Беззнаковое число Стирлинга первого рода
Лекция 5. Формула включений и исключений. Задача о беспорядках
Формула включений и исключений
Задача о беспорядках
Лекция 6. Число элементов, обладающих ровно к свойствами. Задача о встречах. Число элементов, обладающих не менее чем к свойствами
Число элементов, обладающих ровно к свойствами
Задача о встречах
Лекция 7. Полиномиальная теорема. Методы в комбинаторном анализе. Метод производящих функций. Задача о взвешивании
Полиномиальная теорема
Методы в комбинаторном анализе. Метод производящих функций
Задача о взвешивании
Лекция 8. Производящие функции. Виды производящих функций. Свойства производящих функций. Таблица соответствий производящих функций и последовательностей
Производящие функции
Виды производящих функций
Свойства производящих функций
Таблица соответствий производящих функций и последовательностей
Лекция 9. Дифференцирование и интегрирование производящих функций. Некоторые элементарные производящие функции. Бесконечно убывающая геометрическая прогрессия и последовательность из единиц
Дифференцирование и интегрирование производящих функций. Примеры использования
Некоторые элементарные производящие функции
Бесконечно убывающая геометрическая прогрессия и последовательность из единиц
Лекция 10. Примеры нахождения производящих функций для заданной последовательности. Примеры нахождения для последовательности производящих функций
Примеры нахождения производящих функций для заданной последовательности
Примеры нахождения для последовательности производящих функций
Лекция 11. Решение однородных рекуррентных соотношений. Общий метод решения рекуррентного соотношения
Решение однородных рекуррентных соотношений
Общий метод решения рекуррентных соотношений
Лекция 12. Последовательность Фибоначчи. Примеры использования производящих функций. Вычисление корня числа через производящие функции
Последовательность Фибоначчи
Примеры использования производящих функций
Вычисление корня числа через производящие функции
Лекция 13. Числа Каталана. Последовательность Каталана и производящая функция Каталана. Алгоритм расстановки скобок
Числа Каталана
Последовательность Каталана и производящая функция Каталана
Алгоритм расстановки скобок
Лекция 14. Генерирование комбинаторных объектов. Перестановки. Сочетания. Разбиение чисел. Подмножества множеств
Перестановки
Сочетания
Разбиения чисел
Подмножества множества
Литература
Учебно-методический комплекс по дисциплине «Комбинаторные алгоритмы»
1. Место дисциплины в структуре ООП
2. Цели и задачи дисциплины
3. Требования к результатам освоения дисциплины
4. Объем дисциплины и виды учебной работы
5. Содержание дисциплины
5.2. Лабораторный практикум
5.3. Практические занятия (семинары) не предусмотрены
6. Балльно-рейтинговая система оценки знаний, шкала оценок
7. Примерная тематика курсовых проектов (работ)
8. Учебно-методическое и информационное обеспечение дисциплины
I. Информация о преподавателях (ссылка на страницу)
II. Литература
III. Базы данных, информационно-справочные и поисковые системы
9. Материально-техническое обеспечение дисциплины
10. Методические рекомендации по организации изучения дисциплины.

Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Лекции по дискретной математике, Часть I, Комбинаторика, Зарипова Э.Р., Кокотчикова М.Г., 2012 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.

комбинаторика - рассматриваются взаимосвязано.

Человеку часто приходится иметь дело с задачами, в которых нужно подсчитать число всех возможных способов расположения некоторых предметов или число всех возможных способов осуществления некоторого действия. Например, сколькими способами могли быть распределены золотая, серебряная и бронзовая медали на Олимпийских играх в Сеуле по баскетболу; или сколькими различными способами можно разместить здания на площади ? Задачи такого типа называются комбинаторными .

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

Комбинаторика возникла в XVI веке. В то время в жизни привилегированных слоев общества большое место занимали азартные игры (карты, кости). Были широко распространены лотереи. Возникали вопросы: сколькими способами можно выбросить данное число очков, бросая две или три кости, или сколькими способами можно получить двух королей? Эти и другие проблемы оказались движущей силой в развитии комбинаторики .

Теоретические исследования вопросов комбинаторики предприняли Паскаль и Ферма, Бернулли, Лейбниц и Эйлер и др.

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

1. при конструировании :
   • для оптимального размещения элементов системы;
   • для размещения микросхем на плате или элементов на кристалле;
   • при трассировке (выборе маршрута);
2. синтезе схем и проектирования:
   • при решении вопроса, какой набор стандартных микросхем выбрать, чтобы реализовать разработанную схему устройства;
   • при разработке схемы на подсхемы для реализации различными блоками и т. д.;
3. при контроле, выбирая-перебирая последовательность тестирующих сигналов;
4. в организации систем, решая вопрос, каким выбрать оптимальный маршрут передачи информации по сети и т. п.

Общие правила комбинаторики

Рассмотрим некоторые конкретные задачи.

Задача. 1 . "Суеверные велосипедисты"

"Опять восьмерка" - воскликнул председатель клуба велосипедистов, - а все потому, что у меня билет № 008. Надо менять номера и проводить перерегистрацию".

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

00	01	02	....................	09
10	11	12	....................	19
20	21	22	....................	29
30	31	32	....................	39
40	.	.	....................	.
50	.	.	....................	.
60	.	.	....................	.
70	.	.	....................	.
80	.	.	....................	.
90	.	.	....................	.

Для решения этой задачи определим сначала, сколько однозначных номеров не содержит цифру 8? Это 0, 1, 2, 3, 4, 5, 6, 7, 9 - всего девять цифр, а теперь найдем все двузначные номера: их ( таблица ). За каждым двузначным номером можно поставить любую допустимую цифру, следовательно, . Значит в клубе было 729 велосипедистов.

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

Сколько членов было в клубе, если номера билетов были трехзначными и не включали цифр 0 и 8? .

Задача 2 . "Секретный замок"

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

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

Задача 3 . " Команда космического корабля"

В случае, когда число возможных выборов на каждом шаге зависит от того какие элементы были выбраны ранее, удобно решение изображать в виде "дерева". Сначала из одной точки проводят столько отрезков, сколько различных выборов можно сделать на 1-м шаге. Из конца каждого отрезка проводят столько отрезков, сколько можно сделать на 2-м шаге и т. д. В результате получается " дерево решений ".

Рассмотрим задачу о формировании команды космического корабля. Известно, что возникнет вопрос психологической совместимости. Предположим, надо составить команду из 3-х человек: командира, инженера и врача. На место командира есть четыре кандидата: , на место инженера три - , на место врача три - . Проведенная проверка показала, что совместим с ; совместим с ; совместим с и ; совместим с ; не совместим с ; не совместим с ; не совместим с .

Рис. 5.1.

Сколькими способами при этих условиях может быть составлена команда корабля? По результатам совместимости строится дерево решений ( рис. 5.1). Итак, всего 11 комбинаций, а без ограничения .

Упорядоченные множества. Перестановки

Множество называется упорядоченным , если каждому элементу этого множества поставлено в соответствие некоторое число (номер элемента) от до где - число элементов множества .

Всякое конечное множество можно сделать упорядоченным, если, например, переписать все элементы множества в некоторый список (.), а затем каждому элементу присвоить номер.

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

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

Пример . Перестановки множества из 3-х элементов имеют вид .

Число перестановок из элементов !

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

Задача 2 . Сколькими способами можно выстроить в линейку 10 человек (5 девушек и 5 юношей) с условием, чтобы девушки и юноши чередовались, первая - девушка? 5 девушек можно разместить ! способами, а 5 юношей аналогично !. Следовательно, всего способов .

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

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

Пусть - множество из элементов и -

241kb. 22.05.2011 18:33 553kb. 22.05.2011 18:33

Лекция 7-8 - комбинаторика.doc

Лекции 7-8. Комбинаторика

История

Комбинато́рика (Комбинаторный анализ) - раздел элементарной математики, связанный с изучением количества комбинаций, подчинённых тем или иным условиям, которые можно составить из заданного конечного множества объектов (безразлично, какой природы; это могут быть буквы, цифры, какие-либо предметы и т.п.).

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

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

Термин «комбинаторика» был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве». В течение всей своей жизни Лейбниц многократно возвращался к идеям комбинаторного искусства. Комбинаторику он понимал весьма широко, именно, как составляющую любого исследования, любого творческого акта, предполагающего сначала анализ (расчленение целого на части), а затем синтез (соединение частей в целое). Мечтой Лейбница, оставшейся, увы, неосуществлённой, оставалось построение общей комбинаторной теории. Комбинаторике Лейбниц предрекал блестящее будущее, широкое применение.

В XVIII веке к решению комбинаторных задач обращались выдающиеся математики. Так, Леонард Эйлер рассматривал задачи о разбиении чисел, о паросочетаниях, о циклических расстановках, о построении магических и латинских квадратов.

В 1713 году было опубликовано сочинение Я. Бернулли "Искусство предположений", в котором с достаточной полнотой были изложены известные к тому времени комбинаторные факты. "Искусство предположений" появилось после смерти автора и не было автором завершено. Сочинение состояло из 4 частей, комбинаторике была посвящена вторая часть, в которой содержатся формулы:

• 
  для числа перестановок из n элементов,
• 
  для числа сочетаний (называемого Я. Бернулли классовым числом) без повторений и с повторениями,
• 
  для числа размещений с повторениями и без повторений.

Для вывода формул автор использовал наиболее простые и наглядные методы, сопровождая их многочисленными таблицами и примерами. Сочинение Я. Бернулли превзошло работы его предшественников и современников систематичностью, простотой методов, строгостью изложения и в течение XVIII века пользовалось известностью не только как серьёзного научного трактата, но и как учебно-справочного издания. В работах Я. Бернулли и Лейбница тщательно изучены свойства сочетаний, размещений, перестановок. Перечисленные комбинаторные объекты относятся к основным комбинаторным конфигурациям .

Научно-техническая революция, в частности внедрение ЭВМ во все области жизни, вызвала подлинный расцвет дискретной математики. Ее методы должны были стать достоянием не только математиков, но и научно-технических работников - программистов, инженеров, вычислителей, экономистов и других, обеспечивающих успешное функционирование, а также дальнейшую разработку и совершенствование многочисленных систем управления и сложных вычислительных устройств. И комбинаторика, будучи важной составной частью дискретной математики, одним из ее краеугольных камней, также испытала подлинный подъем.
^

Некоторые задачи комбинаторики

1. Найти конфигурацию элементов, обладающую заранее заданными свойствами.

В некоторых случаях такую конфигурацию удается найти сразу. Например, если требуется расположить 10 точек и 5 отрезков так, чтобы на каждом отрезке было по 4 точки, то после недолгих размышлений мы вспоминаем фигуру пятиконечной звезды.

Конечно, если задача возникла из практики, то в большинстве случаев можно быть уверенным в существовании решения. Гораздо хуже в этом отношении положение шахматиста, рассчитывающего спасительную комбинацию, или специалиста по шифрам, придумывающего новый код с заранее заданными свойствами. Они не знают заранее, существует ли то, что они ищут, не являются ли их труды поисками черной кошки в темной комнате, где кошки и в помине не было. Таким образом, возникает вторая проблема комбинаторики.

^ 2. Доказать существование или отсутствие конфигурации с заданными свойствами.

Во многих случаях, однако, бывает недостаточно найти одну конфигурацию с заданными свойствами, а требуется описать все такие конфигурации и найти их число. Например, можно потребовать найти не одно, а все возможные расположения 10 точек на 5 отрезках, при которых на каждом отрезке лежат по 4 точки. Можно доказать, что кроме пятиконечной звезды есть еще пять расположений с таким свойством.

3. Найти общее число конфигураций с заданными свойствами.

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

5. Из всех решений данной комбинаторной задачи выбрать оптимальное по тем или иным параметрам.

Одной из классических оптимизационных задач является «задача о коммивояжере», в которой требуется наметить путь бродячего торговца, объезжающего заданные η городов, причем он должен по одному разу побывать в каждом городе и проделать весь путь за наименьшее время. Несмотря на усилия многих специалистов, до сих пор нет достаточно общего и удовлетворительного решения этой задачи.
^

Структура и методы

Комбинаторика располагает столь многообразными методами, решает столь разнообразные задачи, что трудно чётко обозначить её границы. Условно в комбинаторной теории можно выделить следующие три большие части (см. схему):

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

Элементарными комбинаторными конфигурациями являются сочетания, размещения, перестановки. Для подсчёта числа этих конфигураций используются правила суммы и произведения.

^ Правило суммы: Если элемент A можно выбрать m способами, а элемент B можно выбрать k способами, то выбор элемента A или B можно осуществить m + k способами.

Правило суммы можно перефразировать на теоретико-множественном языке. Обозначим через | A | число элементов множества A , через A B - объединение множеств A и B , через A xB - декартово произведение множеств A и B . Тогда для непересекающихся множеств A и B выполняется равенство: | A B | = | A | + | B | .

Пример: В корзине находится 5 яблок и 7 груш. Сколькими способами можно взять из корзины 1 фрукт (1 яблоко или 1 грушу)? 5+7=12
Подобное правило выполняется тогда, когда множества не пересекается. Если же множества пересекаются, то используются принципы включения-исключения . Формула для двух множеств имеет следующий вид:

^ |AB| = |A| + |B| - |AB|

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

Пример: В группе учатся несколько студентов, каждый из которых имеет, по крайней мере, одну специализацию. На кафедре истории древнего мира и средних веков проходят специализацию 7 человек, на кафедре отечественной истории - 5 человек. Имеют две специализации 4 человека. Сколько студентов учится в группе.

|А|=7; |В|=5; |AB|=4; следовательно, конечная мощность множества |AB|=7+5-4=8.
Формула для двух множеств имеет следующий вид:

^ |ABС| = |A| + |B| + |С| - |AB| - |AС| - |ВС| + |ABС|

Пример: В отделе научно-исследовательского института работают несколько человек, причём каждый из них знает хотя бы один иностранный язык: 12 человек знают английский, 10 - французский, 8 - немецкий, 6 знают английский и французский, 4 - немецкий и английский, 2 - французский и немецкий, 1 человек знает все три языка. Сколько человек работает в отделе? Сколько из них знают только английский язык? Только французский? Только немецкий? Сколько человек знает ровно 1 язык?

Введем следующие множества:

А – множество сотрудников, знающих английский язык;

В – множество сотрудников, знающих французский язык;

С – множество сотрудников, знающих немецкий язык.

^ |А|=12; |В|=10; |С|=8; |AB|=6; |AС|=4; |ВС|=2; |ABС|=1

Тогда конечная мощность множества |ABС| = 12+10+8-6-4-2+1=19.
В классе учатся 50 школьников, в том числе 25 мальчиков. Учатся на хорошо и отлично 30 школьников, в том числе 16 мальчиков. Спортом занимаются 28 учеников, среди которых 18 мальчиков и 17 школьников, учащихся на хорошо и отлично. Учатся на хорошо и отлично и в то же время занимаются спортом 15 мальчиков. Обозначим через м принадлежность к мужскому полу, через у - хорошую успеваемость и через с - увлечение спортом. Подсчитаем, сколько девочек не занимаются спортом и получают время от времени тройки (а быть может, и двойки), т. е. найдем, чему равно |неМнеУнеС|.

По условию задачи имеем

^ |U|=50; |М|=25; |У|=30; |С|=28; |МУ|=16; |МС|=18; |СУ|=17; |МУС|=15
При такой постановке задачи, когда из известного множества, элементы которого обладают какими-либо свойствами, нужно найти мощность неизвестного подмножества, которые этими свойствами не обладают, используется следующая модификация формулы включения-исключения :

|неAнеBнеС| = |U |-|A|-|B|-|С|+|AB|+|AС|+|ВС|-|ABС|

Ответ задачи:

Конечная мощность множества |неМнеУнеС| = 50-25-30-28+16+18+17-15=3

^ Правило произведения: Если элемент A можно выбрать m способами, а после каждого выбора элемента A элемент B можно выбрать k способами, тогда, упорядоченную пару элементов (A , B ) можно выбрать m*k способами.

На теоретико-множественном языке правило произведения формулируется так:

|A хB| = | A | | B | .

Пример: В магазине продаются розы, лилии, гвоздики четырех цветов: красного, белого, розового, чайного. Сколько различных цветов по виду и цвету продается в магазине?
Правило произведения можно распространить на выбор последовательности (x 1 ,x 2 ,…,x n ) произвольной конечной длины n .

Пример: Сколько четырехзначных чисел можно составить из цифр 0,1,2,3,4,5, если ни одна из цифр не повторяется более одного раза?

Шаг 1 - выбор первой цифры - 5-ю способами, т.к. 0 первым быть не может;

Шаг 2 - выбор второй цифры - 5-ю способами, т.к. цифры не повторяются, а одну мы уже выбрали;

Шаг 3 - выбор третьей цифры - 4-мя способами;

Шаг 4 - выбор четвертой цифры - 3-мя способами.

Следовательно, по правилу произведения, 5*5*4*3=300 способами можно составить из цифр 0,1,2,3,4,5 четырехзначные числа, если ни одна из цифр не повторяется более одного раза.
Проверка:

У англичан принято давать ребенку несколько имен. Сколькими способами в Англии можно назвать ребенка, если общее число имен равно 300, а ему дают не более трех имен? Хватит ли этих наборов на всех англичан (57 млн чел.) или непременно найдутся англичане с одинаковыми именами?

Ребенок может получить либо 1, либо 2, либо 3 имени. Следовательно всего вариантов: 300 + 300*299 + 300*299*298 = 26 820 600

^

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

Мы рассмотрели некоторые общие правила решения комбинаторных задач. С их помощью можно решать задачи самых разных типов. Однако как в геометрии неудобно всегда сводить решение задачи к аксиомам, а удобнее пользоваться теоремами, так и в комбинаторике вместо решения задачи по общим правилам часто удобнее пользоваться готовыми формулами. Дело в том, что некоторые типы задач встречаются значительно чаще других. Комбинациям, которые встречаются в этих задачах, присвоены особые названия - размещения, перестановки и сочетания. Для числа таких комбинаций выведены особые формулы, которыми и пользуются при решении различных комбинаторных задач.
^

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

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

Классической задачей на размещение с повторениями является задача «секретный замок ». Для запирания сейфов и автоматических камер хранения багажа применяют секретные замки, которые открываются лишь тогда, когда набрано некоторое «тайное слово» или тайный набор цифр. Это слово набирают с помощью одного или нескольких дисков, на которых нанесены буквы или цифры.

Пусть число букв на каждом диске равно 12, а число дисков равно 5. Сколько неудачных попыток может быть сделано человеком, не знающим секретного слова и подбирающим его наудачу?
Диски представляют собой вакантные места, в каждое из которых будет размещен один из предлагаемых видов элементов, т.е. одна из двенадцати букв, причем одна и та же буква может повторяться на нескольких дисках.

Подобные конфигурации принято обозначать

Так как по условию буква на каждом диске может быть выбрана 12 способами, а дисков 5, то по правилу умножения мы можем заключить, что максимальное число комбинаций будет А 5 12 = 12*12*12*12*12*12 или 12 5 = 248 832. Значит, неудачных попыток может быть 248 831. Считая по 6 секунд на одну попытку, получаем, что для открытия сейфа понадобится более 400 часов непрерывной работы. Впрочем, обычно сейфы делают так, чтобы после первой же неудачной попытки раздавался сигнал тревоги.
Опираясь на этот пример, мы можем записать формулу:

Проверка:

1. Единицей цифровой информации в двоичной системе является байт – это «слово», состоящее из 8 бит (каждый бит – это двоичный разряд, состоящий из 0 или 1). Почему кодовая таблица для шрифтов содержит именно 256 знаков?

Количество мест для заполнения (т.е. k) по условию у на 8, видов элементов для заполнения мест (т.е. n) всего 2. Следовательно, А 8 2 = 2 8 = 256
2. Азбука Морзе предполагает кодирование символами «.» и «-». При этом самые часто встречаемые буквы обозначаются одним символом (например, Е – «.»), а менее всего встречаемые - пятью символами (например, Э – «..–..»). Сколько букв, цифр, знаков препинания закодировано одним, двумя, тремя, четырьмя, пятью символами? Почему именно пять символов стало максимальной длиной для кодирования?

А 1 2 = 2 1 =2

А 2 2 = 2 2 =4

А 3 2 = 2 3 =8

А 4 2 = 2 4 =16

А 5 2 = 2 5 =32

По правилу сложения 2+4+8+16+32=62 символа можно закодировать с помощью подобных комбинаций, что достаточно для букв, цифр и знаков препинания.

^

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

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

Классической задачей на размещение с повторениями является задача «первенство по футболу».

В первенстве страны по футболу участвовали 16 команд. Перед началом первенства был объявлен конкурс знатоков, в котором требовалось предсказать распределение медалей. Сколько различных ответов можно дать на этот вопрос?

Эта задача решается на основе правила произведения. Комплект золотых медалей может получить любая из 16 команд. Иными словами, здесь у нас 16 возможностей. Но если золотые медали уже завоеваны какой-то командой, занявшей 1 место, то остается лишь 15 претендентов на второе место и серебряные медали. Повторения здесь не может быть - одна и та же команда не может завоевать и золотые, и серебряные медали. Значит, после вручения чемпиону золотых медалей остается 15 возможностей получения серебряных медалей. Точно так же, если уже вручены и золотые, и серебряные медали, то на третье место и бронзовые медали претендует лишь одна из оставшихся 14 команд. По правилу произведения получаем, что медали могут быть распределены 16*15*14 = 3 360 способами.
Во многих комбинаторных задачах, которые рассматривают комбинации без повторений, встречается подобные произведения числа. Допустим, что условие предполагает некоторое число nN. Обозначим произведение всех натуральных чисел от 1 до n как n! (читается, как «эн-факториал»). 1!=1; 2!=1*2=2; 3!=1*2*3=6; 4!=1*2*3*4=24; удобно считать, что 0!=1.

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

Приведенную выше задачу можно вписать в эту формулу:

А 3 16 = 16! / (16-3)! = 16! / 13! =

1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16

/ 1*2*3*4*5*6*7*8*9*10*11*12*13 = после сокращения =

14*15*16 = 3360.

Проверка:

1. Научное общество состоит из 25 человек. Надо выбрать президента общества, вице-президента, ученого секретаря и казначея. Сколькими способами может быть сделан этот выбор, если каждый член общества может занимать лишь один пост!

В этом случае надо найти число размещений (без повторений) из 25 элементов по 4. Поэтому ответ дается формулой А 4 25 = 25! / (25-4)! = 25! / 21! = 22*23*24*25.
2. В соревновании по гимнастике участвуют 10 человек. Четверо судей должны независимо друг от друга пронумеровать их в порядке, отражающем их выступление в соревновании. Победителем считается тот, кого назовут первым хотя бы двое судей. В какой доле случаев победитель соревнований будет определен?

Четыре судьи могут выбрать победителя 10 4 =10000 способами. Трех различных кандидатов они назовут в А 4 10 = 5040 случаях. Поэтому совпадение хотя бы у двух судей будет в 4960 случаях.

^

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

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

Число перестановок из n элементов обозначают через Ρ n . Формула для P n сразу получается из формулы для числа размещений без повторений.

Р n = A n n = n! / (n-n)! = n! / 0! = n! / 1 = n!

P n = n!

Классической задачей на размещение с повторениями является задача «Чайник за рулем!».

Сколько аварийных ситуаций создаст начинающий водитель, если нарушит правильную последовательность следующих операций.

1. 
   Сесть в кресло водителя.
2. 
   Пристегнуть ремень.
3. 
   Завести двигатель.
4. 
   Убедиться в отсутствии препятствия.
5. 
   Указать направление собственного движения.
6. 
   Пропустить все транспортные средства, для которых твой транспорт может стать препятствием.
7. 
   Вырулить на полосу движения.

Все n-элементы важны и их нельзя «выкинуть» из списка. Т.е. n=k. Следовательно всего возможных перестановок предложенных инструкцией операций = 7! = 5040. Одна из последовательностей правильная, следовательно количество аварийных ситуаций 5039.
Число перестановок трехэлементного множества {а,b,c} = 3! = 1*2*3 = 6. Действительно, {a,b,c};{b,c,a};{c,a,b};{a,c,b};{c,b,a};{b,a,c}
Проверка:

1. На званый вечер приглашены 5 мужчин и 5 женщин. Напротив каждого места на стол необходимо поставить табличку с именем того, кто будет на этом месте сидеть, но никакие два лица одного пола не должны сидеть рядом. Сколькими способами можно расставить таблички?

Разделение мест на «мужские» и «женские» можно провести двумя способами: Р 2 =2!=2. Мужчин можно рассадить 5! способами, также как и женщин 5! способами. Следовательно, таблички расставляются 2*5!*5! способами = 2*5! 2 способами = 28800 способами.
2. Сколько нечетных и сколько четных четырехзначных чисел можно составить из цифр числа 3694, если каждую цифру надо использовать один раз?

На последнем месте может стоять либо цифра 3, либо 9, а остальные цифры можно переставлять P 3 = 3! способами. Всего получаем 12 нечетных чисел. Точно так же получаем, что количество четных чисел равно 12.

^

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

Подобные задачи должны содержать в условии набор элементов, некоторые из которых повторяются. Обозначается как P(n 1, n 2, .., n i ) . При этом n=n 1 +n 2 +n i .

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

Например, в слове из 4-х неповторяющихся букв число перестановок = 4! = 24. В слове же «мама» имеется два элемента двух различных типов, т.е. 2 элемента буквы «м» и 2 элемента буквы «а». Здесь будет всего 6 перестановок: «мама», «амам», «маам», «амма», «аамм», «ммаа».
Сокращение количества перестановок происходит из-за того, что меняя повторяющиеся типы элементов, мы получаем один и тот же вариант.

Сколько перестановок можно сделать в слове «математика»?

Здесь у нас две буквы «м», три буквы «а», две буквы «т», по одной буквы «е», «и», «к», а всего 10 букв. Значит, по формуле число перестановок равно

Р (2,3,2,1,1,1) = 10! / 2!*3!*2!*1!*1!*1! = 3628800/2*6*2*1*1*1 = 3628800/24 = 151200
Проверка:

1. У мамы 2 одинаковых яблока, 3 одинаковых мандарина и 4 одинаковых апельсина. Каждый день в течение 9 дней подряд она выдает сыну по одному фрукту. Сколькими способами это может быть сделано?

Р(2, 3, 4) = 1260.

2. Сколько различных «слов» можно получить, переставляя буквы слова: а) «парабола»; в) «ингредиент»?

А) Р(3, 1, 1, 1, 1, 1) = 8! / 3!*1!*1!*1!*1!*1! = 40320/6 = 6720;

Б) Р(2, 2, 2, 1, 1, 1, 1) = 10! / 2!*2!* 2!*1!*1!*1!*1! = 3628800/8 = 453600

3. Сколькими способами можно расставить белые фигуры (короля, ферзя, две ладьи, двух слонов и двух коней) на первой линии шахматной доски (не соблюдая шахматные правила)?

Р(2, 2, 2, 1, 1) = 5040

4. На первые две линии шахматной доски произвольным образом ставятся белые и черные фигуры (по два коня, два слона, две ладьи, ферзь и король каждого цвета). Сколькими способами можно это сделать? Сколькими способами можно расставить те же фигуры по всей доске? А если расставляются и все пешки (по 8 пешек каждого цвета)?

Р(2, 2, 2, 2, 2, 2, 1, 1, 1, 1). На всей доске добавляется 48 пустых полей, поэтому ответ Р(48, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1). С пешками ответ Р(32, 8, 8, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1).

^

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

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

Число сочетаний, которые можно составить из n элементов по k, обозначают через С k n или .

В классической задаче на размещение без повторений «первенство по футболу» нас интересовало, кто конкретно займет 1-ое, 2-ое и 3-е места. Но если нас будут интересовать только группа призеров и неважно будет, кто конкретно получил золото, серебро и бронзу (иными словами, из 16-тиэлементного множества мы должны составить все возможные 3-хэлементные множества), то вариантов распределения будет в 6 раз т.е. в 3! раз меньше. 3360 / 3! = 3360/6 = 560

1-Спартак 3-Торпедо

1-Спартак 2-Торпедо

1-Динамо 2-Спартак 3-Торпедо

1-Динамо 2-Торпедо 3-Спартак

1-Торпедо 2-Спартак

1-Торпедо 2-Динамо 3-Спартак

или

* Подобные коэффициенты еще называют биноминальными коэффициентами.
Классической задачей на сочетания без повторений является задача «Прощай, высшая лига!»

В первенстве страны по футболу участвуют 16 команд, а по итогам первенства высшую лигу покидают команды, занявшие последние два места. Каково будет число различных «печальных» исходов футбольного первенства?

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

Следовательно, С 2 16 = 16! / 14! * 2! = 120
Проверка:

А) Сколькими способами можно выбрать три различные краски из имеющихся пяти различных красок? Б) Сколькими способами можно сделать трехцветный флаг (с тремя горизонтальными полосами), если имеется материя пяти различных цветов? В) А если один из цветов должен быть красным? Г) А если цвета могут повторяться, но не рядом (полосы должны быть различимы)?

Так как порядок красок не играет роли, то С 3 5 = 5! / 2! * 3! = 10 способов.

Здесь порядок красок уже важен, поэтому имеем А 3 5 = 5! / 2! = 60 способов.

Если одна полоса красная, то имеем 3 * А 2 4 = 3 * 4! / 2! = 36 способов.

Если цвета могут повторяться, то, осуществляя выбор сверху вниз, имеем 5 * 4 * 4 = 80 способов.

^

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

Подобные задачи должны содержать в условии предметы n различных типов. Сколькими способами можно сделать из них комбинацию из k элементов, если не принимать во внимание порядок элементов в комбинации, при этом предметы одного типа могут повторяться! Иными словами, различные комбинации должны отличаться количеством предметов хотя бы одного типа.

Такие комбинации называют сочетаниями с повторениями из n элементов по k, а их число обозначают Č k n .

Классической задачей на сочетания без повторений является задача «Булочная-кондитерская».

В кондитерском магазине продавались пирожные 4 видов: корзиночки, наполеоны, песочные и эклеры. Сколькими способами можно купить 7 пирожных?

Č 7 4 = (7+(4-1))! / 7!*(4-1)! = 10! / 7! * 3!= С 7 10
Проверка:

В почтовом отделении продаются открытки 10 видов. Сколькими способами можно купить в нем 12 открыток? Сколькими способами можно купить 8 открыток? Сколькими способами можно купить 8 различных открыток?

План:

1. Элементы комбинаторики.

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

4. Применение графов (схем) при решении комбинаторных задач.

1. Комбинаторика и ее возникновение.

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

Комбинаторика возникла в XVI веке. В жизни привилегированных слоев тогдашнего общества большое место занимали азартные игры (карты, кости). Широко были распространены лотереи. Первоначально комбинаторные задачи касались в основном азартных игр: сколькими способами можно получить данное число очков, бросая 2 или 3 кости или сколькими способами можно получить 2-ух королей в некоторой карточной игре. Эти и другие проблемы азартных игр являлись движущей силой в развитии комбинаторики и далее в развитии теории вероятностей.

Одним из первых занялся подсчетом числа различных комбинаций при игре в кости итальянский математик Тарталья. Он составил таблицы (числа способов выпадения k очков на r костях). Однако, он не учел, одна и та же сумма очков может выпасть различными способами, поэтому его таблицы содержали большое количество ошибок.

Теоретическое исследование вопросов комбинаторики предприняли в XVII веке французские математики Блез Паскаль и Ферма. Исходным пунктом их исследований были так же проблемы азартных игр.

Дальнейшее развитие комбинаторики связано с именами Я. Бернулли, Г. Лейбница, Л. Эйлера. Однако, и в их работах основную роль играли приложения к различным играм.

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

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

Правило суммы: Если некоторый объект А может быть выбран m способами, а объект В- k способами, то объект «либо А, либо В» можно выбрать m +k способами.

Примеры:

1. Допустим, что в ящике находится n разноцветных шаров. Произвольным образом вынимается 1 шарик. Сколькими способами это можно сделать?

Ответ: n способами.

Распределим эти n шариков по двум ящикам: в первый- m шариков, во второй- k шариков. Произвольным образом из произвольно выбранного ящика вынимается 1 шарик. Сколькими способами это можно сделать?

Решение: Из первого ящика шарик можно вынуть m способами, из второго- k способами. Тогда всего способов m+k=n .

2. Морской семафор.

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

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

Правило произведения: Если объект А можно выбрать m способами, а после каждого такого выбора другой объект В можно выбрать (независимо от выбора объекта А) k способами, то пары объектов «А и В» можно выбрать m *k способами.

Примеры:

1. Сколько двузначных чисел существует?

Решение: Число десятков может быть обозначено любой цифрой от 1 до 9. Число единиц может быть обозначено любой цифрой от 0 до 9. Если число десятков равно 1, то число единиц может быть любым (от 0 до 9). Таким образом, существует 10 двузначных чисел, с числом десятков- 1.Аналогично рассуждаем и для любого другого числа десятков. Тогда можно посчитать, что существует 9 *10 = 90 двузначных чисел.

2. Имеется 2 ящика. В одном лежит m разноцветных кубиков, а в другом- k разноцветных шариков. Сколькими способами можно выбрать пару «Кубик-шарик»?

Решение: Выбор шарика не зависит от выбора кубика, и наоборот. Поэтому, число способов, которыми можно выбрать данную пару равно m *k .

3. Генеральная совокупность без повторений и выборки без повторений.

Генеральная совокупность без повторений - это набор некоторого конечного числа различных элементов a 1 , a 2 , a 3 , ..., a n .

Пример: Набор из n разноцветных лоскутков.

Выборкой объема k (k n ) называется группа из m элементов данной генеральной совокупности.

Пример: Пестрая лента, сшитая из m разноцветных лоскутков, выбранных из данных n .

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

- число размещений из n по k .

Число размещений из n по k можно определить следующим способом: первый объект выборки можно выбрать n способами, далее второй объект можно выбрать n -1 способом и т.д.

Преобразовав данную формулу, имеем:

Следует помнить, что 0!=1.

Примеры:

1. В первой группе класса А первенства по футболу участвует 17 команд. Разыгрываются медали: золото, серебро и бронза. Сколькими способами они могут быть разыграны?

Решение: Комбинации команд-победителей отличаются друг от друга составом и порядком следования элементов, т.е. являются размещениями из 17 по 3.

2. Научное общество состоит из 25-ти человек. Необходимо выбрать президента общества, вице-президента, ученого секретаря и казначея. Сколькими способами это можно сделать?

Решение: Комбинации руководящего состава общества отличаются друг от друга составом и порядком следования элементов, т.е. являются размещениями из 25 по 4.

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

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

Примеры:

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

Решение: Имеем перестановки из 5 элементов. 2. Сколькими способами можно собрать 6 разноцветных лоскутков в пеструю ленту?
Решение: Имеем перестановки из 6 элементов.

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

- число сочетаний из n по k

Элементы каждого из сочетаний можно расставить способами. Тогда Примеры:

1. Если в полуфинале первенства по шахматам участвует 20 человек, а в финал выходят лишь трое, то сколькими способам и можно определить эту тройку?

Решение: В данном случае порядок, в котором располагается эта тройка, не существенен. Поэтому тройки, вышедшие в финал, являются сочетаниями из 20 по 3.

2. Сколькими способами можно выбрать трех делегатов из десяти человек на конференцию?

Решение: В данном случае порядок, в котором располагается эта тройка, не существенен. Поэтому тройки делегатов являются сочетаниями из 10 по 3.

Конспект:

4.Применение графов (схем) при решении комбинаторных задач.

В случае, когда число возможных выборов на каждом шагу зависит от того, какие элементы были выбраны ранее, можно изобразить процесс составления комбинаций в виде «дерева». Сначала из одной точки проводят столько отрезков, сколько различных выборов можно сделать на первом шагу. Из конца каждого отрезка проводят столько отрезков, сколько можно сделать выборов на втором шагу, если на первом шагу был выбран данный элемент и т.д.

Задача:

При составлении команд космического корабля учитывается вопрос и психологической совместимости участников путешествия. Необходимо составить команду космического корабля из 3 человек: командира, инженера и врача. На место командира есть 4 кандидата: a 1 , a 2 , a 3 , a 4 .На место инженера- 3: b 1 , b 2 , b 3 . На место врача- 3: c 1 , c 2 , c 3 . Проведенная проверка показала, что командир a 1 психологически совместим с инженерами b 1 и b 3 и врачами c 1 и c 3 . Командир a 2 - с инженерами b 1 и b 2 . и всеми врачами. Командир a 3 - с инженерами b 1 и b 2 и врачами c 1 и c 3 . Командир a 4 -со всеми инженерами и врачом c 2 . Кроме того, инженер b 1 не совместим с врачом c 3 , b 2 - с врачом c 1 и b 3 - с врачом c 2 . Сколькими способами при этих условиях может быть составлена команда корабля?

Решение:

Составим соответствующее «дерево».

Ответ: 10 комбинаций.

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