Презентация - N!. Соединения и правила комбинаторики

n!
Соединения и правила комбинаторики
Волошина Н.Н., *

Множества
Теория соединений, или, как ее еще называют, комбинаторика, - это раздел элементарной алгебры, где изучаются некоторые операции над конечными множествами и решаются задачи, связанные с этими операциями. Комбинаторика - раздел математики, посвящённый решению задач выбора и расположения элементов в соответствии с данными условиями. Термин «комбинаторика» происходит от латинского слова «combinare», что в переводе на русский означает – «сочетать», «соединять».

Термин "комбинаторика" был введён в математический обиход знаменитым Лейбницем. В 1666 году Лейбниц опубликовал «Рассуждения о комбинаторном искусстве». Комбинаторика становится наукой лишь в XVII в. в период, когда возникла теория вероятности. Чтобы решать теоретико-вероятностные задачи, нужно было уметь подсчитывать число различных комбинаций, подчиненных тем или иным условиям. Комбинаторными задачами интересовались и математики, занимавшиеся составлением и разгадыванием шифров, изучением древних письменностей. Теперь комбинаторика находит приложения во многих областях науки: в биологии, где она применяется для изучения состава белков и ДНК, в химии, механике сложных сооружений и т. д .

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

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

Круги Эйлера
Круги Эйлера – это особые чертежи, при помощи которых наглядно представляют отношения между множествами.
А
В
А
В
А
В
А=В
В
А
Множества А и В имеют общие элементы, но ни одно из них не является подмножеством другого
В М А
А М В
А = В
Множества А и В не пересекаются

Множество М = {а, b, с, d, ...} называется упорядоченным, если между его элементами установлено некоторое соотношение а < b (читают: "а предшествует b"), имеющее следующие свойства: 1) для каких-либо двух элементов а и b действительно одно и только одно из соотношений a = b, а < b, b > а; 2) для всяких трех элементов а, b и с из соотношений а > b и b > с следует соотношение а > с.

Комбинаторные задачи
Перестановки Сочетания Размещения Решение примеров и задач Правила комбинаторики Комбинаторный практикум Комбинации с повторением

Перестановки
Пусть мы имеем множество М, состоящее из n элементов: a₁, а₂, а₃, ..., аn. Если переставлять эти элементы всеми возможными способами, оставляя неизменным их общее число, получим несколько последовательностей: а1 а2 a3 ... an, а2 а1 а3 ... аn, аn а3 а2 ... a1 и т.д. Каждую из этих последовательностей называют перестановкой из данных n элементов.

Пример. Ниже приведены 6 всевозможных перестановок из букв а, b и с: abc, асb, bас, bса, cab, сbа. Итак, перестановкой из n элементов называется всякая конечная последовательность, которая получается в результате упорядоченности некоторого конечного множества, состоящего из n элементов. Если множество имеет некоторое число элементов, то его можно упорядочить несколькими способами. Число всех перестановок из n элементов обозначается Рn.

Это число равно произведению всех целых чисел от 1 до n включительно: Рn = 1 · 2 · 3 · 4 ... (n - 1) · n. Произведение n первых натуральных чисел принято обозначать символом n!: 1 · 2 · 3 · 4 · 5 · ... · n = n! Символ n! читают "эн факториал". Это слово происходит от латинского factor, что значит - множитель. Итак, Рn = n! Верна также следующая формула: Pn = n · Pn-1

Примечание.
При n = 1 в выражении 1 · 2 · 3, ... n остается одно число 1. Поэтому принимается (в качестве определения): 1! = 1. При n = 0 выражение 1 · 2, ..., n вовсе лишается смысла. Однако принимается (в качестве определения): 0! = 1.

Пример 1
Каким числом способов можно расставить 8 книг на полке из 8 мест? Решение: Р8 = 8! = 1 · 2 · 3 · 4 · 5 · 6 · 7 · 8 = 40320.

Сочетания - комбинации
Пусть имеем множество М, состоящее из n различных элементов. Всякое подмножество множества М, содержащее k элементов (k = 0, 1, 2, ..., n), называется сочетанием или комбинацией из данных n элементов по k элементов. Из определения следует, что два различных сочетания из данных n элементов по k элементов отличаются по крайней мере одним элементом.

Пример. Из множества цифр 1, 2, 3, 4 можно образовать такие сочетания по два элемента: 1, 2; 1, 3; 1, 4; 2, 3; 2, 4; 3, 4. Число различных сочетаний из n элементов по k обозначается символом: combinatio от combinare (лат.) - соединять Но иногда вместо пишут:

Число всех сочетаний из n элементов по k элементов, где 1 ≤ k ≤ n, равно произведению k последовательных натуральных чисел, из которых наибольшее есть n, деленному на произведение последовательных натуральных чисел от 1 до k

Формулу для можно записать в ином виде. Умножив числитель и знаменатель дроби в правой части ее на произведение 1 · 2 · 3 ... (n - k), получим: или

Примечание
Из n элементов можно составить только одно сочетание, содержащее все n элементов, поэтому Формула для дает это значение только в том случае, если принять 0! за 1. В качестве определения принимается, что Принято также считать, что

Пример 2
Из 15 туристов надо выбрать трех дежурных. Сколькими способами можно сделать этот выбор? Решение: Можно оформить решение более рационально:

Свойства сочетаний
1) Число сочетаний из n элементов по k элементов равно числу сочетаний из n элементов по n - k элементов, т.е. Это соотношение позволяет упростить нахождение числа сочетаний из n элементов по k, когда k превосходит Пример:

Свойства сочетаний
2) Число сочетаний из n элементов по k элементов равно числу сочетаний из n - 1 элементов по k элементов, прибавленному к числу сочетаний из n - 1 элементов по k - 1 элементов, т.е. правило Паскаля: Комбинаторные тождества:

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

Из трех цифр 1, 2, 3 можно образовать такие размещения по два: 1, 2; 2, 1; 1, 3; 3, 1; 2, 3; 3, 2. Число размещений из n элементов по k обозначается символом Arrangement (франц.) - размещения.

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

Пример 3
В классе 10 учебных предметов и 5 разных уроков в день. Сколькими способами могут быть распределены уроки в день? Решение: Всевозможные распределения уроков в день представляют собой, очевидно, всевозможные размещения из 10 элементов по 5; поэтому всех способов распределения должно быть:

Решение примеров и задач на соединения
n! = n(n-1)(n-2)…4·3·2·1

Упростить выражение: Решение:

2. Решить уравнение: Решение: (x + 1)(х + 2) = 110 или x2 + 3x - 108 = 0, Ответ: х = 9.

3. Решить систему уравнений: Решение: Ответ: n = 5, x = 5

3. Решить систему уравнений: Решение: Ответ: n = 5, x = 5

4. Число перестановок из n букв относится к числу перестановок из n + 2 букв, как 0,1 к 3. Найти n. Решение: По условию => (n + 1)(n + 2) = 30 n2 + 3n – 28 = 0 Ответ: n = 4

5. Число сочетаний из n элементов по 3 в 5 раз меньше числа сочетаний из n + 2 элементов по 4. Найти n. Решение: По условию => 20(n - 2) = n2 + 3n + 2 n2 – 17n + 42 = 0 Ответ: {3; 14}
Это выражение можно не записывать!

6. Сколькими разными способами собрание, состоящее из 40 человек, может избрать из своего числа председателя собрания, его заместителя и секретаря? Решение: Избрать определенные три человека из 40 человек можно так: а - председатель, а - секретарь, b - секретарь, b - председатель, с - зам. председателя; с - зам. председателя и т.д., => количество разных способов будет:

7. На плоскости расположено 10 точек так, что из них никакие 3, за исключением одной тройки точек, не лежат на одной прямой. Сколько разных прямых можно провести через эти точки? Решение: Если бы 3 точки не лежали на одной прямой, то всего можно было бы провести прямых. Если при этом 1 точка перемещается так, что будет на одной прямой с 2 другими точками, то из 3 разных прямых получим одну. Итак, всего прямых можно провести:

Правило умножения строгое
Если объект А1 может быть выбран n1 способами, затем для каждого из таких выборов объекта А1 другого объекта А2 может быть n2 способов, затем для каждого из таких выборов и объекта А1, и объекта А2 – III объект А3 может быть выбран n3 способами, и т.д., включая Аm, который может быть выбран nm способами, то объект, состоящий в выборе всех m объектов вместе, т.е. объект А1, и А2, и А3, … и Аm может быть выбран n1 · n2 · n3 · … · nm способами

Дерево возможных вариантов.
Проведенный перебор вариантов проиллюстрирован на схеме, изображенной на рисунке . Такую схему называют: дерево возможных вариантов.

Комбинаторное правило умножения
Пусть имеется n элементов и требуется выбрать один за другим некоторые m элементов. Если I элемент можно выбрать n1 способами, после чего II элемент можно выбрать из оставшихся элементов n2 способами, затем III элемент — n3 способами и т. д., то число способов, которыми могут быть выбраны все m элементов, равно произведению n1 · n2 · n3 · … · nm

Правило для 2-х элементов
Правило умножения, иначе называемое правилом «и» — одно из основных правил комбинаторики. Если элемент A можно выбрать n способами и, при любом выборе A (т.е. независимо), элемент B можно выбрать m способами, то пару (A, B) можно выбрать n · m способами.

A - n B - m
Пример 4
=> (A, B) - n · m
Когда в школе объявили день вежливости, каждый мальчик из VIII класса поздоровался с каждой девочкой из своего класса. Всего при этом было 77 рукопожатий. Сколько учеников может быть в VIII классе? Решение: Т.к. 77 = 7 • 11, то, по правилу умножения для комбинаторных задач, в классе может быть или 7 девочек и 11 мальчиков, или 7 мальчиков и 11 девочек, т.e. всего ребят 7 + 11 = 18 Ответ: 18

Пример 5
Из города А в город В ведут 2 дороги, из города В в город С - 3 дороги, из города С до пристани - 2 дороги. Туристы хотят проехать из города А через города В и С к пристани. Сколькими способами они могут выбрать маршрут? Схема задачи: Решение: Путь из А в В можно выбрать 2-мя способами. Далее в каждом случае можно проехать из В в С 3-мя способами. Значит, имеем 2 · 3 вариантов маршрута из А в С. Т.к. из С на пристань можно попасть 2-мя способами, то всего 2 · 3 · 2 = 12 способов выбора туристами маршрута из города А к пристани.

Правило сложения
Пусть даны m действий А1, А2, А3, …, Аm таких, что выполнение любого из них не зависит от выполнения остальных. Если: действие А1 можно выполнить n1 способами, А2 ------ n2 способами, -------------------------------, Аm ------ nm способами, то действие, состоящее в том, что выполняется одно любое из действий, можно выполнить n1 + n2 + …. + nm способами

Пример 6
Сколько существует делителей числа 210? Решение: 210 = 2 · 3 · 5 · 7 Число делителей из произведения 2-х простых множителей (6,10,14,15,21,35) из 3-х простых множителей (30,42,70,105) из простых делителей – 4 (2,3,5,7) еще делители 1 и 210 => по правилу сложения: 6 + 4 + 4 + 1 + 1 = 16

Комбинаторный практикум
1. Найти число диагоналей выпуклого десятиугольника. Решение: Вершины десятиугольника образуют совокупность 10 точек плоскости, из которых любые три не лежат на одной прямой. Соединяя всякую пару этих точек отрезком прямой, получаем отрезков, 10 из которых являются сторонами многоугольника, а другие 35 - его диагоналями.

2. Сколько возможных способов для образования дозора из трех солдат и одного офицера, если есть 80 солдат и 3 офицера? Решение: При одном офицере и 80 солдатах можно образовать дозор При 3-х офицерах число способов будет в 3 раза больше

3. В кафе предлагают два первых блюда: борщ, рассольник. И четыре вторых блюда: гуляш, кебаб, суши, пельмени. Укажите все обеды из двух блюд, которые может заказать посетитель. Проиллюстрируйте ответ, построив дерево возможных вариантов. Решение: Обозначим первые блюда Б, Р; вторые – Г, К, С, П. Имеем 4 выбора вторых и 2 выбора первых блюд. Значит существует 4·2=8 вариантов заказа обеда изданных блюд. Дерево возможных вариантов. +

4. Сколько возможных способов распределения 6 разных предметов между тремя лицами, так чтобы каждое из них получило 2 предмета? Решение: Одно лицо предметов Пусть лица А, В, С получили при одном способе распределения по два предмета так: А - аb, B - cd, С - ef. Поменяв местами собственников этих предметов, получим Р₃ способов распределения, что соответствует одной комбинации из 6 элементов по 2. Итак, всего способов распределения будет .

5. Сколько может быть случаев выбора двух карандашей и трех ручек из 5 разных карандашей и 5 разных ручек? Решение: Выбор Из 5 карандашей 2 карандаша – Из 5 ручек 3 ручки – =>

6. Среди сочетаний из 10 букв а, b, с, ... по 4 сколько таких, что не содержат букву а?, буквы а и b? Решение: Чтобы вычислить количество сочетаний из 10 букв а, b, с, ... по 4, которые не содержат буквы а, надо подсчитать число сочетаний из 9 букв b, с, ... по 4; их будет Тогда число сочетаний из 10 по 4, не содержащих букв а и b, будет

7. Сколько различных натуральных чисел можно составить из цифр 0, 1, 2, 3, 4, если в каждое число входит каждая из данных цифр не более одного раза? Решение: Различными однозначными числами, исключая нуль, будут Если бы среди данных цифр не было нуля, то число различных двузначных чисел было бы равно Но так как среди них есть нуль, то в числе размещений из этих пяти цифр по две есть однозначные числа, это те, которые начинаются с нуля. Число их равно Значит, различных двузначных чисел получится Аналогично найдем, что число различных трех-, четырех- и пятизначных чисел будет соответственно Всего получится 4 + 16 + 48 + 96 + 96 = 260 чисел.

8. В шахматном турнире двое из участников выбыли, сыграв по три партии каждый, и потому на турнире было сыграно всего 84 партии. Сколько было участников первоначально? Решение: Пусть искомое число участников турнира было х. Полностью сыграли друг с другом по партии лишь х-2 участников (двое выбыли) и число этих партий, очевидно, равно числу Это число партии вместе с шестью сыгранными двумя выбывшими участниками составило 84 партии. Отсюда получаем уравнение => x² - 5х - 150 = 0, x = 15; x = -10 не удовл. реш. зад. Ответ. 15. Примечание. В решении предполагается, что выбывшие игроки друг с другом не играли. Это действительно так, потому что уравнение не имеет решений.

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