Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Элементы комбинаторики

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

Это выражение называют основной формулой комбинаторики.

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

Заметим, что в любом случае результат выбора m элементов из группы, содержащей n элементов, будем называть выборкой.

Определение. Выборку, в которой не учитывают порядок выбора элементов, называют сочетанием, а выборку, в которой учитывают порядок выбора элементов, − размещением. При этом если рассматривают выборку с возвращением, то сочетание (размещение) называют сочетанием (размещением) с повторениями, а если рассматривают выборку без возвращения, то сочетание (размещение) называют сочетанием (размещением) без повторений, или просто сочетанием (размещением).

Замечание. Размещение без повторений из n элементов по n элементов называют перестановкой из n элементов.

Теорема. Число размещений (без повторений) из n элементов по m определяется формулой

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

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

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