«Число, положение и комбинаторика – три взаимно пересекающиеся, но различные сферы мысли, к которым можно отнести все математические идеи» Джозеф Сильвестр (1844 г.) КОМБИНАТОРИКА

КОМБИНАТОРИКА - это раздел математики, в котором изучаются различного рода соединения элементов: перестановки, размещения, сочетания. Термин «комбинаторика» происходит от латинского слова «combina», что в переводе на русский означает – «сочетать», «соединять».

( ) Готфрид Вильгельм Лейбниц Лейбниц впервые ввёл термин «комбинаторика» и стал рассматривать комбинаторику как самостоятельный раздел математики.

Основное правило комбинаторики ( правило умножения ) Если некоторый выбор А можно осуществить m различными способами, а для каждого из этих способов другой выбор В можно осуществить n способами, то выбор А и В можно осуществить mn способами. Пример 1 К площади с неким памятником ведёт 6 улиц. По четырём из них разрешено двустороннее движение, а по двум одностороннее – к площади. Водитель собирается приехать на площадь, посмотреть на памятник, а затем покинуть площадь. Каким числом способов он может это сделать? 6 способов попасть на площадь и 4 способа уехать с площади. Значит, всего 6 х 4 = 24 способа.

Основное правило комбинаторики в общем виде Пусть требуется выполнить одно за другим k действий. Если первое действие можно выполнить n 1 способами, второе действие – n 2 способами, третье – n 3 способами и так до k –го действия, которое можно выполнить n k cпособами, то все k действий вместе могут быть выполнены n 1 x n 2 x n 3 x ….x n k Пример 2 Сколько четырёхзначных чисел можно составить из цифр 0,1,2,3,4,5, если: а) ни одна из цифр не повторяется более одного раза; б) цифры могут повторяться. а) Для первой цифры 5 вариантов – 1,2,3,4,5 (0 не может быть). Для второй цифры 5 вариантов, для третьей 4 варианта, для четвёртой 3 варианта. 5х5х4х3 = 300 чисел. б) 5 возможностей для первой цифры, 6 вариантов для других: 5х6х6х6 = 1080 чисел.

Сочетания Сочетания Сочетание из n элементов по k - произвольное k-элементное подмножество n-элементного множества (комбинация). Порядок элементов в подмножестве не имеет значения. Число всех подмножеств множества из n элементов равно 2 n. Термин сочетание впервые встречается у Блеза Паскаля в 1665 году. C – первая буква французского слова combinasion – сочетание. ( )

Термин «факториал» ввел в 1800 году французский математик Аргобаст Луи Франсуа Антуан ( ). N! n! (n-факториал) – произведение всех натуральных чисел от 1 до n включительно. n! = 1 х 2 х 3 х ….. х n 0!=1 1! = 1 Обозначение n! придумал чуть позже французский математик Кристиан Крамп ( ) в 1808 году.

Пример 3 Сколькими способами читатель может выбрать 3 книжки из 5? Число способов равно числу трёхэлементных подмножеств из 5 элементов: Пример 4 Сколькими способами из 7 судей можно выбрать комиссию, состоящую из 3 человек? Сочетания Сочетания

Перестановки Перестановки Множество называется упорядоченным, если каждому элементу этого множества поставлено в соответствие некоторое число (номер элемента) от 1 до n, где n – число элементов множества, так что различным элементам соответствуют различные числа. Перестановки – различные упорядоченные множества, которые отличаются лишь порядком элементов. Термин перестановка употребил впервые Якоб Бернулли в книге «Искусство предположений». Р – первая буква французского слова permutation – перестановка. ( )

Пример 5 Перестановки множества А={a, b, c} из трёх элементов имеют вид: (a, b, c); (b, c, a); (c, a, b); (a, c, b); (b, a, c); (c, b, a), т. е. P 3 = 3! = 1х2х3 = 6 перестановок. Пример 6 Сколькими способами можно разместить на полке 4 книги? P 4 = 4! = 1х2х3х4 = 24 способа. Перестановки Перестановки

Размещения Размещения Размещения из n элементов по k – упорядоченные k-элементные подмножества множества из n элементов. Различные размещения отличаются количеством элементов или их порядком. A – первая буква французского слова arrangement - размещение. Число всех k-элементных подмножеств множества А равно Каждое такое подмножество можно упорядочить k! способами. Значит, число размещений из n по k равно Пример 7 Сколькими способами можно рассадить 4 учащихся на 25 мест?

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

Перестановки с повторениями Перестановки с повторениями Рассматривая перестановки ранее, мы предполагали, что n элементов различны. Если среди n элементов есть n 1 элемент одного вида, n 2 элементов другого вида и т.д., n k элементов k-го вида, то имеем перестановки с повторениями, их число: Пример 9 Сколько различных «слов» можно составить из букв слова ДЕД? n=3, k=2, n 1 =2, n 2 =1

Размещения с повторениями Размещения с повторениями Размещения из n элементов, в каждое из которых входит m элементов, причём один и тот же элемент может повторяться в каждом размещении любое число раз, но не более m называются размещениями из n элементов по m с повторениями. Пример 10 Телефонные номера одной фирмы состоят только из цифр 2,3,5,7. Сколько всего может быть телефонных номеров, если каждый номер семизначный?