Пример.
Второй способ доказательства формулы бинома Ньютона.
В2.4. Бином Ньютона
Пример 2.
Число неотрицательных решений в целых числах уравнения равно , ведь всякое решение данного уравнения можно трактовать, как сочетание с повторениями, содержащее элементов первого типа (), элементов второго типа (), …,элементов n го типа (), .
Утверждение. Справедлива формула (формула бинома Ньютона)
.
Чтобы получить произведение вида нужно из имеющихся скобок отобрать скобок, из которых выбирается сомножитель а, в оставшихся k скобках выбрать в качестве сомножителя b. Но число способов выбрать k скобок из п имеющихся равно . Следовательно, = , что и требовалось.
Следствия.
1. При =1, =1: (1 + 1)n= 2n = .
2. При = 1, = -1: (1 - 1)n = 0= (-1)k .
24 = 16 =1 + 4 + 6 + 4 + 1.
0 = 1 - 4 + 6 - 4 + 1.
Любой граф может быть однозначно разделен на максимальные связные подграфы, которые называются его компонентами связности.
Компонентой связности С(Vi) называется подграф графа G, порожденный С(Vi).
Компонентой сильной связности орграфа G называется его максимальный сильно связный подграф
Пусть G1,G2… - компоненты связности, порожденные на множестве вершин V1,V2,… тогда:
«Для всякого I, для всякого j вершина i!=вершине j»
«Подмножества не содержат общих вершин»(пересечение равно 0)
«Объединение подмножеств вершин составляет множество вершин графа»
Граф G=(V,U), связен тогда и только тогда, когда множество его вершин нельзя разбить на два пустых подмножества V1 и V2 так, что обе граничные точки каждого ребра находятся в одном и том же подмножестве.
//К следующей пятнице: