- •24. Основные типы доказательств. Рассуждение «от противного». Пример.
- •25) Теория доказательств. Основные типы доказательств. Метод математической индукции. Пример.
- •26) Комбинаторика. Предмет, метод и значение комбинаторики. Типы комбинаторных задач.
- •27. Правила суммы и произведения. Привести примеры.
- •28. Понятие выборка и основные ее разновидности. Формулы их вычисления. Примеры.
- •29. Выборки с повторениями. Выборка по спецификации. Пример.
- •33. Схемы решения комбинаторных задач. Принцип распределения по ячейкам. Пример.
- •30. Выборки с повторениями. Выборка с возвращениями. Пример.
- •31. Выборки с повторениями. Сочетания с неограниченными повторениями. Пример.
- •32. Схемы решения комбинаторных задач. Принцип включения и исключения. Пример.
- •34. Бином Ньютона. Биномиальные и полиномиальные коэффициенты. Пример их вычисления.
- •35. Треугольник Паскаля. Правило его вычисления. Закономерности между элементами треугольника Паскаля.
- •36. Решето Эратосфена. Описание алгоритма и пример для первой сотни чисел.
- •37. Метод рекуррентных соотношений. Пример доказательства формулы для числа сочетаний из n по k с повторениями.
- •38. Числа Фибоначчи. Формулировка задачи. Рекуррентные соотношения и формулы для вычисления n-го числа.
34. Бином Ньютона. Биномиальные и полиномиальные коэффициенты. Пример их вычисления.
Розглянемо
детальніше формулу
для
визначення числа сполучень
без повторень і спробуємо її спростити:
.
Чисельник
отриманої формули
позначають
,
тобто
. (6.6)
Якщо
n
–
натуральне число, то
.
Нагадаємо,
що 0!
= 1.
Для
будь-якого дійсного числа n
і
цілого невід’ємного r
величина
називається
біноміальним
коефіцієнтом.
Назва пояснюється застосуванням таких
коефіцієнтів у формулі бінома
Ньютона:
, (6.7)
де
- будь-які
числа.
Розглянемо більш загальний випадок.
Нехай
- цілі невід’ємні числа і
,
тоді величина
називається
поліноміальним
коефіцієнтом.
Справедлива рівність
. (6.8)
Підсумовування
проводиться за всіма цілочисельними
невід’ємними розв’язками рівняння
.
Кількість
доданків у сумі формули (6.8) дорівнює
.
Обчислити
вираз
.
Розв’язання.
Тут
k
=
3,
n
=
5.
Виділимо ненульові ступені x
у
сумі: це –
і
.
Завдання
зводиться до знаходження розв’язків
рівняння
,
тобто
.
Розв’язками
цього рівняння є:
і
.
Використовуючи
перший розв’язок для підстановки у
формулу (6.8), отримуємо
;
Підставивши у формулу (6.8) другий розв’язок, отримуємо
.
Склавши
коефіцієнти при першому і другому
входженні
,
отримаємо
підсумкове значення коефіцієнта при
у
виразі
:
41.
35. Треугольник Паскаля. Правило его вычисления. Закономерности между элементами треугольника Паскаля.
Треугольник Паскаля — бесконечная таблица биномиальных коэффициентов, имеющая треугольную форму. В этом треугольнике на вершине и по бокам стоят единицы. Каждое число равно сумме двух расположенных над ним чисел. Строки треугольника симметричны относительно вертикальной оси.
Биномиальные
коэффициенты часто
обозначаются
или
и
читаются как «число сочетаний
из n элементов
по k.
Числа треугольника симметричны (равны) относительно вертикальной оси.
В строке с номером n:
первое и последнее числа равны 1.
второе и предпоследнее числа равны n.
третье число равно треугольному числу
,
что также равно сумме номеров
предшествующих строк.четвёртое число является тетраэдрическим.
m-е число (при нумерации с 0) равно биномиальному коэффициенту
.
Сумма чисел n-й строки треугольника Паскаля равна 2^n.
Если в строке с нечётным номером сложить все числа с порядковыми номерами вида 3n, 3n+1, 3n+2, то первые две суммы будут равны, а третья на 1 меньше.
Каждое число в треугольнике равно количеству способов добраться до него из вершины, перемещаясь либо вправо-вниз, либо влево-вниз.
36. Решето Эратосфена. Описание алгоритма и пример для первой сотни чисел.
Задача – найти простые натуральные числа , меньшие некоторого числа N.
Алгоритм Эратосфена:
1.Вычеркнуть все числа, которые делятся на 2, оставить 2;
2. Вычеркнуть все числа, которые делятся на 3, оставить 3;
3. Вычеркнуть все числа, которые делятся на 5, оставить 5;
…………………………………………………………. И т.д
Рассмотрим первую сотню чисел.
Обозначим количество простых чисел в ней π(100)
В 1-й десятке (1…10) 2,3,5,7 – 4 простых числа ;
Рассмотрим числа 2…100 (1 – особое число)
Обозначим –
А1 – свойство делимости на 2
А2 – на 3
А3 -- на 5
А4 – на 7
=
π(100)
+1 -4 = π(100)-3
Для первой сотни
=
100/2 =50
=
100/2*3 = 16
=
100/3*7*5 = 0
=
100/2*3*7*5 = 0
=
π(100)-3
= 100 -
-
-
-
+
+
+
+
+
-
-
-
-
+
=
100-50-33-20-14+16+10+7+6+4+2-3-2-1-0=22
