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

Комбинаторика (или теория соединений) - раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, удовлетворяющих тем или иным условиям, можно составить из заданных объектов. Комбинаторика решает задачи выбора и расположения элементов, обычно конечного множества в соответствии с заданными условиями.

Решение большинства комбинаторных задач основано на двух основных правилах, которые называют правилами суммы и произведения.

Правило суммы. Если объект а можно выбрать m способами, а объект b можно выбрать k способами, отличными от способа выбора объекта a, то выбор «либо a, либо b » можно осуществить m+k способами. Правило суммы распространяется на тот случай, когда число попарно непересекающихся множеств более двух.

Правило произведения. Если объект а можно выбрать n способами, и если после каждого такого выбора объект b можно выбрать m способами, то выбор «a и b » можно осуществить n m способами. Правило произведения распространяется на случай выбора кортежа любой длины.

Факториал – функция, определённая на множестве целых неотрицательных чисел, значение которой равно произведению натуральных чисел от 1 до донного числа n, т.е. 1 2 3 … n; обозначается n!; по определению 0! = 1, 1! = 1.

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

Теорема. Число различных перестановок из n элементов равно произведению последних натуральных чисел от 1 до n включительно, то есть

Р = 1 2 3 … n = n!

Всякое упорядоченное k – элементное подмножество n – элементного множества ( k n ) называется размещением из n элементов по k и обозначают символом А.

Теорема. Число различных размещений из n элементов по k равно произведению k последовательных натуральных чисел, наибольшим из которых является n, то есть

А = n ( n - 1 ) ( n – 2 ) … ( n – k + 1 ) или А = .

Всякое k – элементное подмножество n – элементного множества (kn) называется сочетанием из n элементов по k и обозначают символом C.

Теорема. Число сочетаний из n элементов по k элементов определяется по формуле:

C = .

Размещением с повторениями из k элементов по m элементов – это кортеж, составленный из m элементов k-элементного множества.

Число всевозможных размещений с повторениями из k элементов по m элементов обозначают и подсчитывают по формуле

.

Набор из n элементов, составленный из повторяющихся элементов m элементного множества, называется сочетанием с повторениями из m по n и обозначают символом .

Другое по теме:

Методика изучения свойств степеней и логарифмов. Введение определения показательной школе показательной функций, ее свойства и их приложения
Ознакомление учащихся с показательной и логарифмической функциями начиная с изучения свойств степеней и логарифмов. Курс алгебры знакомит учащихся с понятием степени с рациональным показателем. Таким образом для любого основания степени (где , ). Можно построить функцию: , , область определения кот ...

Возрастные особенности младших школьников
Рассмотрим возрастные особенности детей младшего школьного возраста. Рост и вес - в возрасте от 6 до 12 лет большинство детей прибавляет в росте 5-7 см в год. Средний рост 6-ти летних детей составляет лишь 1.22 м, к подростковому возрасту он увеличивается до 1.52 м. Обычно в 6 лет девочки немного н ...

Диагностика игровой деятельности умственно отсталых детей
Для выявления уровня развития игровой деятельности у детей был использован такой метод исследования как наблюдение. Были использованы следующие методики: диагностика игровой деятельности по Г.А. Уруптовой и диагностика уровня развития игровой деятельности по Д.Б. Эльконину. Исследование проводилось ...