КОМБИНАТОРИКА-раздел математики, посвящённый решению задач выбора и расположения элементов, обычно конечного, множества в соответствии с данными условиями.
Комбинаторику можно рассматривать как введение в теорию вероятностей, поскольку методы комбинаторики используются для решения многих вероятностных задач, в которых речь идет о подсчете числа возможных исходов и числа благоприятных исходов в различных конкретных случаях.
Определение 1: Под множеством понимают совокупность объектов, рассматриваемых как единое целое.
Определение 2: Объединением множеств А и В называется множество , которое состоит из всех элементов, принадлежащих хотя бы одному из множеств А или В, т.е.
{x/ x А или x В}.
Определение 3: Пересечением множеств А и В называется множество , ех элементов, принадлежащих и множеству А, и множеству В, т.е.
{x/ x А и x В}.
Правило суммы.
Теорема 1.1. (Правило суммы для двух множеств). Пусть даны два конечных непересекающихся множества А={а1, а2,…,ар} и В={b1, b2,…,bq}, т.е. n(A)=p, n(B)=q и А∩В=0. Тогда элемент, принадлежащий А или В, можно выбрать p+q способами.
Правило суммы также легко распространяется на тот случай, когда число попарно непересекающихся множеств больше двух.
Теорема 1.1’ (Правило суммы).Пусть даны m действий x1,x2,….,xm таких, что выполнение любого из них не зависит от выполнения других действий. Если действие x1 можно выполнить k1 способами (i=1,2,…,m), тогда действие, состоящее в том, что выполняется любое из данных действий, можно выполнить k1+k2+….+km= способами.
Пример. В вазе 6 белых цветов, 9 красных и 5 желтых. Сколькими способами можно взять из вазы один цветок?
Решение: Белый цветок можно выбрать 6 способами, красный-9, желтый-5. На основании правила суммы заключаем, что или белый, или красный, или желтый цветок можно выбрать из вазы 6+9+5 способами.
Ответ:21.
Правило произведения.
Теорема 1.2. (Правило произведения для двух множеств). Пусть даны два конечных непересекающихся множества А={а1, а2,…,ар} и В={b1, b2,…,bq}, т.е. n(A)=p, n(B)=q и А∩В=0. Тогда число упорядоченных пар, первая компонента которых принадлежит А, а вторая-В, можно составить pq способами.
Правило произведения также легко распространяется на случай кортежа любой длины.
Теорема 1.2’ (Правило произведения).Пусть элемент x1 можно выбрать k1 способами , то кортеж (x1,x2,…,xm) можно составить k1k2….km способами.
Пример: Если F1={0}, F2={1}, F3={0, 1}, то n( )= .
|
