Математика. Комбинаторика. Принцип сложения. Примеры + решения.

Комбинаторика.

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

Пример.

Выборкой объема  из множества  называется всякая последовательность из  элементов множества .

Если элементы в выборке не повторяются, то выборка называется бесповторной, иначе – выборкой с повторениями

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

 

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

 

 

Рассмотрим бесповторную выборку

 

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

Например, на множестве из трех элементов  возможны следующие перестановки: .

Число различных перестановок без повторений из  элементов обозначается  и равно , т.е.

Сочетанием без повторений из  элементов по называется неупорядоченное -элементное подмножество -элементного множества. Число сочетаний без повторений из  элементов по   равно :

Например, требуется подсчитать, сколькими способами можно составить бригаду из трех человек для дежурства в  группе из 30 человек. Поскольку порядок расположения людей в бригаде не фиксируется и люди не повторяются, то мы имеем случай сочетаний из 30 элементов по 3 без повторений:

.

Таким образом, бригаду дежурных из трех человек в группе из 30 человек можно выбрать 4060 различными способами.

В вазе лежит 5 яблок, 4 груши и 3 мандарина. Сколько существует возможностей взять один фрукт из вазы?   Если взять яблоко, то существует 5 возможностей, если взять грушу, то существует 4 возможности, если взять мандарин, то существует 3 возможности. Значит, чтобы взять один фрукт из всех лежащих в вазе, существует 5+4+3=12 возможностей.   Этот пример можно обобщить.   Допустим, что есть две группы: в одной k различных элементов, во второй n различных элементов. Если из первой группы какой-либо элемент можно выбрать k способами, а из второй n способами, то выбрать один элемент из первой или второй группы можно k+n способами. Это называется законом сложения в комбинаторике. Закон сложения также используется, если нужно выбрать элемент из трёх, четырёх и т.д. групп.   Закон сложения используется тогда, когда нужно выбрать только 1 элемент. Чтобы использовать закон сложения: 1. нужно понять, каковы группы, из которых нужно выбрать 1 элемент; 2. нужно выяснить количество элементов в каждой группе; 3. нужно убедиться, что в различных группах, из которых выбирают элемент, нет одинаковых элементов.   Пример: Вика должна выбрать только один десерт из 8 видов коктейля, 5 видов мороженого и 5 видов йогурта. Сколькими способами она может выбрать десерт? Решение: Используется закон сложения, т.к. Вика должна выбрать или коктейль, или мороженое, или йогурт. 8+5+5=18 Ответ: Вика может выбрать десерт 18 способами. При использовании закона сложения надо следить, чтобы ни один из способов выбора объекта a не совпадал с каким-либо способом выбора объекта b.  Если такие совпадения есть, то закон сложения утрачивает силу, и мы получаем лишь (k+n−m) способов выбора, где m — число совпадений. Итак: Если объект a можно получить k способами, объект b — n  способами, то объект «a или b» можно получить k+n−m способами, где m — это количество повторяющихся способов. Пример: В группе 7 человек имеют «5» по математике, 9 человек — «5» по философии. В сессии 2 экзамена. Известно, что 4человека сдали сессию отлично. Сколько человек имеют хотя бы одну пятерку в сессии? Решение: 7+9−4=12