28. Элементы комбинаторики. Схема выбора без возвращения.

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

Каждая из задач на использование комбинаторных формул определяет число всевозможных исходов в некотором опыте, состоящем в выборе на удачу m элементов из n элементов.

Существует две схемы выбора элементов:

1. Схема без возвращения выбранного элемента.

2. Схема с возвращением выбранного элемента.

Схема выбора без возвращения.

Определение. Пусть дано множество из n различных элементов. Размещениями из n элементов по m элементам () называются комбинации, составленные из данных n элементов по m элементов, которые отличаются либо самими элементами, либо порядком элементов.

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

(1)

Например, из трех элементов a, b, c можно составить по два элемента следующие размещения: ab, ac, bc, ba, ca, cb.

Определение. Перестановками из n различных элементов называют размещения из этих n элементов по m.

Из определения следует, что перестановки можно считать частным случаем размещений при m = n.

(2)

Пример. Сколькими способами можно расставить на полке 5 книг.

Определение. Сочетаниями из n различных элементов по m элементов называются комбинации, составленные из данных n элементов по m элементов, которые отличаются хотя бы одним элементом.

В сочетаниях в отличие от размещений не учитывается порядок элементов.

(3)

Отметим особенность формулы (3): .

Пример. Сколькими способами можно выбрать 3 цветка из вазы, в котором стоят 10 красных и 4 розовых гвоздики. А если выбрать 1 красную и 2 розовые гвоздики.

1)

2) , , .

29. Элементы комбинаторики. Схема выбора с возвращением.

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

Каждая из задач на использование комбинаторных формул определяет число всевозможных исходов в некотором опыте, состоящем в выборе на удачу m элементов из n элементов.

Существует две схемы выбора элементов:

1. Схема без возвращения выбранного элемента.

2. Схема с возвращением выбранного элемента.

Схема выбора с возвращения.

Определение. Если при выборке m элементов из n элементов сами элементы возвращаются обратно и упорядочиваются, то такое размещение называется размещением с повторениями.

Определяются и обозначаются следующим образом:

(1)

Пример. Из элементов a, b, c составить все размещения по два элемента с повторениями.

ab, ac, bc, ba, ca, cb, aa, bb, cc. .

Размещения с повторениями могут отличаться друг от друга элементами, их порядком, количеством повторений элементов.

Определение. Если при выборке m элементов из n элементов элементы возвращаются обратно без последующего упорядочивания, то говорят, что это сочетания с повторениями.

Определяются и обозначаются следующим образом:

(2)

Пусть в множестве с n элементами есть k различных элементов. При этом первый элемент повторяется , второй – раз и так далее, причем

Определение. Перестановки из n элементов данного множества называется перестановками с повторением.

(3)