23.Перестановки. Біном Ньютона. Трикутник Паскаля.

Перестановка з n елементів – це особливий випадок розміщення без повторень з n елементів, коли в розміщення входять всі елементи Р_n= n!

Біно́м Нью́тона — це вираз вигляду (a+b)n. Біном розкладається в суму одночленів, які є добутками степенів його доданків а і в.

Властивості біноміальних коефіцієнтів:1)Нехай n i r - невід'ємні цілі числа, n ≤ r. Тоді С^r_n= С^{n - r}_n 2)Рівність Паскаля: С^K_n =С^K_n - ₁+С^{K - 1}_{n – 1}

Трикутник Паскаля — це геометрично, на зразок трикутника розміщені біноміальні коефіцієнти. Ряди трикутника Паскаля умовно пронумеровані згори, починаючи з нульового, й числа в нижньому ряді відносно чисел у попередньому ряді завжди розміщені ступінчасто й навскіс. Кожне число в кожному ряді одержуємо, додавши два числа, розміщені вгорі (зліва і справа). Якщо зліва або справа немає числа, підставляємо нуль на його місце.

24. Метод математичної індукції

Математична індукція – один з методів доказу. Використовується щоб довести істинність якогось твердження для всіх натуральних чисел. Для цього спочатку перевіряється істинність твердження з номером 1 – база індукції, а потім доводиться, що, якщо вірне твердження з номером n, то вірне і наступне твердження з номером n + 1 – крок індукції, або індукційний перехід.

Однією з найващих проблем теорії чисел є доведення істеності тверджень для всіх додатніх цілих чисел. Якщо твердж. істине для преших 10 додат. чисел, або навіть для перших 10 млн., то з цього не слідує що твердження істине для всіх додат. чисел. Простіше показати що це твердження хибне для деякого 1-го значення. Тобто навести конкретний приклад.

Принцип математичної індукції:

1)Показати що твердження істине для n=1

2)Припустимо що твердж. істине для n=K, і доведемо що воно істине для n=k+1

Математична індукція – один з методів доказу. Використовується щоб довести істинність якогось твердження для всіх натуральних чисел. Для цього спочатку перевіряється істинність твердження з номером 1 – база індукції, а потім доводиться, що, якщо вірне твердження з номером n, то вірне і наступне твердження з номером n + 1 – крок індукції, або індукційний перехід.

25. Основні означення та властивості графів

Простим графом назив. множина G = (V,E) де V це множина вершин, Е – ребер що послід. з‘єднують ці вершини. Кратним назив. ребра які з‘єднують одну і ту саму пару вершин. Петлею назив. ребро що з‘єд. вершини саму з собою. Мультиграф – це граф який містить кратні ребра але не містить петель. Псевдограф – це граф який не містить ні кратних ребер, ні петель. Орієнтований – називається граф G=(V,E), де V – вершина, а E це множина впорядков. пар елем. з V (дуги). Дугою назив. орієнтований ребро. Орієнтованим мультиграфом – це орієнт граф який може містити орієнтовані кратні ребра але не містить петель. Орієнтований псевдограф – це оргграф який може містити петлі. Дві вершини назив. суміжними якщо вони мають спільну вершину. Два ребра назив. суміжними якщо вони мають спільну вершину. Вершину та ребро називають інцедентними. Степінь вершини – це кілька ребер інцедент. даній вершині.

Якщо deg(V)=1 – то вершина назив висячою.

Якщо deg(V)=0 – то вершина назив. ізоморфн.