Презентація на тему «Комбинаторика»

Презентация на тему: «Комбинаторика»
Выполнила: ученица 11 Б класса
ЗМЛ№99
Шевченко Анжела
Учитель: Летунова Валентина Петровна

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

История
Некоторые элементы комбинаторики были известны в Индии еще во II в. До н. э. Индийцы умели вычислять числа, которые сейчас называют «сочетания». Предполагают, что индийские ученые изучали соединения в связи с применением их в поэтике, науке о структуре стиха и поэтических произведениях. Как научная дисциплина, комбинаторика сформировалась в XVII в.

Б. Паскаль в «Трактате об
арифметическом треугольнике» и в
«Трактате о числовых порядках» (1665 г.) изложил учение о биномиальных коэффициентах.
П. Ферма знал о связях математических квадратов и фигурных чисел с теорией соединений.
Термин «комбинаторика» стал употребляться
после опубликования Лейбницем в
1665 г. Работы «Рассуждение
комбинаторном искусстве», в которой
впервые дано научное обоснование теории сочетаний и перестановок.

Правило суммы и правило произведения
Правило суммы. Если объект А можно выбрать n способами, а объект B можно выбрать m способами, то объект А или B можно выбрать n+m способами.
Правило произведения. Если объект А можно выбрать n способами, а объект B можно выбрать m способами, то объект А и B можно выбрать n*m способами.

Примеры
В магазине имеется 5 видов упаковок конфет и вида коробок печенья.
Определите сколькими способами можно составить подарок из одной упаковки конфет или одной коробки печенья.
Определите сколькими способами можно составить в подарок набор из одной коробки конфет и одной коробки печенья.
Ответ на первый вопрос: 9=5+4, ответ на второй вопрос: 20=5*4.

Ученик должен выполнить практическую работу по математике. Ему предложили на выбор 17 тем по алгебре и 13 тем по геометрии. Сколькими способами он может выбрать одну тему для практической работы?
Решение: n=17, m=13. По правилу суммы n+m=17+13=30 .
Ответ на вопрос: 30 тем.
Имеется 5 билетов денежно-вещевой лотереи, 6 билетов спортлото и 10 билетов автомотолотереи. Сколькими способами можно выбрать один билет?
Решение:5+ 6+10=21.
Ответ на вопрос: 21 способами.

Интересные случаи
Сколько существует пятизначных чисел, которые одинаково читаются слева направо и справа налево?
В таких числах последняя цифра будет такая же, как и первая, а предпоследняя - как и вторая. Третья цифра будет любой. Числа такого вида можно представить в виде XYZYX, где Y и Z - любые цифры, а X - не ноль. Значит, по правилу произведения количество чисел, одинаково читающихся как слева направо, так и справа налево равно 9*10*10=900.
Все вышесказанное относиться к множествам, которые не имеют общих элементов, т.е. в примере с конфетами и печеньем в множестве коробок конфет не могли оказаться коробки с печеньем, а в множестве коробок с печеньем не могли оказаться коробки конфет.

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

Теперь все множество группы разбито на три непересекающихся множества:
А – множество тех, кто изучает только немецкий язык (красная область),
B – множество тех, кто изучает только английский язык (зеленая область),
C – множество тех, кто изучает и немецкий и английский языки (белая область).
Пока нам известна мощность только множества С, |C|=5. Учитывая, что немецкий язык всего изучает 10 человек, из них 5 изучает и английский, можно сделать вывод, что только немецкий язык изучает 5 человек, т.е. мощность множества А равна 5. Аналогично, мощность множества В равна 15.
Итого |A|+|B|+|C|=5+5+15=25.

Размещения без повоторений
Пусть задано n-элементное множество M. Размещением n-элементного множества M по k называется любое упорядоченное подмножество из k элементов множества M.
 Количество размещений из n по k обозначается     и
находится по формуле , где n! (n-факториал) – произведение чисел натурального ряда от 1 до числа n включительно.n!=1*2*3*...*n          
0!=1 Сколько можно составить телефонных номеров из 6 цифр каждый, так чтобы все цифры были различны?
Это пример задачи на размещение без повторений.

Размещаются здесь 10 цифр по 6. А варианты, при которых одинаковые цифры стоят в разном порядке считаются разными.
 Если X-множество, состоящие из n элементов, m≤n, то размещением без повторений из n элементов множества X по m называется упорядоченное множество X, содержащее m элементов называется упорядоченное множество X, содержащее m элементов.
Количество всех размещений из n элементов по m обозначают 
Значит, ответ на выше поставленную задачу будет

Перестановки без повторений
Пусть задано n-элементное множество M. Перестановкой n-элементного множества M называется любое размещение множества М по n.
Пример: Составьте все возможные перестановки {a, b, c}. (a, b, c), (a, c, b), (b, c, a), (c, a, b), (c, b, a), (b, a, c). Всего таких перестановок 6.
Количество всех перестановок n-элементного множества обозначается и находится по формуле .
Пример: Сколько различных шестизначных чисел можно составить из цифр 0, 1, 2, 3, 4,5, если цифры в числе не повторяются?
Найдем количество всех перестановок из этих цифр:
0 не может являться первой цифрой шестизначного числа, поэтому определим количество перестановок, первый элемент которых 0. Если 0 зафиксировать на первой позиции, то переставляться будут только остальные пять цифр, поэтому таких перестановок всего.

Сочетания без повторений
Пусть задано n-элементное множество M. Сочетанием n-элементного множества M по k называется любое неупорядоченное подмножество из k элементов множества M.
Пример: Составьте все возможные сочетания по 2 множества {a, b, c}.{a, b}{a, c}{b, c}. Всего таких сочетаний 3.
Таким образом, количество вариантов при сочетании будет меньше количества размещений.
 Количество всех сочетаний из n по k обозначается    и находится по формуле:    .

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

Свойства количества сочетаний
1.
2.
3.

Свойства количества сочетаний
1.
2.
3.

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

Пример:  Раскройте скобки   .Воспользуемся формулой бинома Ньютона:
Найдем биноминальные коэффициенты.
Подставим биноминальные коэффициенты в формулу: