Правило суммы и произведения.

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

План:

1 Правило суммы и произведения.

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

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

4. Примеры комбинаторных задач из различных областей знаний

 

Теоретические сведения

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

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

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

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

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

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

Правило суммы и произведения.

Правило суммы:

Пусть множество A содержит m элементов, n(A)=m, множество B содержит k элементов, n(B)=k объединяются в новое множество. Возникает вопрос о числе элементов в объединении этих множеств, n(A∪B). Имеются две возможности:

1. Данные множества не имеют общих элементов. Они не пересекаются, n(A∩B).=0. Поэтому n n(A∪B).= n(A) + n(B)= m + k. Формула справедлива для любого числа множеств.

2. Данные два множества имеют d общих элементов, n(A∩B).=d. Они пересекаются, n(A∩B).=0. Поэтому n(A∪B).= n(A) + n(B) - n(A∩B)= m + k.- d

Если учувствуют в объединении три множества: n(A)=m, n(B)=k, n(C)=s, n(A∩B).=d₁, n(B∩C).=d₂, n(A∩C).=d₃, n(A∩B∩C)=g, то формула имеет вид:

n(A∪B∪C).= n(A) + n(B)+ n(C)- n(A∩B)- n(A∩C)- n(A∩C)+n(A∩B∩C) или

n(A∪B∪C).= m + k +s - d₁ - d₂ – d₃ +g

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

Правило произведения

Пусть множество A содержит m элементов, n(A)=m, множество B содержит k элементов, n(B)=k из элементов которых необходимо записать множество W, состоящее из пар, первый элемент которых принадлежит множеству A, второй – множеству B. При этом справедлива формула: n(W)=n(AxB)=n(A)·n(B)=m·k. Множества W yназывается декартовым произведение множеств A и B. Формула справедлива для любого числа множеств, в том числе при умножении множества само на себя.

 

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

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

 

12Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: