Презентация "Комбинаторика" по математике – проект, доклад

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

КОМБИНАТОРИКА

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

(1646 - 1716 )

Готфрид Вильгельм Лейбниц

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

Основное правило комбинаторики (правило умножения)

Если некоторый выбор А можно осуществить m различными способами, а для каждого из этих способов другой выбор В можно осуществить n способами, то выбор А и В можно осуществить mn способами.

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

Основное правило комбинаторики в общем виде

Пусть требуется выполнить одно за другим k действий. Если первое действие можно выполнить n1 способами, второе действие – n2 способами, третье – n3 способами и так до k –го действия, которое можно выполнить nk cпособами, то все k действий вместе могут быть выполнены n1 x n2 x n3 x ….x nk

Пример 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 элементов равно 2n.

Термин “сочетание” впервые встречается у Блеза Паскаля в 1665 году. C – первая буква французского слова combinasion – сочетание.

(1623-1662)

Термин «факториал» ввел в 1800 году французский математик Аргобаст Луи Франсуа Антуан (1759-1803).

N! n! (n-факториал) – произведение всех натуральных чисел от 1 до n включительно. n! = 1 х 2 х 3 х ….. х n 0!=1 1! = 1

Обозначение n! придумал чуть позже французский математик Кристиан Крамп (1760-1826) в 1808 году.

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

Перестановки

Множество называется упорядоченным, если каждому элементу этого множества поставлено в соответствие некоторое число (номер элемента) от 1 до n, где n – число элементов множества, так что различным элементам соответствуют различные числа. Перестановки – различные упорядоченные множества, которые отличаются лишь порядком элементов.

Термин “перестановка” употребил впервые Якоб Бернулли в книге «Искусство предположений». Р – первая буква французского слова permutation – перестановка.

(1654-1705)

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

Размещения

Размещения из n элементов по k – упорядоченные k-элементные подмножества множества из n элементов. Различные размещения отличаются количеством элементов или их порядком. A – первая буква французского слова arrangement - размещение.

Число всех k-элементных подмножеств множества А равно

Каждое такое подмножество можно упорядочить k! способами. Значит, число размещений из n по k равно

Пример 7 Сколькими способами можно рассадить 4 учащихся на 25 мест?

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

Сочетания с повторениями

Пример 8 Сколько наборов из 7 пирожных можно составить, если в продаже имеется 4 сорта пирожных?

Перестановки с повторениями

Рассматривая перестановки ранее, мы предполагали, что n элементов различны. Если среди n элементов есть n1 элемент одного вида, n2 элементов другого вида и т.д., nk элементов k-го вида, то имеем перестановки с повторениями, их число:

Пример 9 Сколько различных «слов» можно составить из букв слова ДЕД? n=3, k=2, n1=2, n2=1

Размещения с повторениями

Размещения из n элементов, в каждое из которых входит m элементов, причём один и тот же элемент может повторяться в каждом размещении любое число раз, но не более m называются размещениями из n элементов по m с повторениями.

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