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

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

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

Правило суммы. Если объект а можно выбрать 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 и обозначают символом .

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

Физиологические закономерности обучения движениям школьников
Формирование произвольных движений у школьников происходит при активном участии сознания. Эффективность обучения зависит от понимания значения разучиваемых упражнений, от интереса учащихся, от соответствия методов обучения возрастным особенностям детей. Двигательная деятельность человека тесно связ ...

Технологизация образования
Педагогика современности испытывает огромную потребность в смыслорождающих авторских обучающих и воспитательных технологиях, что является как следствием, так и выражением личностной парадигмы творческой, поисковой самореализации педагога. Обучение в своей генеральной направленности должно способств ...

Перцептивная модальность как средство формирования интонационной выразительности речи
Значение живого устного слова неоспоримо, так как лекция, доклад, беседа, выступление – любые формы устного повествования – являются повседневным явлением в нашей жизни. Устная речь всегда имеет большой запас средств для передачи мыслей и чувств: это и мимика, и жесты, и интонация, и т.д. В то же в ...