1. Во скольких подмножествах множества {1,2,...12} не найдется трех подряд идущих чисел?

задан 15 Сен '14 20:11

изменен 15 Сен '14 20:29

10|600 символов нужно символов осталось
0

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$%.

ссылка

отвечен 15 Сен '14 20:31

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×1,370

задан
15 Сен '14 20:11

показан
966 раз

обновлен
15 Сен '14 20:31

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru