Комбинаторика Комбинаторный анализ

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

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

Основные правила комбинаторики Пусть имеется k групп А 1,А 2,...,А k, причем i-ая группа содержит n i элементов.

Правило умножения Общее число N способов, которыми можно получить упорядоченную совокупность (a 1,a 2,...a k ), где a iA i (т.е. выбрать по одному элементу из каждой группы и расставить их в определенном порядке), равно N=n 1 n 2 …n k. Если одну часть действия можно выполнить k способами, а другую - p способами, то все действие можно выполнить kp числом способов.

Пример Пусть требуется составить набор из ручки, карандаша и линейки. Имеется: 5 различных ручек, 7 различных карандашей, 10 различных линеек. Сколькими способами можно составить требуемый набор?

Правило сложения Если один элемент из группы A i можно выбрать n i способами, и при этом любые две группы A i и A j не имеют общих элементов, то выбор одного элемента или из A 1, или из A 2,..., или из A k можно осуществить N=n 1 +n 2 +…+n k способами. Если два действия взаимно исключают друг друга, и одно из них можно выполнить k способами, а другое - p способами, то оба действия можно выполнить k+p числом способов.

Пример В ящике 100 деталей, из них 30 – деталей 1-го сорта, 50 – 2-го, остальные – 3-го. Сколько существует способов извлечения из ящика одной детали 1-го или 2-го сорта?

Факториал Факториал числа n (обозначается n!) произведение всех натуральныхчисел до n включительно: По определению полагают 0! = 1. Факториал определён только для целых неотрицательных чисел.

Выборка Набор элементов x i1,…, x ik из множества X={x 1, …, x n } называется выборкой объема k из n элементов или, иначе, (n, k)-выборкой. УпорядоченнаяНеупорядоченная С возвращениемБез возвращения

Размещения Упорядоченная (n, k)- выборка с возвращением называется (n, k)- размещением с повторениями Упорядоченная (n, k)- выборка без возвращений называется (n, k)- размещением без повторений или просто (n, k)-размещением

Теорема Число размещений без повторений равно убывающему факториалу

Теорема Число размещений с повторениями из n элементов по k равно R n k =n k

Перестановки Перестановками из n элементов называются множества из элементов, отличающиеся один от другого порядком элементов. Обозначаем P n. Теорема: Теорема: Число перестановок без повторений равно P n =n!

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

Доказательство Рассмотрим перестановку из n элементов по k. Если не считаться с порядком элементов, то существует k! перестановок, которые не различимы. Следовательно Упрощая эту формулу, получим искомую.

Пример Имеется 6 штаммов бактерий. Для определения скорости их роста необходимо выбрать 3 штамма. Сколькими способами можно это сделать?

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

Разбиение Если множество из n различных элементов разбивается на k групп так, что в первую группу попадают n1 элементов, во вторую – n 2 элементов, в k-ую группу – n k элементов, причем n 1 +n n k =n, то число таких разбиений равно

Пример Сколькими способами можно разбить группу из 25 студентов на три подгруппы по 6, 9 и 10 человек в каждой группе?

Задача 1

Замечание

Доказательство леммы

Теорема

Задача 2

Доказательство

Задача 3

Доказательство

Пример

Бином Ньютона

Треугольник Паскаля