Задача 1
На книжной полке стоит 12 книг. Сколькими способами можно выбрать из них 5 книг так, чтобы никакие две из них не стояли рядом?
Решение Зашифруем каждый выбор книги последовательностью нулей и единиц. Именно, каждой оставленной книге сопоставим 0, каждой взятой — 1. В результате получится последовательность из 5 единиц и 7 нулей. При этом, поскольку нельзя брать стоящие рядом книги, в полученной последовательности не должно быть двух подряд идущих единиц. Сначала выписываем 7 нулей. Для единиц имеем 8 мест: 2 по краям и 6 мест в промежутках между нулями. На любое из этих мест можно поставить одну из 5 единиц. Это может быть сделано С₈⁵ = 56 способами.
Решение 2. Поставим справа на полку ещё одну, тринадцатую книгу. Склеим мысленно каждую выбранную книгу с соседней книгой справа. Это возможно, так как мы не выбираем 13-ю книгу и не выбираем рядом стоящие. Получится 5 склеенных двухтомников и ещё 3 книги отдельно. Значит, способов столько же, сколько способов разместить в ряд 5 двухтомников (считая их одинаковыми) и 3 однотомника (тоже одинаковых). Это число равно С₈³ = 56.
Ответ: 56-ю способами.