![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Правило произведения
В математике важную роль играют комбинаторные задачи, связанные с подсчетом числа элементов различных конечных множеств, перебором конечного числа вариантов и т.п. Одним из основных правил, которые применяются при решении таких задач, является правило произведения. Пусть элемент З а м е ч а н и е: Это правило распространяется и на Приведем примеры решения комбинаторных задач с помощью правила произведения. З а д а ч а 1. Пусть дан упорядоченный набор длины
Следовательно, число двоичных наборов длины n равно З а д а ч а 2. Пусть дано множество Перестановки, размещения и сочетания Перестановки. Одна из наиболее распространенных комбинаторных задач такова: сколькими способами можно переставить элементы некоторого конечного множества? Например: сколько 9-значных чисел с различными цифрами можно составить из цифр 1, 2, 3, 4, 5, 6, 7, 8, 9? При каждой перестановке n- элементного множества образуется упорядоченный набор длины n, все элементы которого различны. Число всех возможных перестановок в данном множестве совпадает с числом всех таких наборов. О п р е д е л е н и е 4: Перестановкой из n элементов называется упорядоченный набор длины n с различными элементами, взятыми из некоторого n- элементного множества. Число перестановок из n элементов обозначают Рn. Выведем формулу для вычисления Рn. Пусть некоторое множество М состоит из n элементов. Рассмотрим произвольную перестановку элементов этого множества, то есть упорядоченный набор ( Произведение Получена формула числа перестановок из n элементов. Применяя эту формулу, можно, в частности, получить, что из цифр 1, 2, 3, 4, 5, 6, 7, 8, 9 можно составить 9!, то есть 362880 9-значных чисел с различными цифрами. Размещения. Другой важный тип комбинаторной задачи можно продемонстрировать на следующем примере: сколькими способами из 10 учебных предметов можно составить расписание занятий на один день, включив в него 4 различных предмета? Очевидно, что один вариант расписания может отличаться от другого как предметами, так и порядком их следования. Поэтому данную задачу можно сформулировать так: сколько существует упорядоченных наборов длины 4 с различными элементами, взятыми из 10-элементного множества? Число всех таких наборов называется числом размещений из 10 элементов по 4. О п р е д е л е н и е 5: Размещением из n элементов по m (m≤ n) называется упорядоченный набор длины m различными элементами, взятыми из некоторого n -элементного множества. Еще раз напомним, что упорядоченные наборы с одними и теми же элементами, но разным порядком их следования считаются различными. Обозначим число размещений из n элементов по n через Рассмотрим n -элементное множество M и произвольный упорядоченный набор ( Искомая формула имеет вид:
Заметим, что произведение в правой части состоит в точности из m множителей. Это облегчает применение формулы. Вернемся к задаче о расписании. Число всех вариантов расписания можно посчитать по формуле (1): Имеет место другая формула для Для ее вывода достаточно преобразовать правую часть формулы (1). Сочетания. Рассмотрим теперь такую задачу: сколькими способами можно из 10 учебных предметов выбрать 4 для составления расписания на день? Заметим, что в этой задаче, в отличие от задачи предыдущего пункта, не требуется составлять расписание, то есть упорядочивать предметы. Нужно узнать, сколькими способами из множества, состоящего из 10 элементов, можно выбрать 4-элементное подмножество (а не упорядоченный набор). Число таких подмножеств называют числом сочетаний из 10 элементов по 4. О п р е д е л е н и е 6: Сочетанием из n элементов по m Подчеркнем, что в данном случае не различаются подмножества, состоящие из одних и тех же элементов, в каком бы порядке эти элементы не перечислялись. Число сочетаний из n элементов по m обозначают Пусть дано множество из n элементов. Возьмем произвольное m -элементное подмножество этого множества и составим из него все возможные упорядоченные наборы. Их будет m! Проделав такое действие с каждым подмножеством, получим множество всех упорядоченных наборов длины m, то есть всех размещений из n элементов по m. Их число Таким образом,
Иногда последнюю формулу записывают по-другому:
Применив полученную формулу, найдем
Число 210 дает ответ задачи, поставленной в начале этого пункта.
|