Бином Ньютона. Полиномиальная формула.

218. Раскрыть скобки: (а+в) ⁵, (3х+2у)⁶.

219. Найти коэффициент при х⁷в выражении (2х+3)¹².

220. Найти коэффициент при х¹⁰в выражении (3х-2)¹³.

221. В выражении (x+2y)¹⁰раскрыли скобки и привели подобные члены. Какой коэффициент будет стоять при выражения x⁴y⁶.

222. Доказать с помощью треугольника Паскаля:

• свойство симметричности биноминальных коэффициентов

• основное свойство биноминальных коэффициентов

• свойство биноминальных коэффициентов

223. Чему равна сумма?

224. Чему равна сумма ?

225. Докажите тождество .

226. Докажите тождество .

227. Получить все различные коэффициенты, которые будут появляться при приведении подобных членов в формулах: (x+y+z)⁶и (x+y+z+u)⁵.

228. Найти коэффициенты при х⁷после раскрытия скобок и приведения подобных членов в выражении (2+х³+х⁴)¹³.

229. Найти коэффициенты при х⁸после раскрытия скобок и приведения подобных членов в выражении (1+х²-х³)⁹.

230. Найти коэффициенты при х¹⁷и х¹⁸после раскрытия скобок и приведения подобных членов в выражении (1+х⁵+х⁷)²⁰.

231. В каком из выражений (1+х²-х³)¹⁰⁰⁰, (1-х²+х³)¹⁰⁰⁰ будет после раскрытия скобок и приведения подобных членов больший коэффициент при х¹⁷.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.

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

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

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

Введение в теорию графов

Среди дисциплин и методов дискретной математики теория графов и особенно алгоритмы на графах находят наиболее широкое применение в программировании. Дело в том, что теория графов дает очень удобный язык для описания программных моделей. Особенно важно наличие наглядной графической интерпретации понятия графа. Картинки позволяют сразу «усмотреть» суть дела на интуитивном уровне, дополняя и украшая утомительные рациональные текстовые доказательства и сложные формулы.

Начало теории графов относят к 1736 г., когда Л. Эйлер решил задачу о Кениксбергскихмостах. Около 100 лет это был единственный результат теории графов. В задаче о Кениксбергских мостах (см. рис. 1) необходимо было определить можно ли, начав с некоторой точки, совершить прогулку и вернуться в исходную точку, пройдя по каждому мосту ровно один раз.

В 1930 году К. Куратовским была решена задача о трех домах и трех колодцах, сформулированная следующим образом: «Имеются три дома и три колодца. Жители домов поссорились и решили проложить дороги к своим колодцам так, чтобы они не пересекались. Возможно ли это?»

Почти 100 лет не была доказана теорема о раскраске карты: «Любую карту на плоскости можно раскрасить четырьмя красками так, чтобы никакие две соседние области не были закрашены одним цветом.»

Родившись при решении головоломок и занимательных игр, теория графов стала в настоящее время простым, доступным и мощным средством решения вопросов, относящихся к широкому кругу проблем. В виде графов можно интерпретировать схемы дорог и электрические цепи, географические карты и молекулы химических соединений, связи между людьми и группами людей. То есть виде графа можно изобразить любую структуру, на которой задано некоторое отношение между её объектами.

На рисунках 2 и 3 изображены участок электрической цепи и часть карты дорог. Ясно, что оба эти рисунка могут быть представлены одной и той же диаграммой из точек и линий, изображенной на рисунке 4

Основные определения

Определение. Определимграф как совокупность двух множеств непустого множества V (множество вершин) и множества E неупорядоченных и упорядоченных пар вершин из V.

Определение. Неупорядоченная пара вершин называетсяребром, а упорядоченная пара -дугой.

Определение. Граф, содержащий только ребра, называетсянеориентированным; граф, содержащий только дуги, -ориентированным, илиорграфом, содержащий и ребра и дуги – смешанным.

Каждый граф можно представить на плоскости множеством точек, соответствующих вершинам, которые соединены линиями, соответствующими ребрам. В трехмерном пространстве любой граф можно представить, таким образом, что линии (ребра) не будут пересекаться. Вершины графа на рисунке выделяют обычно кружочками или квадратиками, так как не всегда точки пересечения ребер являются вершинами графа.

На рисунке 5 изображен неориентированный граф G1, с пятью вершинами и восьмью ребрами.

На рисунках 6 и 7 изображены ориентированный и смешанный графы, соответственно.

Обозначения

Множество вершин будем обозначать большой латинской буквой V. Элементы этого множества (вершины) – маленькими латинскими буквами vс индексом. Множество ребер (дуг) обозначим большой латинской буквой Е, а сами ребра (дуги) - маленькими латинскими буквами е с индексом. Граф G с множеством вершин V и множеством ребер Е будем обозначать G(V,E). Количество вершин (мощность множества V) будем обозначать |V|, количество ребер (дуг) – |E|.

Для графа, изображенного на рисунке 1.5

V={v₁, v₂, v3, v₄, v₅, }, |V|=5,

E={e₁, e₂, e₃, e₄, e₅, e₆, e₇, e₈ }, |E|=8.

Определение. Вершины, соединенные ребром (дугой), называютсясмежными. Ребра (дуги), имеющие общую вершину, также называются смежными.

Определение. Ребро и любая из его двух вершин называютсяинцидентными.

Определение. Степень вершиныв неориентированном графе - число ребер, концом которых является эта вершина. Будем обозначать степень i-той вершины через deg v_i.

Например, для графа, изображенного на рисунке 5:

• вершины v₁ и v₂ смежны, а вершины v₄ и v₂ не смежны.

• ребро е₁ инцидентно вершинам v₁ и v₂

• степень первой вершины равна 4 (deg v₁=4).

Определение. Пустьvвершина орграфаDназовемполустепенью исходаvчисло дуг орграфаD, имеющих вид (v,w); аналогичнополустепенью заходаvназовем число дуг вида (w,v).

Будем обозначать полустепень захода i-той вершины через deg⁺ v_i, полустепень исхода i-той вершины через deg^- v_i.

Например, для графа, изображенного на рисунке 6 deg⁺ v₁=3, deg^- v₁=1.

Определение. Если два ребра инцидентны одной и той же паре вершин, они называютсякратными.

Определение. Граф, содержащий кратные ребра называетсямультиграфом..

Например, граф соответствующий ситуации, описанной в задаче о кенигсбергских мостах, является мультиграфом и изображен на рисунке 8. Ребра е₁ие₂этого графа соединяют одну и ту же пару вершин, а значит, являются кратными.

Определение. Ребро (дуга) называется петлей, если начало и конец его (её) совпадают.

Определение.Граф содержащий петли называется псевдографом

Рис. 9

На рисунке 9 изображен мульти-псевдограф.

Определение. Неориентированный граф без петель и кратных ребер называется простым графом.

Теорема. (Лемма о рукопожатиях). В простом графе сумма степеней всех его вершин – число четное, равное удвоенному числу ребер графа.

Доказательство. Очевидно, что каждое ребро вносит 2 в сумму степеней вершин.

Теорема. Число нечетных вершин простого графа четно.

Доказательство. Предположим противное: существует графG, имеющий нечетное количество вершин нечетной степени. Подсчитаем сумму степеней всех вершин – она будет нечетной, что противоречит лемме о рукопожатиях.

Орлемма о рукопожатии. Сумма полустепеней захода всех вершин орграфа равна сумме полустепеней исхода всех вершин.

Доказательство. Каждая дуга “участвует” в каждой сумме ровно один раз.

Примеры графов

Определение. Регулярный граф – граф, у которого все вершины имеют одну и ту же степень.

На рисунке 10 изображен регулярный граф со степенью регулярности 2. На рисунке 11 – регулярный граф со степенью регулярности 3. Граф, изображенный на рисунке 11 называют графом Петерсона, он интересен тем, что любые две его вершины соединены маршрутом, проходящим не более чем по двум ребрам.

Определение. Граф называетсяполным, если каждые две его различные вершины соединены одним и только одним ребром.

Полный граф с nвершинами обозначается К_n. На рисунке 12 изображены полные графы на 2, 3 и 5 вершинах.

Определение. Двудольный граф-это граф G(V,E), такой что множество V разбито на два непересекающихся множества V₁ и V₂(,), причем всякое ребро из E соединяет вершину из V₁ с вершиной из V_2. Множества V₁ и V₂ называются долями двудольного графа. Если двудольный граф содержит все ребра, соединяющий множества V₁ и V₂, то он называется полным двудольным графом.

Полный двудольный граф с m вершинами в одной доле и n вершинами в другой обозначается К_mn. На рисунке 13 изображен полный двудольный граф К₃₃

Способы описания графа.

При решении задач на компьютере граф должен быть представлен дискретным способом. Известны различные способы представления графов в памяти компьютера, которые различаются объемом занимаемой памяти и скоростью выполнения операций над графами. Выбор наилучшего представления определяется требованиями задачи. При решении конкретных задач используются, как правило, некоторые комбинации или модификации указанных представлений.