нет. Учебное пособие в оронеж 2011 фгбоу впо Воронежский государственный технический университет
![]()
|
1. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ1.1. Простейшие комбинаторные конфигурацииКомбинаторика – раздел математики, связанный с решением задач выбора и размещения элементов конечного множества в соответствии с заданными правилами. Каждое правило определяет способ построения некоторой конструкции из элементов исходного множества. Полученные конструкции называются комбинаторными конфигурациями. Цель комбинаторного анализа заключается в изучении комбинаторных конфигураций, алгоритмов их построения, а также решении задач по их перечислению. Основные правила комбинаторикиБольшинство комбинаторных задач решается с помощью двух основных правил – правила суммы и правила произведения. Правило суммы. Пусть A, B – конечные множества, |A| = n, |B| = m. , следовательно . Комбинированная интерпретация. Если некоторый объект A можно выбрать n способами, а другой объект B можно выбрать m способами, то выбор «либо A, либо B» можно осуществить n+m способами. Правило произведения. Если мощность |A| = n, |B| = m, то . Комбинаторная интерпретация. Если объект A можно выбрать nспособами, а после каждого такого выбора другой объект Bможно выбрать (независимо от выбора объекта A) mспособами, то пары объектов A и B можно выбрать способами. Пусть , и |А| - число элементов множества A. Составим декартово произведение множеств A и B, т.е. множество пар . Тогда правило произведения записывается следующим образом: Пример. Сколько всего существует двузначных чисел? Решение. Поскольку в двузначном числе цифра, обозначающая число десятков, должна быть отлична от нуля, то A = {1, 2, …, 9}, B = {0, 1, 2, …, 9} и , Выборки элементов без повторенийПростейшими комбинаторными конфигурациями являются перестановки, размещения и сочетания. Перестановки. Пусть . Перестановкой элементов множества M называется любой упорядоченный набор элементов , состоящий из n различных элементов множества M. Перестановки отличаются друг от друга порядком следования элементов. Теорема. Число всех перестановок равно n! Доказательство. На первом месте можно разместить nэлементов, на втором – любой из оставшихся (n-1) элементов и т.д. Для последнего места остается 1 элемент. В силу правила произведения имеем: . Пример. Сколькими способами можно разместить 5 студентов при наличии 5 мест? . Размещения. Пусть множество Mсостоит из n элементов. Размещением (упорядоченной выборкой) из nэлементов по m элементов называется любой упорядоченный набор элементов , состоящий из mразличных элементов множества M. Теорема. Число размещений n элементов по mэлементов обозначается . . Справедлива формула: Доказательство. Размещение M элементов множества M можно представить, как заполнение некоторых m позиций элементами множества M. При этом первую позицию можно заполнить n способами, вторую позицию (n-1) способами. Последнюю позицию можно заполнить (n-m+1) способами. Пример. Из 10 книг производным образом берутся 3 книги и ставятся на полку. Сколько существует способов такой расстановки книг? . Заметим, что размещение из n элементов по nэлементов представляет собой перестановку, т.е.: Сочетания. Сочетанием (неупорядоченной выборкой) из nэлементов по m, где , называется неупорядоченное подмножество множества M, состоящее из nразличных элементов. Теорема. Число сочетаний из nэлементов по m обозначается как и определяется по формуле: Доказательство. Если объединить размещения из nэлементов по m, которые состоят из одних и тех же элементов (то есть не учитывать порядка расположения элементов), то получим сочетание из nэлементов по m. Так как для каждого такого сочетания можно получить n! размещений. Тогда и, следовательно: . Выборки элементов с повторениямиРазмещением (упорядоченной выборкой) с повторениями из n элементов по m называется любой упорядоченный набор , элементы которого могут повторяться. Поскольку в упорядоченном наборе может находиться любой из n элементов, то число размещений с повторениями (обозначение такого числа ) равно nm. Таким образом: Пример. Из чисел 1, 2, 3, 4 составляются трехзначные числа. Сколько чисел можно получить таким образом? . Сочетанием (неупорядоченной выборкой) с повторениями из n элементов по mэлементов называется множество, состоящее из элементов, выбранных m раз из множества M. При этом допускается выбирать элемент повторно. Число сочетаний с повторениями из n элементов по m обозначается . Пример. Сколько существует различных результатов бросания двух одинаковых кубиков? Вид простейшей комбинаторной конфигурации поможет определить следующая таблица Таблица 1
|