Мощность множества, правила суммы, произведения, степени
+ (-1 )
| Х
) Х
)…)Х
|
Замечание. Правило суммы является следствием этой формулы.
Основной принцип комбинаторики.
Если А ~ В , то | А | = | В |. Этот принцип является главным рабочим инструментом комбинаторики, т.е. он позволяет переносить изучение свойств с одного множества на другое, когда природа элементов не важна. Например, если | А | = n, то с элементами множества А можно работать как с числами 0, 1, …, n-1.
Задача. Из города А в город В ведет три дороги, а из города В в город С – четыре. Сколькими способами можно добраться из города А в город С через город В?
Обозначим через АВ – множество дорог из А в В, через ВС – множество дорог
из В в С. Тогда задача сводится к нахождению числа элементов в декартовом произведении
АВ 
ВС , т.е. число способов будет равно
| АВ ВС | = | АВ | · | ВС | = 3 · 4 = 12.
Задача. Из города А в город В ведет три дороги, из города В в город С – четыре. Из А в С есть пять дорог, не проходящих через В. Сколькими способами можно попасть из А в С?
Обозначим через АВС множество всех способов добраться из А в С через В. Через АС обозначим множество способов добраться из А в С минуя В. Эти множества не пересекающиеся , поэтому число способов попасть из А в С определяется по правилу суммы и будет равно
предыдущаяследующая