комбинаторика - Немного комбинаторики

2) Такое утверждение неверно. Верно утверждение с похожей формулировкой: число сочетаний из $%n$% по $%k$% равно числу сочетаний из $%n$% по $%n-k$%. Это сразу следует из определения сочетаний (а также из формулы, но первое доказательство проще). Ясно, что у каждого $%k$%-элементного подмножества дополнение состоит из $%n-k$% элементов. Поэтому между $%k$%-элементными и $%(n-k)$%-элементными подмножествами этим установлено взаимно однозначное соответствие. Значит, тех и других имеется одинаковое количество, а это и есть сочетания.

2) Здесь надо вывести рекуррентную формулу. Пусть $%a_n$% -- количество подмножеств множества $%\{1,2,\ldots,n\}$%, для которых никакие три элемента не идут друг за другом. Ясно, что $%a_0=1$%, $%a_1=2$%, $%a_2=4$% (для $%n\le2$% годятся все подмножества).

Пусть $%n\ge3$%. В подмножество, количество которых мы подсчитываем (будем их для краткости называть "хорошими") либо не входит $%n$%, либо входит. Хорошее подмножество без элемента $%n$% будет в точности хорошим подмножеством $%(n-1)$%-элементного множества. Таких всего имеется $%a_{n-1}$%. Пусть теперь $%n$% принадлежит хорошему подмножеству. Если $%n-1$% ему не принадлежит, то по количеству получается $%a_{n-2}$%. Если принадлежит, то $%n-2$% уже не принадлежит, и тогда получается $%a_{n-3}$% хороших подмножества. Итого $%a_n=a_{n-1}+a_{n-2}+a_{n-3}$%.

Такие числа иногда называют "числами трибоначчи". Прямой подсчёт по рекуррентной формуле даёт $%a_{12}=1705$%.