стеро — французский. Пятеро знают английский и немецкий,

четверо — английский и французский, трое — немецкий и французский. Найти: а) сколько человек знают все три языка; б) сколько знают ровно два языка; в) сколько знают только английский?

108.Имеются Зп + 1 предметов (п одинаковых, остальные различны). Доказать, что из них можно извлечь п предметов 22" способами.

109.Применяя формулу включения и исключения, определить количество целочисленных решений системы уравнений и неравенств: X] + л2 + ... + = г, а, < х,< Ъь1 - \,п, ahxn b — целые числа.

110.Определить количество целочисленных решений системы jq + х2 + х3 = 40, хх >3,х2> О, х3 > 2.

111.Компания, состоящая из 10 супружеских пар, разбивается на 5 групп по 4 человека для лодочной прогулки. Сколькими способами можно разбить их так, чтобы в каждой лодке оказались двое

мужчин и две женщины?

112.Имеем п предметов, расположенных в ряд. Сколькими способами можно выбрать из них три предмета так, чтобы не брать

никаких двух соседних элементов?

113.Даны 2п различных предметов аь щ, аъ а2,..., ап, ап. Сколько существует перестановок из этих 2л предметов, в которых не стоят рядом одинаковые элементы?

114.В шахматной олимпиаде участвуют представители п стран по

4 представителя от каждой страны. Сколькими способами они

могут встать в ряд так, чтобы рядом с каждым был представитель

той же страны?

115.Имеется п одинаковых вещей и еще п различных вещей. Сколькими способами можно выбрать из них п вещей? Сколькими способами можно упорядочить все 2л вещей?

116.Найти число способов распределения 2л одинаковых шаров по двум неразличимым корзинам.

117.В каждой клетке шахматной доски размером п х п поставили число, указывающее количество прямоугольников, в которые входит эта клетка. Чему равна сумма всех поставленных чисел?

118.Найти число расстановок/гладей так, чтобы они не били друг друга, на доске п х л (см. случаи а, 6, в) с выколотыми или добавленными клетками. В случае в) использовать п ладей.

гтт п~т lxu

о ф

Производящие функции и рекуррентные

119.Найти производящую функцию последовательности {2(л- 5) + Т+г).

120.Применить технику производящих функций для нахождения суммы чисел 1 + 23 + ... + л .

121.Решить рекуррентные соотношения:

1)ип+2. 4ип+1 + Зип= 0, "о = 8,«i = 10;

2)ы„+3 - Зи„+2 + н„+1 - Ъм„ = 0, щ = 1, щ = 3, и2 = 8;

3)ы„+2 ± 9н„ = 0, и0 = 1, = 0;

4)ы„+4 + 4и,, = 0, м0= 1, «i=l, w2= 1, м3=1;

5)"я+з + "«+2 - *Vi -ип = 0,щ= 1, », = 2, м2 = 3;

6)ип+2 - 4м„+1 + 4ия = 0, и0 = 1, щ = 2.

122.Решить неоднородные рекуррентные соотношения: !) un+i = ип+ п, "o = li

2)"„+2 = -2ил+1 + 8и„ + 27 • 5л, ио = 0,щ = - 9;

3)ы„+2 - Зыл+1 + 2и„ = л, w0= 1, = 1;

4)м„+2 - 4и„+1 + 4и„ = 2я, м0 = 1, «i = 2;

5)"„+2 = - -"п + 2"", «о = 1. Щ = 3/2;

6)и„+2 - Зил+1 + 2и„ = (-1)", щ = 1, «! = 2.

123.Последовательность Фибоначчи {«„} задается рекуррентным соотношением м„+2 = и„+1 + w„, и0 = 1, wt = 1. Найти ы„; показать, что и„ и м„+2 — взаимно простые числа и ип делится на ит, где л = т • к.

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

2)- 4ия+1 + = 0;

3)«и+2 - - «й = 0.

125. Найти решение системы рекуррентных соотношений:

126.Найти число решений уравнениях + 2у = п, гдех, у, л е Z+ -положительные целые числа; х, у — неизвестные.

127.Найти число решений уравнения х + 2у + 4z= п, х, у, я е Z+, х, у, z — неизвестные.

соотношения

6.

128. Найти определитель матрицы ос+р ар 1 а + р ар

1 а + р ар

Л„ =

\

а + Р ар 1 а+Ру

где а, р — произвольные числа; вне обозначенных диагоналей матрицы располагаются нули.

129.Вычислитьсумму £ (1 / 2 *) где суммирование производится

по всем натуральным к, не кратным 2, 3 и 5.

130.Найти ладейный многочлен запрещенных позиций для досок а) и Ь) и для каждого из этих случаев составить многочлен попаданий. Для доски с) составить многочлен запрещенных позиций. Для досок а), Ъ) и с) найти число расстановок трех ладей на

запрещенных позициях.

а}Ыс)d)

131.Найти число способов расставить 5 ладей на доске 5 к 5 так, чтобы ни одну из них не бил слон. Позиция слона указана на доске символом «с».

132.Найти число способов расставить 5 ладей на доске 5x5 так, чтобы ни одну из них не бил конь. Позиция коня указана на доске d) символом «к».

133.Найти число замкнутых маршрутов длины 2л по ребрам графа для случаев а), Ь)жс). Длина ребра равна 1. Начало и конец пути есть вершина А.

с

В

A

D

Е