По следам Великого Комбинатора

Мы разобрались с очень простыми комбинациями с небольшим числом вариантов. А что делать, когда «тысячи их»!? Во-первых, как и в простых случаях, дать команду «по порядку становись!», а во-вторых, опереться на два простых правила, которые облегчают дело. К этим правилам мы и переходим. Получим мы их, опять же, с помощью простых задач.

Основные законы комбинаторики. ПРАВИЛО СУММЫ.

Пример4.

Веселый продавец привез на базар 5 кошек и 6 собак . Сколькими разными способами можно купить у него одно животное? А сколькими разными способами можно купить у него кошку и собакой кота в мешке?

Решение.

На первый вопрос ответить очень просто: всего животных у продавца 5+6=11. Значит, купить у него одно животное можно одиннадцатью разными способами: либо одну из пяти кошек (все кошки разные!), либо одну из шести собак (а собаки и подавно разные!).

Можно сформулировать и общее правило:
Если некоторый элемент из множества A (в нашем примере кошку из множества кошек, привезенных на базар) можно выбрать m способами, а элемент из множества B (в нашем примере собаку из множества собак, привезенных на базар) можно выбрать n способами, то выбор «или A, или B» (в нашем примере выбор животного) можно осуществить m+n способами.

Рассмотрим похожий пример.

Пример 5.

Есть 5 человек, которые знают английский язык, и 4 человека, знающих немецкий, причем двое из них знают оба языка, Сколькими способами можно выбрать человека, знающего хотя бы один иностранный язык?

Решение.

Действительно, пусть английский язык знают Паша, Даша, Маша и Саша, а немецкий язык – Маша, Саша, Аня, Таня и Ваня. Видно, что оба языка знают Маша и Саша.

Казалось бы, у нас в двух списках девять человек, так что будет девять способов выбрать нужного человека. Но, обратите внимание, в этой компании не девять человек, а семь! Потому что Маша и Саша есть в обоих списках.