Биноминальные коэффициенты. Свойства биномиальных коэффициентов.
Биномиальные коэффициенты
Биномиальным коэффициентом 
называется количество способов выбрать набор 
предметов из 
различных предметов без учёта порядка расположения этих элементов (т.е. количество неупорядоченных наборов).
Также биномиальные коэффициенты - это коффициенты в разложении 
(т.н. бином Ньютона):
Свойства:
1) 
2) Число всех членов разложения на единицу больше показателя степени бинома то есть равно (n+1)
3) Сумма показателей степеней а и b каждого члена разложения равна показателю степени бинома то есть n
4) Биномиальные коэффициенты членов разложения равноотстоящих от концов разложения, равны между собой 
«правило симметрии»
5) Сумма биномиальных коэффициентов всех членов разложения равна 2n
6) Сумма биномиальных коэффициентов, стоящих на нечетных места равна сумме биномиальных коэффициентов, стоящих на четных местах и равна 
.
7)Правило Паскаля 
8)Любой биномиальный коэффициент начиная со второго, равен произведению предшествующего биномиального коэффициентам дроби 
9) 
38. «Треугольник Паскаля»
Биномиальные коэффициенты можно подучить с помощью треугольника Паскаля (пользуясь операцией сложения).
В верхней строке пишутся две единицы. Все следующие строки начинаются и оканчиваются единицей. Промежуточные числа получаются сложением соседних чисел вышестоящей строки.
Практическая значимостьтреугольника Паскаля заключается в том, что с его помощью можно восстановить по памяти не только известные формулы, но и формулы куба суммы (разности) , четвертой степени и выше.
Пример: (a + b)6=a6+6a5b + 15a4b2+20a3b3 + 15a2b4+6ab5+b6.
39. Ориентированные графы. Динамика графа. Матрицы смежности, инциденций и достижимости.
Ориентированный граф - это граф, на ребрах которого обозначены разрешенные направления движения, проще говоря, расставлены стрелочки.
- входящая степень вершины - это число входящих в нее ребер;
- исходящая (или выходящая) степень вершины - это число выходящих из нее ребер;
- путь из вершины A в вершину B - это последовательность ребер и промежуточных вершин, по которым можно дойти из A в B; длина пути определяется, как обычно (число ребер); простой путь - как обычно, путь, в котором вершины (и тем более, ребра) не повторяются;
- ориентированный цикл - это замкнутый простой путь в ориентированном графе;
- сильно связный ориентированный граф - это ориентированный граф, где из любой вершины в любую есть путь (для каждой пары вершин A и B есть как путь из A в B, так и путь из B в A);
- компонента сильной связности - это часть графа, которая сама по себе сильно связна, но ее нельзя расширить так, чтобы она осталась сильно связной; между разными компонентами сильной связности могут быть ребра, но все ребра между двумя разными компонентами направлены в одну и ту же сторону.
Диаграмма графа - графы принято изображать диаграммами, состоящими из кружков и линий. Кружки соответствуют вершинам графа. Линии, соединяющие кружки, соответствуют ребрам графа. Внутри кружка пишется обозначение вершины.
Матрица смежности 
матрица А называется матрицей смежности графа G. Это симметрическая матрица с нулями на диагонали, число единиц в строке равно степени соответствующей вершины, т.е числу инцидентных этой вершине ребер.
Матрица инцидентности 
Матрица называется матрицей инцидентности графа G называется матрица с р строками (каждая строка соответствует одной из вершин графа) и q столбцами (каждый столбец соответствует одному из ребер графа),