Презентация. Комбинаторика

Комбинаторика

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

Основные понятия комбинаторики. Формулы.

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

Правило суммы:  если элемент А можно выбрать  п  способами, а элемент В можно выбрать  т способами, то выбрать либо А, либо В можно ( п  +  т ) способами.

Правило произведения (умножения ): если элемент А можно выбрать  п  способами, а элемент В можно выбрать  т  способами, то два элемента (пару) А и В можно выбрать  п  ·  т  способами.

Правило умножения верно и для любого конечного числа объектов. Пусть имеется  п  элементов и требуется выбрать один за другим некоторые  к  элементов. Если 1-й элемент можно выбрать  п 1  способами, после чего 2-й элемент можно выбрать из оставшихся  п 2  способами, затем 3-й – п 3  способами и т.д., то число способов, которыми могут быть выбраны  к  элементов, равно п 1  ·  п 2  ·…·  п к  .

Типы соединений: 1) Перестановки; 2) Размещения; 3) Сочетания.

Размещением  из nn элементов множества ХХ по kk элементам назовем любой упорядоченный набор (xi1,xi2,...,xik)(xi1,xi2,...,xik) элементов множества ХХ.

Если выбор элементов множества YY из ХХ происходит с возвращением, т.е. каждый элемент множества ХХ может быть выбран несколько раз, то число размещений из nn по kk находится по формуле nknk ( размещения с повторениями ).

Если же выбор делается без возвращения, т.е. каждый элемент множества ХХ можно выбирать только один раз, то количество размещений из nn по kk обозначается AknAnk и определяется равенством

Akn=n⋅(n−1)⋅...⋅(n−k+1)=n!(n−k)!.Ank=n⋅(n−1)⋅...⋅(n−k+1)=n!(n−k)!.

( размещения без повторений ).

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

Частный случай размещения при n=kn=k называется  перестановкой  из nn элементов. Число всех перестановок из nn элементов равно Ann=Pn=n!Ann=Pn=n!.

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

Р п  – число перестановок из  п  элементов

Р п  =  п !

п ! = 1 · 2 · 3 ·…· ( п –2)( п –1) п  (факториал)

Сочетания

Пусть теперь из множества ХХ выбирается неупорядоченное подмножество YY (порядок элементов в подмножестве не имеет значения).  Сочетаниями  из nn элементов по kk называются подмножества из kk элементов, отличающиеся друг от друга хотя бы одним элементом. Общее число всех сочетаний из nn по kk обозначается CknCnk и равно