Презентация по теме: "Комбинаторика"

Слайд 1

Слайд 2

Комбинаторика — математический раздел, изучающий вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов. Комбинаторика связана со многими другими областями математики — алгеброй, геометрией, теорией вероятностей, и имеет широкий спектр применения, например в информатике и статистической физике. Термин « комбинаторика » был введён в математический обиход Лейбницем , который в 1666 году опубликовал свой труд - «Рассуждения о комбинаторном искусстве». Г.В. Лейбниц История комбинаторики

Слайд 3

Формирование комбинаторики Комбинаторика занимается различного вида соединениями, которые можно образовать из элементов конечного множества. Некоторые элементы комбинаторики были известны в Индии еще во II в. до н. э. Индийцы умели вычислять числа, которые сейчас называют "сочетания". В XII в. Бхаскара вычислял некоторые виды сочетаний и перестановок. Предполагают, что индийские ученые изучали соединения в связи с применением их в поэтике, науке о структуре стиха и поэтических произведениях. Например, в связи с подсчетом возможных сочетаний ударных (долгих) и безударных (кратких) слогов стопы из n слогов. Как научная дисциплина, комбинаторика сформировалась в XVII в. Б. Паскаль в "Трактате об арифметическом треугольнике" и в "Трактате о числовых порядках" (1665 г.) изложил учение о биномиальных коэффициентах. П. Ферма знал о связях математических квадратов и фигурных чисел с теорией соединений. Изучением размещений впервые занимался Я. Бернулли во второй части своей книги "Ars conjectandi" (искусство предугадывания) в 1713 г. Современная символика сочетаний была предложена разными авторами учебных руководств только в XIX в.

Слайд 4

Для формулировки и решения комбинаторных задач используют различные модели комбинаторных конфигураций (размещение, перестановку, сочетание, композицию числа и разбиение числа) Но всё разнообразие комбинаторных формул может быть выведено из двух основных утверждений, касающихся конечных множеств – правило суммы и правило произведения .

Слайд 5

Правило суммы Если некоторый объект A можно выбрать m способами, а другой объект В можно выбрать n способами, то выбор «либо А, либо В» можно осуществить (m+n) способами. При использовании правила суммы надо следить, чтобы ни один из способов выбора объекта А не совпадал с каким-либо способом выбора объекта В. Если такие совпадения есть, правило суммы утрачивает силу, и мы получаем лишь (m + n - k) способов выбора, где k—число совпадений.

Слайд 6

Примеры задач на правило суммы Пример 1 Если на первой полке стоит X книг, а на второй Y , то выбрать книгу с первой или второй полки, можно X+Y способами. Пример 2 Ученик должен выполнить практическую работу по математике. Ему предложили на выбор 17 тем по алгебре и 13 тем по геометрии. Сколькими способами он может выбрать одну тему для практической работы? Решение: По правилу суммы получаем 17+13=30 вариантов.

Слайд 7

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

Слайд 8

Примеры задач на правило произведения Пример 1 Если на первой полке стоит 5 книг, а на второй 10, то выбрать одну книгу с первой полки и одну со второй можно 5*10=50 способами. Пример 2 Переплетчик должен переплести 12 различных книг в красный, зеленый и коричневые переплеты. Сколькими способами он может это сделать? Решение. Имеется 12 книг и 3 цвета, значит по правилу произведения возможно 12*3=36 вариантов переплета.

Слайд 9

Факториал Факториал числа n ( n !) — произведение всех натуральных чисел до n включительно. Например: 3!=1*2*3=6 5!=1*2*3*4*5=120 Это понятие очень часто употребляется в комбинаторике.

Слайд 10

Перестановки Перестановка из n элементов – каждое расположение этих элементов в определённом порядке . Pn = 1*2*3...= n! - перестановка Задача: Сколькими способами можно рассадить 4-х человек на четыре места? Р4 = 4! = 1*2*3*4= 24 способа

Слайд 11

Сочетания Сочетаниями из n элементов по m элементов называются комбинации, составленные из данных n элементов по m элементов, которые различаются хотя бы одним элементом (отличие сочетаний от размещений в том, что в сочетаниях не учитывается порядок элементов). Число сочетаний без повторений (n различных элементов, взятых по m) вычисляется по формуле (1): Число сочетаний c повторениями (n элементов, взятых по m, где элементы в наборе могут повторяться) вычисляется по формуле(2):

Слайд 12

Пример . Возьмем буквы Б, А, Р . Какие сочетания из этих букв, взятых по две, можно получить? Сколько таких наборов получится, если: 1) буквы в наборе не повторяются; 2) можно брать по два одинаковые буквы. Решение . 1) Получатся наборы: БА ( БА и АБ - один и тот же набор), АР и РБ По формуле 1 получаем: наборов. 2) Получатся наборы: ББ, БА, БР, АА, АР, РР. По формуле 2 получаем: 6 наборов.