Элементы комбинаторики

Ключевые слова: правило умножения, правило суммы, метод включений и исключений, перестановки с повторениями и без повторений, размещения с повторениями и без повторений, сочетания с повторениями и без повторений

Задача 4.1. Сколько четырехзначных чисел можно составить из цифр 0, 1, 2, 3, 4, 5, если:

а) ни одна из цифр не повторяется более одного раза;

б) цифры могут повторяться.

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

а) Так как ни одна из цифр не может повторяться более одного раза, то , , , , откуда .

б) Если цифры могут повторяться, то на каждом месте может стоять любая из цифр, следовательно, и .

Задача 4.2. Сколько нечетных чисел находится между и ?

Решение. Пусть - множество нечетных чисел между и , для - подмножество такое, что является последней цифрой его элемента. Для каждого существует вариантов выбора первой цифры и - второй, так что каждое множество содержит элементов. Так как , то

.

Задача 4.3. Из колоды, содержащей 52 карты, вынули 10 карт. Сколькими различными способами это можно сделать? В скольких случаях среди этих карт окажется хотя бы один туз? В скольких случаях окажется ровно один туз? В скольких случаях ровно 4 туза?

Решение. Выбор 10 карт из колоды можно осуществить способами. Определим, в скольких случаях среди выбранных карт нет ни одного туза, тогда во всех остальных случаях будет хотя бы один туз. Но если среди выбранных карт нет ни одного туза, то выбор совершался не из 52, а из 48 карт (всех карт кроме тузов), а потому число таких выборов равно . Следовательно, хотя бы один туз будет в случаях.

Чтобы найти, в скольких случаях будет ровно один туз, разобьем операцию выбора карт на две: сначала выбирают из четырех тузов один туз - это можно сделать способами, а потом из оставшихся 48 карт выберем 9, что можно сделать способами. В соответствии с комбинаторным принципом умножения получаем, что существует способов.

Наконец выбор, содержащий четыре туза, можно осуществить способами - надо взять 4 туза и выбрать еще 6 карт из 48.

Задача 4.4. Сколько целых неотрицательных решений имеет уравнение ?

Решение. Заметим, что если - целые неотрицательные числа, такие что , то можно составить сочетания из элементов по с повторениями среди которых элементов первого типа, элементов второго типа, ..., элементов -го типа. С другой стороны, имеем сочетание из элементов по , получим решение уравнения в целых неотрицательных числах. Следовательно, между множеством всех сочетаний из элементов по с повторениями и множеством всех целых неотрицательных решений уравнения существует взаимно однозначное соответствие, поэтому число решений определяется формулой .

Задача 4.5. Сколько можно сделать перестановок из элементов, в которых данные два элемента и не стоят рядом?

Решение. Если данные два элемента и стоят рядом, то их можно объединить, считая одним элементом. Учитывая, что и можно переставить местами, получаем перестановок, в которых и стоят рядом. Поэтому они не стоят рядом в перестановках.

Задача 4.6. В соревновании по гимнастике участвуют 10 человек. Трое судей должны независимо друг от друга перегруппировать их в порядке, отражающем их успехи в соревновании, по мнению судей. Победителем считается тот, кого назовут первым хотя бы двое судей. В какой доле случаев в соревновании победитель будет определен?

Решение. Трое судей могут выбрать победителя способами. В случаях они назовут трех различных кандидатов. Поэтому совпадение хотя бы у двух судей будет в случаях. Доля таких случаев равна .

Задача 4.7. Сколькими способами можно переставить буквы слова “обороноспособность” так, чтобы две буквы “о” не шли подряд?

Решение. Сначала расставим все буквы слова “обороноспособность”, отличные от буквы «о», способами. После этого выбираем 7 из 12 мест способами, на которые можно вставить буквы «о». Таким образом всего получим способов.