Рекуррентные соотношения

226. Подсчитать количество последовательностей длины N, состоящих из 0 и 1, в которых никакие две единицы не стоят рядом.

227. Посылка бандероли стоит 18 рублей, а на почте имеются марки по 4, 6 и 10 рублей. Сколькими разными способами можно наклеить на бандероль марки, на нужную сумму?

228.Имеется возможность передавать 4 разных сигнала А, Б, В, Г, причем их передача занимает соответственно Т1, Т2 Т3, Т4 (целые) единиц времени. Сколько различных сообщений может быть передано за время Т (тоже целое)?

229.Абитуриент сдает в вуз 4 экзамена по 5-балльной системе и хочет набрать не менее 17 баллов. Сколькими способами он может это сделать.

230.Сколькими способами можно разбить натуральное число М на К простых слагаемых, где способы разбиения, отличающиеся порядком слагаемых, считаются разными? Например при М=10 и К=2 ответом будет 3, так как 10=3+7=5+5=7+3.

231.В лототроне имеются бочонки с номерами от 1 до К. Последовательно вынимают по одному бочонку, записывают его номер и считают сумму записанных чисел. Сколькими способами может получиться сумма М?

232.В лототроне имеются бочонки с номерами от 1 до К. Последовательно вынимают по одному бочонку, записывают его номер и считают сумму записанных чисел, после записывания номера бочонок возвращается обратно в лототрон. Сколькими способами может получиться сумма М?

233.На единственной улице в деревне стоят К домов с известными координатами. Требуется соединить их телефонными проводами минимальной суммарной длины так, чтобы житель каждого дома мог пообщаться хотя бы с одним жителем другого дома.

234.В пригородном автобусе кондуктор следил за тем, чтобы все покупали билеты и отмечал, сколько билетов (k_i,j) куплено с i–й остановки до j–й. По известной матрице k_i,j нужно найти промежуток времени, когда в автобусе было максимальное количество пассажиров и чему оно равно.

235.Прямоугольная таблица размерами МхК произвольно заполнена цифрами от 0 до 9. Найти путь из левого нижнего угла в правый верхний с максимальной суммой цифр в клетках пути (разрешается на каждом шаге переходить вверх или вправо).

236.В романе N глав, причем р-я глава состоит из Ар страниц. Роман нужно разбить на К томов, причем главы должны идти по порядку и главы нельзя разбивать в разные тома. Какова может быть минимальная толщина самого толстого тома при этом?

237. Для последовательности с f(1)=5 и f(2)=13, удовлетворяющей рекуррентному соотношению f(к+2)=5f(к+1)-6f(к), выписать формулу общего члена.

238. Для последовательности с f(0)=6 и f(1)=24, удовлетворяющей рекуррентному соотношению f(к+2)=6f(к+1)-9f(к), выписать формулу общего члена.

239. Для последовательности с f(0)=4, f(1)=-7 и f(2)=15, удовлетворяющей рекуррентному соотношению f(к+3)=-6f(к+2)-11f(k+1)-6f(к), выписать формулу общего члена.

240. Найдите общее решение рекуррентных соотношений:

a) а_n+2-7a_n+1+12a_n=0;

b) а_n+2+3a_n+1-10a_n=0;

c) а_n+2+9a_n=0;

d) а_n+2+4a_n+1+4a_n=0.

241. Найдите решение рекуррентного соотношения:

a) а_n+2-5a_n+1+6a_n=0, а₁=1, а₂=-7;

b) а_n+2-4a_n+1+4a_n=0, а₁=2, а₂=4.

Задачи по теории графов