«Производящая функция является устройством, отчасти напоминающим мешок. Вместо того чтобы нести отдельно много предметов, что могло бы оказаться затруднительным, мы собираем их вместе, и тогда нам нужно нести лишь один предмет - мешок».
Д. Пойа
Введение
Математика делится на два мира - дискретный и непрерывный. В реальном мире есть место и для того и для другого, и часто к изучению одного явления можно подойти с разных сторон. В этой статье мы рассмотрим метод решения задач с помощью производящих функций - мостика ведущего из дискретного мира в непрерывный, и наоборот.Идея производящих функций достаточно проста: сопоставим некоторой последовательности
История возникновения производящих функций
Известно, что начало методу производящих функций положил английский математик Абрахам де Муавр, а дальнейшему развитию и продолжению данного метода мы обязаны великому математику, имя которого Леонард Эйлер.В 50-х годах XVIII века Эйлер решал следующую задачу: какие грузы можно взвесить с помощью гирь в 2 0 , 2 1 , 2 2 ,..., 2 n грамм и сколькими способами? При решении этой задачи он использовал никому неизвестный на то время метод производящих функций , которому и посвящена данная статья. К этой задаче мы вернёмся немного позже, после того как разберёмся более подробно с устройством производящих функций.
Метод производящих функций
Изучение этого мощного механизма позволяющего решать многие задачи, мы начнём с простенькой задачи: сколькими способами можно расположить в линию чёрные и белые шары, общее количество которых равно n?Обозначим белый шар символом ○, чёрный - ●, T n - искомое количество расположений шаров. Символом Ø - обозначим нулевое количество шаров. Как и любое решение комбинаторной задачи начнём с тривиальных случаев:
Если n=1, то очевидно имеется 2 способа - взять либо белый шар ○, либо взять чёрный шар ●, таким образом, T 2 = 2.
Если n=2, то имеется 4 способа расположений: ○○, ○●, ●○, ●●.
Рассмотрим случай для n=3. Мы можем начать белым шаром и продолжить 4-мя комбинациями, описанными выше ○○○, ○○●, ○●○, ○●●, или же мы можем начать чёрным шаром и аналогично продолжить 4-мя шарами ●○○, ●○●, ●●○, ●●●.
В итоге количество шаров удвоилось, то есть T 3 = 2T 2 . Аналогично T 4 = 2T 3 , то есть, обобщая для всех n, получаем рекуррентное уравнение T n = 2T n-1 которое и является решением для данной задачи. Решение такого уравнения можно легко угадать - T n = 2 n (так как 2⋅2 n-1 = 2 n).
А что если у нас плохо с угадыванием? И что делать, если уравнение будет сложнее? А вообще причём здесь производящие функции?
«Просуммируем» все возможные комбинации расположений шаров:
G = Ø + ○ + ● + ○○ + ○● + ●○ + ●● + ○○○ + ○○● + ○●○ + ○●● + ●○○ + ●○● + ●●○ + ●●● +…
Вопрос о допустимости такой нелепой на первый взгляд суммы опустим. Будем складывать и умножать последовательности шаров. Со сложением всё понятно, но что значит умножить одну последовательность шаров на другую? Перемножив ○● на ●○ мы получим не что иное как ○●●○. Заметим, однако, что произведение шаров в отличие от произведения чисел не является коммутативным, так как ○●⋅●○ ≠ ●○⋅○●. Символ Ø - в произведении играет роль мультипликативной единицы, то есть Ø ⋅ ○○● = ○○● ⋅ Ø = ○○● и коммутирует с любой последовательностью шаров.
Производя с рядом G последовательность манипуляций, а именно вынося за скобки левый белый и чёрный шары
G = Ø + ○ (Ø + ○ + ● + ○○ + ○● + ●○ + ●● + ...) + ● (Ø + ○ + ● + ○○ + ○● + ●○ + ●● + ...) = Ø + ○G +●G
Получим уравнение G = Ø + ○G +●G.
Несмотря на то, что умножение некоммутативно, и мы фактически не различаем левое и правое деление, попробуем всё же «решить» это уравнение, на свой страх и риск. Получим,
Учитывая формулу суммы геометрической прогрессии , имеем
В этой сумме так же учтены все возможные варианты разбиения в точности по одному разу. Далее воспользуемся формулой бинома Ньютона: , где - число сочетаний из n по k. Тогда с учетом этого имеем:
Коэффициент при ○ k ● n-k равный числу сочетаний из n по k, показывает общее количество последовательностей из n шаров содержащих ○ шары в количеств k штук и ● шары в количестве n-k штук. Таким образом, общее количество расположений n шаров есть сумма по всем возможным значениям k. Как известно .
Эту формулу можно было получить непосредственно из заменив Ø на 1, а ○ и ● на z (в виду их равнозначности). Получим то есть коэффициент при z n равен 2 n .
Обсуждение метода
Так что же позволяет данному методу быть работоспособным при решении различных задач?Алгоритм решения задачи можно описать примерно следующим образом: рассматривается некоторая бесконечная сумма, которая в конечном итоге представляет собой формальный степенной ряд G(z) = g 0 + g 1 z + g 2 z 2 +… + g n z n +… причем коэффициенты g k (не заданные в явном виде) - являются ключом к решению исходной задачи. То, что ряд является формальным, говорит о том, что z - является просто символом, то есть вместо него может быть любой объект: число, шар, кость домино и т.д. В отличие от степенных рядов в анализе формальным степенным рядам не придается числовых значений и, соответственно, нет смысла говорить о сходимости таких рядов для числовых аргументов.
G(z) = g 0 + g 1 z + g 2 z 2 +… + g n z n +… - называется производящей функцией для последовательности
Затем производя различные преобразования с бесконечной суммой G(z) мы преобразуем её к замкнутому (компактному) виду. То есть у производящей функции есть 2 представления: бесконечное и замкнутое и, как правило, для решения задачи необходимо бесконечный вид преобразовать к замкнутому, а затем замкнутый вид разложить в степенной ряд, и тем самым получить значения для коэффициентов g k .
Отвечая на поставленный вначале вопрос можно сказать так: успех данного метода связан с возможностью записать производящую функцию в замкнутом виде. Так, например, производящая функция для последовательности <1, 1, 1, ..., 1> в бесконечном виде представляется как 1 + x + x 2 + x 3 + ..., а в замкнутом .
А теперь вооружившись знаниями, вернемся к задаче, которую решал Эйлер.
Итак, задача звучит следующим образом: какие грузы можно взвесить с помощью гирь в 2 0 , 2 1 , 2 2 ,..., 2 n грамм и сколькими способам?
Я не знаю, как долго Эйлер придумывал решение для этой задачи, но оно поражает своей неожиданностью. Посудите сами. Эйлер рассматривает произведение G(z) = (1+z)(1+z 2)(1+z 4)… которое после раскрытия скобок представляется в виде бесконечного ряда G(z) = 1 + g 1 z + g 2 z 2 + g 3 z 3 +….
Что же из себя представляют коэффициенты g k ? Каждый g k - это коэффициент при z k , а z k - получается как произведение каких-то одночленов z 2m , то есть g k - это в точности число разных представлений числа k в виде суммы некоторых из чисел 1, 2, 2 2 , 2 3 ,..., 2 m ,…. Другими словами g k - это число способов взвешивания груза в k грамм заданными гирями. Как раз то, что мы искали!
Следующий шаг Эйлера поражает не менее предыдущего. Он умножает обе части равенства на (1-z).
(1-z)G(z) = (1-z)(1+z)(1+z 2)(1+z 4)(1+z 8)…
(1-z)G(z) = (1-z2)(1+z 2)(1+z 4)(1+z 8)…
(1-z)G(z) = (1-z 4)(1+z 4)(1+z 8)…
(1-z)G(z) = 1
С одной стороны G(z) = 1 + g 1 z + g 2 z 2 + g 3 z 3 +… с другой стороны мы только что получили . Последнее равенство есть не что иное, как сумма геометрической прогрессии, которая равна . Сопоставляя эти два равенства, получаем g 1 = g 2 = g 3 =… = 1, то есть любой груз в k грамм можно взвесить гирями в 1, 2, 4, 8,… грамм притом единственным способом.
Решение рекуррентных соотношений
Производящие функции подходят для решения не только комбинаторных задач. Оказывается, с их помощью можно решать рекуррентные соотношения.Начнем со всеми знакомой последовательностью чисел Фибоначчи. Каждый из нас знает её рекуррентный вид: F 0 = 0, F 1 = 1, F n = F n-1 + F n-2 , n ≥ 2. Однако не каждый знает вид этой формулы в замкнутом виде и это не удивительно, ведь она содержит иррациональное число(«золотое сечение») в своём составе.
Итак, имеем
F 0 = 0,
F 1 = 1,
F n = F n-1 + F n-2 , n ≥ 2
Умножим каждую строчку на z 0 , z 1 , ..., z n соответственно:
Z 0 ⋅ F 0 = 0,
z 1 ⋅ F 1 = z,
z n ⋅ F n = z n ⋅ F n-1 + z n ⋅ F n-2 , n ≥ 2
Просуммируем эти равенства:
Обозначим левую часть
Рассмотрим каждое из слагаемых в правой части:
Имеем следующее уравнение G(z) = z + z G(z) + z 2 G(z) решая которое относительно G(z) находим
Производящая функция для последовательности чисел Фибоначчи.
Разложим её на сумму простейших дробей, для этого найдем корни уравнения 
. Решая это простое квадратное уравнение, получаем: 
. Тогда нашу производящую функцию можно разложить следующим образом:
Следующим шагом является нахождение коэффициентов a и b. Для этого умножим дроби на общий знаменатель:
Подставляя в это уравнение значение z = z 1 и z = z 2 , находим 
Напоследок немного преобразуем выражение для производящей функции
Теперь каждая из дробей представляет собой сумму геометрической прогрессии.
По формуле находим
Но ведь мы искали G(z) в виде 
. Отсюда делаем вывод, что
Эту формулу можно переписать в другом виде не используя «золотое сечение»:
Что достаточно трудно было ожидать, учитывая красивое рекуррентное уравнение.
Давайте запишем общий алгоритм решения рекуррентных уравнений, используя производящие функции. Он записывается в 4 шага:
Причина, по которой данный метод работает, заключается в том, что единая функция G(z) представляет всю последовательность g n и это представление допускает многие преобразования.
Прежде чем переходить к следующему примеру, рассмотрим 2 операции, совершаемые над производящими функциями, которые часто оказываются полезными.
Дифференцирование и интегрирование производящих функций
Для производящих функций обычное определение производной можно записать следующим образом.Пусть G = G(z) – производящая функция. Производной этой функции называется функция 
. Дифференцирование, очевидно, линейная операция, поэтому для того, чтобы понять, как оно действует на производящих функциях, достаточно посмотреть на его действие, на степенях переменной. Имеем
Тем самым, действие дифференцирования на произвольной производящей функции
G (z) = g 0 + g 1 z + g 2 z 2 + g 3 z 3 +… дает G΄(z) = g 1 + 2g 2 z + 3g 3 z 2 + 4g 4 z 3 +….
Интегралом называется функция
Операция дифференцирования обратна операции интегрирования:
Операция же интегрирования производной приводит к функции с нулевым свободным членом, и поэтому результат, отличается от исходной функции,
Нетрудно заметить, что для функций, представимых в виде степенных рядов, формула для производной соответствует обычной. Формула для интеграла соответствует значению интеграла с переменным верхним пределом
Используя только что полученные знания о дифференцировании и интегрировании производящих функций, попробуем решить следующее рекуррентное уравнение:
G 0 = 1,
g 1 = 1,
g n = g n-1 + 2g n-2 + (-1) n
Будем следовать вышеописанному алгоритму. Первое условие алгоритма выполнено. Умножим обе части всех равенств на z в соответствующей степени и просуммируем:
Z 0 ⋅ g 0 = 1,
z 1 ⋅ g 1 = z,
z n ⋅ g n = z n ⋅ g n-1 + 2z n ⋅ g n-2 + (-1) n ⋅ z n
Левая часть представляет собой производящую функцию в бесконечном виде.
Попытаемся выразить правую часть через G(z). Рассмотрим каждое слагаемое:
Составляем уравнение:
Это и есть производящая функция для заданного рекуррентного уравнения. Раскладывая её на простейшие дроби (например, методом неопределенных коэффициентов или методом подстановки различных значений z), получаем:
Второе и третье слагаемые легко раскладываются в степенной ряд, а вот с первым придется чуть повозиться. Используя правило дифференцирования производящих функций имеем:
Собственно всё. Раскладываем каждое слагаемое в степенной ряд и получаем ответ:
С одной стороны мы искали G(z) в виде 
, с другой стороны .
Значит, 
.
Вместо заключения
Производящие функции нашли большое применение в математике, поскольку являются мощным оружием при решении многих практических задач, связанных, например, с перечислением, распределением и разбиением множеств объектов различной природы. Кроме того применение производящих функций позволяет доказать некоторые комбинаторные формулы, которые иначе получить очень трудно. Например, разложение функции
в степенной ряд имеет вид , то есть справедливо равенство:
Возводя в квадрат обе части этого равенства получим
Приравнивая коэффициенты при x n в левой и правой частях, получаем
Эта формула имеет прозрачный комбинаторный смысл, но доказать её непросто. Еще в 80-е годы XX века появились публикации, посвященный этому вопросу.
Последовательность удовлетворяет следующему соотношению где - некоторые числа. При заданных значениях формула (1) полностью определяет последовательность; каждый ее элемент, начиная с к-го, является линейной комбинацией предыдущих к элементов с коэффициентами поэтому формулу (1) называют линейным рекуррентным соотношением к-го порядка. Если положить можно переписать в виде ИЛИ Решение линейных рекуррентных уравнений Поставим задачу - перейти от рекуррентного задания последовательности к формуле, выражающей зависимость общего члена последовательности хп от его номера п. Для решения этой задачи введем в рассмотрение: - производящую функцию последовательности - характеристический многочлен - многочлен Отметим следующую связь между многочленами: при. Докажем, что F(t) является дробно-рациональной функцией. Действительно, где коэффициенты Cm определяются по коэффициентам а^ и первым к членам последовательности Итак,) - многочлен степени не выше к- 1; поэтому F(t) = - правильная рациональная дробь. Дальнейший ход наших выкладок будет следующим: мы представим F(t) в виде суммы простейших дробей, запишем разложения простейших дробей по степеням переменной t, после чего по виду полученного ряда для F(t) будет ясен характер зависимости хп от п. Пусть характеристический многочлен /(А) имеет s различных (комплексных) корней: Aj кратности Г|, ..., Ха кратности rs: Как известно из алгебры, разложение правильной рациональной дроби со знаменателем g(t) на простейшие дроби имеет вид где некоторые константы. Применив биномиальное разложение, получим Таким образом, или, поскольку - многочлен от п степени (при фиксированном j)> где - некоторый многочлен степени не выше Мы доказали, что обший член последовательности, удовлетворяющей линейному рекуррентному соотношению fc-ro порядка, имеет вид где для число - корень кратности г, характеристического многочлена рекуррентного соотношения, Р*(я) - многочлен степени, не превосходящей г, - 1. Конкретный вид указанных многочленов определяется первыми к членами последовательности: В частности, если все корни характеристи- ческого многочлена - простые (т.е. кратности 1), то последовательность (ж„) представима в виде суммы геометрических прогрессий: где Ci - некоторые константы. Рассмотрим несколько примеров. Пример 1. Последовательность чисел Фибоначчи задается соотношениями Составим характеристическое уравнение: формула общего члена: Коэффициенты С\ и Cj определим из -начальных условий»: . Решив систему двухуравнений с двумя неизвестными, получим окончательный результат: Пример 2. Найдем все последовательности, удовлетворяющие условию Характеристическое уравнение А2 - 2А4- 1 =0 имеет двукратный корень: Au = 1, поэтому общий член последовательности имеет вид: где константы о и 6 определяются первыми двумя членами последовательности. Таким образом, (х„) - арифметическая прогрессия. Этот результат можно было предвидеть, заметив, что соотношение (3) является характеристическим для арифметической прогрессии: каждый член последовательности, начиная со второго, есть среднее арифметическое его соседних членов. ПримерЗ. Найдем последовательность (z„), задаваемую соотношениями Разложим характеристический многочлен на множители: Вид n-го члена последовательности:. Константы а, Ь, с найдем из системы уравнений Ответ: Упражнения Решение линейных рекуррентных уравнений Правило произведения 1. Из города А в город Б ведут 5 дорог, а из города Б в город В - 7 дорог. Сколько есть различных маршрутов из города А в В через Б? 2. В меню столовой 3 первых, 5 вторых и 3 третьих блюда. Сколькими способами можно выбрать обед из трех блюд (первое, второе и третье)? 3. Сколько есть двузначных чисел, не содержащих цифр 4. Сколько есть двузначных чисел, не содержащих цифр Номер автомашины состоит из трех букв латинского алфавита (содержащего 26 букв) и трех цифр. Сколько можно составить различных номеров автомашин? 6. У рояля 88 клавиш. Сколькими способами можно извлечь последовательно 6 звуков? 7. Сколько натуральных делителей имеет число 8. Сколько натуральных делителей имеет число 9. Сколько есть пятизначных чисел, 1) оканчивающихся двумя семерками? 2) начинающихся с двух одинаковых цифр? 3) в каждом из которых нет одинаковых цифр? 4) в каждом из которых соседние цифры различны? 5) делящихся на 4 и не содержащих цифр 6) в записи которых есть одинаковые цифры? 7) в записи которых есть хотя бы одна четная цифра? Решение линейных рекуррентных уравнений 10. Сколько есть перестановок цифр в которых 1) цифра 3 занимает третье место, а цифра 5 - пятое? 2) цифра 1 следует непосредственно за цифрой 0? 3) цифра 0 занимает одно из первых трех мест, а цифра 1 - одно из последних четырех мест? 4) цифра 0 занимает одно из первых пяти мест, а цифра 1 - одно из первых трех мест? 5) между цифрами 0 и 1 стоят ровно три цифры? 6) цифра 0 расположена левее цифры 1? 7) цифра 1 расположена между цифрами 0 и 2? 8) хотя бы одна из первых трех цифр делится на 3? 11. Сколькими способами можно рассадить за десятью партами 10 мальчиков и 10 девочек так, чтобы за каждой партой сидели а) мальчик слева, а девочка справа? б) мальчик и девочка? 12. Сколькими способами можно прочитать слово ПАРУС, двигаясь вправо или вниз по каждой из следующих таблиц? Сколькими способами можно расставить на шахматной доске 8 одинаковых ладей так, чтобы никакие две из них не били друг друга? 14. Сколькими способами можно расставить на шахматной доске 8 одинаковых ладей так, чтобы они били все поля? Сочетания 15. Вычислить: 16. Найти число подмножеств X множества обладающих следующими свойствами: 5) множество X состоит из трех четных и двух нечетных чисел; 17. На окружности последовательно отмечены точки Сколько существует 1) хорд с концами в отмеченных точках; 2) треугольников с вершинами в отмеченных точках; 3) выпуклых четырехугольников с вершинами в отмеченных точках; 4) треугольников с вершинами в отмеченных точках, не имеющих обших точек с прямой А2Ая; 5) треугольников с вершинами в отмеченных точках, имеющих общие точки с прямой AiA}? 18. На окружности отмечено п точек. Точки соединяются всевозможными хордами; известно, что никакие три из них не пересекаются в одной точке внутри круга. Найти: 1) число точек пересечения хорд внутри круга; 2) количество частей, на которые хорды делят круг. 19. На прямой I отмечено 8 точек, а на параллельной ей прямой m точек. Сколько существует 1) треугольников с вершинами в отмеченных точках; 2) выпуклых четырехугольников с вершинами в отмеченных точках? 20. Две команды играют в волейбол до 4 побед. Сколько существует разных вариантов изменения счета в игре по партиям? 21. Сколькими способами можно разложить 4 белых и 3 черных шара по 6 различным ящикам? 22. Решить предыдущую задачу при дополнительном условии: ни один яшик не должен быть пустым. 23. Сколькими способами можно разложить 20 одинаковых шаров по 5 различным яшикам так, чтобы 1) в каждом ящике оказалось не менее двух шаров; 2) в каждом ящике оказалось не более 5 шаров; 3) оказалось не более двух пустых яшиков? 24. Найти коэффициент при г100 в разложении многочлена Дан квадрат. Каждая его сторона разбита на п равных частей. Через точки деления проведены прямые, параллельные сторонам. Сколько существует 1) прямоугольников; 2) квадратов, ограниченных проведенными линиями? 26. В правлении банка 7 человек. Каково должна быть минимальное число замков от сейфа и как следует распределить ключи меж^у членами правления (каждый член правления может получить ключи от нескольких замков), чтобы любое большинство сейф могло открыть, а любое меньшинство - не могло? 27. Каким числом способов можно прочитать слово «абракадабра», двигаясь вправо или вниз по таблице (с. 76)? На клетчатой бумаге нарисован прямоугольник ABCD, стороны которого лежат на линиях сетки, причем длина отрезка AD в к раз больше длины отрезка АВ (к - натуральное число). Рассматриваются всевозможные пути, проходящие по линиям сетки и кратчайшим образом ведущие из А в С. Доказать, что среди этих путей в к раз больше тех, у которых первое звено лежит на AD, чем тех, у которых первое звено лежит на АВ. 29. Изучите поведение последовательности (о*), где ак = С* (при фиксированном п), с точки зрения возрастания-убывания. 30. Имеется карточная колода из 52 карт. Каким числом способов можно раздать по 13 карт четырем игрокам? Полиномиальная формула 31. Найти коэффициент при хк в разложении многочленов: Комбинаторные тождества 32. С помощью формулы бинома Ньютона Решение линейных рекуррентных уравнений доказать следующие тождества: 33. С помощью комбинаторных рассуждений доказать: Формула яключения-исключения 34. На кафедре лингвистики работают 13 человек, причем каждый из них знает хотя бы один иностранный язык. Десять человек знают английский язык, семеро немецкий, шестеро - французский. Пятеро знают английский и немецкий, четверо - английский и французский, трое - немецкий и французский. Сколько человек знают 1) все три языка; 2) ровно два языка; 3) только английский язык? 35. 1) Показать, что количество натуральных чисел, делящихся на п и не превосходящих положительного числа х, равно 2) Сколько есть чисел, не превосходящих и не делящихся ни на ни на, ни на 3) Сколько есть четырехзначных чисел, не делящихся ни на, ни на, ни на 4) Сколько есть чисел, не превосходящих и не делящихся ни на одно из чисел 5) Показать, что если п = 30т, то количество натуральных чисел, не превосходящих п и не делящихся ни на одно из чисел равно. 36. Пусть. Показать, что простых чисел в множестве не больше восьми. 37. На каждой стороне треугольника А ВС отмечено по п точек, разбивающих ее на п + 1 равных частей. Рассмотрим всевозможные треугольники с вершинами в отмеченных точках (по одной на каждой стороне). Сколько среди этих треугольников таких, у которых ни одна из сторон не параллельна стороне треугольника ABC? 38. Сколько существует б-значных номеров (первые цифры могут быть и нулями) с суммой цифр 27? 39. В кошельке лежит по 20 монет достоинством в рублей. Сколькими способами можно из этих 60 монет выбрать к монет (к ^ 60)? Задача о беспорядках и встречах 40. С помощью рекуррентных соотношений найти число беспорядков Dn для 42. Сколькими способами можно расставить на шахматной доске 8 одинаковых ладей так, чтобы никакие две из них не били друг друга и чтобы ни одна ладья не стояла на главной диагонали? 43. Сколькими способами можно раскрасить клетки шахматной доски 8 х 8 в 8 цветов так, чтобы клетки, имеющие обшую сторону, были бы окрашены в разные цвета и чтобы в каждом горизонтальном ряду встречались все 8 цветов? 44. Две колоды карт, содержащие по 52 карты, тщательно тасуются, после чего сравниваются карта за картой. Какова вероятность того, что не будет ни одной пары совпадающих карт? 45. Для числа перестановок п элементов с А: встречами Dn,k доказать тождества: Случайным образом выбирается перестановка чисел 1,2..., п. Пусть £ - количество элементов, остающихся на своих местах. Найти математическое ожидание и дисперсию случайной величины 47. Секретарше нужно отправить п различных писем по п различным адресам. Она подписывает конверты и случайным образом вкладывает письма в конверты. Сколько в среднем писем дойдет до своего адресата? Производящие функции Найти производящие функции следующих последовательностей: Пусть - последовательности, - соответствующие производящие функции. Выразить А(х) через В(х) при следующих соотношениях между последовательностями: Пусть an = С?Ък. Доказать, что bn = Рекуррентные соотношения 64. Последовательность (a„) удовлетворяет соотношению уравнение имеет два различных ненулевых корня х, и х2. Доказать, что имеет место тождество для некоторых С| и с2, однозначно определяемых Найти формулу общего члена последовательности: 66. Найти количество n-значных чисел, состоящих из цифр, в которых первая и последняя, а также любые две соседние цифры различны. 67. Сколько существует раскрасок вершин n-угольника, если соседние вершины должны быть разного цвета, а всего имеется к цветов? 68. Пусть n-й член последовательности задается формулой. Доказать, что для последовательности имеет место рекуррентное соотношение а, где 69. Найти а, если 70. Найти число двоичных последовательностей длины 11, не содержащих единиц ни в каких трех соседних позициях. 71. Найти обшие решения рекуррентных соотношений: 72. Найти ап по рекуррентным соотношениям и начальным условиям: 1) Каждая точка пересечения хорд однозначно задается (неупорядоченной) четверкой точек - концов этих хорд. Будем последовательно проводить хорды. Пусть kt - число точек пересечения t"-й хорды с ранее проведенными. Этими точками «-я хорда делится на fc, + 1 отрезков, каждый из которых, в свою очередь, делит одну «старую» часть разбиения круга на две «новые». Изначально имелась одна часть. После проведения всех N хорд количество частей равно Осталось заметить, что N = а обшее количество точек пересечения хорд Решение линейных рекуррентных уравнений (согласно первому пункту данной задачи). Интересен ответ к задаче при Он "гаков: Физик из известного анекдота на основании первых пяти результатов заявил бы, что общий ответ - 2я"а число 31 возникло в результате погрешности эксперимента. . Составьте отношение. Подсчитайте двумя способами сумму мощностей всех подмножеств п-элементного множества. 3 при нечетном при четном п. . Решение. Пусть U - множество последовательностей (составленных из шести неотрицательных целых чисел с суммой 27; а для каждого i множество Ai С U состоит из таких последовательностей, в которых Для решения -Заметим,что | а пересечение трех и большего числа множеств Ai пусто. 41. Используйте оценку остаточного члена ряда из признака Лейбница. Указание. Обозначим через о„ число двоичных последовательностей длины п, удовлетворяющих условию задачи. Найдите начальные условия и рекуррентное соотношение для последовательности (оп).
Числа Фибоначчи.
При решении многих комбинаторных задач применяют метод сведения данной задачи к задаче касающегося меньшего числа элементов. Например, можно вывести формулу для числа перестановок:
Отсюда видно, что всегда может быть сведён к факториалу от меньшего числа.
Хорошей иллюстрацией к построению рекуррентных соотношений является задача Фибоначчи. В своей книге в 1202 г. итальянский математик Фибоначчи привел следующую задачу. Пара кроликов приносит приплод раз в месяц двух крольчат (самку и самца), причём новорождённые крольчата через два месяца после рождения сами приносят приплод. Сколько кроликов появится через год, если в начале была одна пара кроликов.
Из условия задачи следует, что через месяц будет две пары кроликов, через два месяца приплод даст только первая пара кроликов, появившихся два месяца назад, поэтому всего будет 3 пары кроликов. Ещё через месяц будет уже 5 пар. И так далее.
Обозначим через количество пар кроликов по истечении месяцев с начала года. Тогда через месяц количество пар кроликов можно найти по формуле:
Эта зависимость называется рекуррентным соотношением . Слово «рекурсия» означает возврат назад (в нашем случае – возврат к предыдущим результатам).
По условию, и , тогда по соотношению имеем: , , и т.д., .
Определение 1: Числа называются числами Фибоначчи . Это – известная в математике последовательность чисел:
1, 1, 2, 3, 5, 8, 13, 21, ...
В этой последовательности каждое последующее число является суммой двух предыдущих чисел. И в рекуррентном соотношении также последующий член находится как сумма двух предыдущих членов.
Установим связь между числами Фибоначчи и комбинаторной задачей. Пусть требуется найти число - последовательностей, состоящих из нулей и единиц, в которых никакие две единицы не стоят подряд.
Возьмем любую такую последовательность и сопоставим ей пару кроликов по следующему правилу: единицам соответствуют месяцы появления на свет одной из пар «предков» данной пары (включая и исходную), а нулями – все остальные месяцы. Например, последовательность 
устанавливает такую «генеалогию» – сама пара появилась в конце 11-го месяца, ее родители в конце 7-го месяца, «дед» – в конце 5-го месяца, и «прадед» в конце 2-го месяца. Первоначальная пара шифруется последовательностью 
. Ни в одной последовательности две единицы не могут стоять подряд – только что появившаяся пара не может принести приплод через месяц. Очевидно, различным последовательностям отвечают различные пары и обратно.
Таким образом, число последовательностей с указанными свойствами, равно .
Теорема 1: Число находится как сумма биномиальных коэффициентов:. Если – нечетно, то . Если – четно, то . Иначе: – целая часть числа .
Доказательство: В самом деле, - число всех последовательностей из 0 и 1, в которых никакие две единицы не стоят рядом. Число таких последовательностей, содержащих ровно единиц и нулей, равно , при этом , тогда изменяется от 0 до . Применяя правило суммы, получаем данную сумму.
Это равенство можно доказать иначе. Обозначим:
Из равенства 
, следует, что . Кроме этого, ясно, что и 
. Так как обе последовательности и удовлетворяют рекуррентному соотношению , то , и .
Определение 2: Рекуррентное соотношение имеет порядок , если оно позволяет вычислять через предыдущих членов последовательности: .
Например, – рекуррентное соотношение второго порядка, а рекуррентное соотношение 3-го порядка. Соотношение Фибоначчи является соотношением второго порядка.
Определение 3:Решением рекуррентного соотношения является последовательность, удовлетворяющая этому соотношению.
Если задано рекуррентное соотношение ‑ го порядка, то ему удовлетворяют бесконечно много последовательностей, т.к. первые элементов можно задать произвольно. Но если первые элементов заданы, то остальные члены определяются однозначно.
Например, соотношению Фибоначчи кроме рассмотренной выше последовательности 1, 1, 2, 3, 5, 8, 13, 21, ..., могут удовлетворять также и другие последовательности. К примеру, последовательность 2, 2, 4, 8, 12,... строится по тому же принципу. Но если задать начальные члены (их в последовательности Фибоначчи - 2), то решение определяется однозначно. Начальных членов берут столько, каков порядок соотношения.
По известным рекуррентным соотношениям и начальным членам можно выписывать члены последовательности один за другим и таким путем мы можем получить любой её член. Но во многих случаях, нам не нужны все предыдущие члены, а необходим один определенный член. В этом случае удобнее иметь формулу ‑ го члена последовательности.
Мы будем говорить, что некоторая последовательность является решением данного рекуррентного соотношения, если при подстановке этой последовательности соотношение тождественно выполняется.
Например, последовательность является одним из решений соотношения: . Это легко проверить обычной подстановкой.
Определение 4: Решение рекуррентного соотношения ‑ го порядка называется общим , если оно зависит от произвольных постоянных , меняя которые, можно получить любое решение данного соотношения.
Например, для соотношения общим решение будет 
.
В самом деле, легко проверяется, что оно будет решением нашего соотношения. Покажем, что любое решение можно получить в таком виде. Пусть и – произвольны.
Тогда найдутся такие и , что
Очевидно, для любых , система уравнений имеет единственное решение.
Определение 5: Рекуррентное соотношение называется линейным , если оно записывается в виде:
где - числовые коэффициенты.
Для решения произвольных рекуррентных соотношений общих правил, вообще говоря, нет. Однако для решения линейных рекуррентных соотношений есть общие правила решения.
Рассмотрим сначала соотношение 2-го порядка .
Решение этого соотношения основано на следующих утверждениях.
Теорема 2: Если и - являются решением данного рекуррентного соотношения 2-го порядка, то для любых чисел и последовательность также является решением этого соотношения.
Теорема 3:
Если число является корнем квадратного уравнения , то последовательность 
является решением рекуррентного соотношения .
Из теорем 2, 3 вытекает следующее правило решения линейных рекуррентных соотношений 2-го порядка.
Пусть дано рекуррентное соотношение .
1) Составим квадратное уравнение , которое называется характеристическим для данного соотношения. Найдём все корни этого уравнения (даже кратные и комплексные).
2) Составим общее решение рекуррентного соотношения. Его структура зависит от вида корней (одинаковые они или различные).
а) Если это соотношение имеет два различных корня
и , то общее решение соотношения имеет вид 
.
Действительно, из теорем 2, 3 следует, что - решение и система уравнений
Имеет единое решение, т.к. при условии .
Например, для чисел Фибоначчи, имеем . Характеристическое уравнение имеет вид: . Решая последнее уравнение, получим корни.
Размер: px
Начинать показ со страницы:
Транскрипт
1 МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Костромской государственный университет имени Н. А. Некрасова Т. Н. Матыцина ДИСКРЕТНАЯ МАТЕМАТИКА РЕШЕНИЕ РЕКУРРЕНТНЫХ СООТНОШЕНИЙ Практикум Кострома 2010
2 ББК я73-5 М348 Печатается по решению редакционно-издательского совета КГУ им. Н. А. Некрасова Рецензент А. В. Чередникова, кандидат физико-математических наук, доцент М348 Матыцина Т. Н. Дискретная математика. Решение рекуррентных соотношений: практикум [Текст] / Т. Н. Матыцина. Кострома: КГУ им. Н. А. Некрасова, с. Практикум содержит индивидуальные задания для студентов и предназначен для обеспечения самостоятельной работы по освоению первой части курса «Дискретная математика». Для студентов 2 3 курсов физико-математического факультета, обучающихся по специальностям «Математика» с дополнительной специальностью «Информатика», «Информатика» с дополнительной специальностью «Математика». ББК я73-5 Т. Н. Матыцина, 2010 КГУ им. Н. А. Некрасова,
3 ОГЛАВЛЕНИЕ Введение Методические рекомендации по решению линейных рекуррентных соотношений Основные понятия и определения рекуррентных (возвратных) последовательностей Алгоритмы решения ЛОРС и ЛРС Примеры решения ЛОРС и ЛРС Задачи для самостоятельного решения Задачи для решения ЛОРС и ЛРС Ответы Заключение Библиографический список
4 ВВЕДЕНИЕ Первая часть курса «Дискретная математика», изучаемая студентами 2 3 курсов физико-математического факультета, обучающихся по специальностям «Информатика» с дополнительной специальностью «Математика» (IV семестр) и «Математика» с дополнительной специальностью «Информатика» (V семестр), предполагает решение рекуррентных соотношений. В настоящее издание включены задачи на вычисление однородных и неоднородных линейных рекуррентных соотношений. Поводом для написания практикума послужило то обстоятельство, что у студентов практически нет навыков решения задач по данному курсу. Одной из причин является отсутствие доступного учебника или сборника задач. Задачи из предлагаемого практикума помогут каждому из студентов (индивидуально) разобраться с основными методами и приемами решения задач. С целью более легкого освоения материала в начале пособия рассмотрены все типы задач, предлагаемых для самостоятельного решения. В конце помещен список рекомендуемой литературы, которая поможет глубже изучить данный предмет. Тема «Рекуррентные соотношения» близка к школьному курсу (арифметические и геометрические прогрессии, последовательность квадратов и кубов натуральных чисел, и т. п.), поэтому не требует от студентов предварительного изучения каких-либо других дисциплин. Основы теории рекуррентных соотношений (возвратных последовательностей) были разработаны и опубликованы в 20-х гг. XVIII в. французским математиком А. Муавром и одним из первых по времени членов Петербургской Академии наук швейцарским математиком Д. Бернулли. Развёрнутую теорию дал крупнейший математик XVIII в. 4
5 петербургский академик Л. Эйлер. Из более поздних работ следует выделить изложение теории возвратных последовательностей в курсах исчисления конечных разностей, читанных знаменитыми русскими математиками академиками П. Л. Чебышевым и А. А. Марковым. Рекуррентные соотношения (от латинского слова recurrere возвращаться) играют большую роль в дискретной математике, являясь по существу в некотором смысле дискретным аналогом дифференциальных уравнений. Кроме того, они позволяют сводить данную задачу от параметров к задаче от 1 параметров, потом к задаче от 2 параметров и т. д. Последовательно уменьшая число параметров, можно дойти до задачи, которую уже легко решить. Понятие рекуррентного соотношения (возвратной последовательности) является широким обобщением понятия арифметической или геометрической прогрессии. Как частные случаи оно охватывает также последовательности квадратов или кубов натуральных чисел, последовательности цифр десятичного разложения рационального числа (и вообще любые периодические последовательности), последовательности коэффициентов частного от деления двух многочленов, расположенных по возрастающим степеням х, и т. д. 5
6 1. МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО РЕШЕНИЮ ЛИНЕЙНЫХ РЕКУРРЕНТНЫХ СООТНОШЕНИЙ 1.1. Основные понятия и определения рекуррентных (возвратных) последовательностей Будем записывать последовательности в виде a 1, a 2, a 3, a, (1) или, коротко, {a }. Если существует натуральное число k и числа α 1, α 2, α k (действительные или мнимые), такие, что, начиная с некоторого номера и для всех следующих номеров, a +k = α 1 a +k 1 + α 2 a +k α k a, (k 1), (2) то последовательность (1) называется рекуррентной (возвратной) последовательностью порядка k, а соотношение (2) рекуррентным (возвратным) уравнением порядка k. Таким образом, рекуррентная последовательность характеризуется тем, что каждый её член (начиная с некоторого из них) выражается через одно и то же количество k непосредственно предшествующих ему членов по формуле (2). Само название «рекуррентная» (а также возвратная) употребляется именно потому, что здесь для вычисления последующего члена возвращаются к предшествующим членам. Приведём несколько примеров рекуррентных последовательностей. Пример 1. Геометрическая прогрессия. Пусть имеем геометрическую прогрессию: a 1 = α, a 2 = α q, a 3 = α q 2, a = α q 1, ; (3) для неё уравнение (2) принимает вид: a +1 = q a. (4) 6
7 Здесь k = 1 и α 1 = q. Таким образом, геометрическая прогрессия является рекуррентной последовательностью первого порядка. Пример 2. Арифметическая прогрессия. В случае арифметической прогрессии a 1 = α, a 2 = α + d, a 3 = α + 2d, a = α + (1)d, имеем a +1 = a + d соотношение, не имеющее вида уравнения (2). Однако если мы рассмотрим два соотношения, написанные для двух соседних значений: a +2 = a +1 + d и a +1 = a + d, то получим из них путём почленного вычитания a +2 a +1 = a +1 a, или a +2 = 2a +1 a уравнение вида (2). Здесь k = 2, α 1 = 2, α 2 = 1. Следовательно, арифметическая прогрессия является рекуррентной последовательностью второго порядка. Пример 3. Рассмотрим старинную задачу Фибоначчи 1 о числе кроликов. В ней требуется определить число пар зрелых кроликов, образовавшихся от одной пары в течение года, если известно, что каждая зрелая пара кроликов ежемесячно рождает новую пару, причём новорождённые достигают полной зрелости в течение месяца. В этой задаче интересен отнюдь не результат, получить который совсем нетрудно, но последовательность, члены которой выражают общее число зрелых пар кроликов в начальный момент (a 1) через месяц (a 2), через два месяца (a 3) и, вообще, через месяцев (a +1). Очевидно, что a 1 = 1. Через месяц прибавится пара новорождённых, но число зрелых пар будет прежнее: a 2 = 1. Через два месяца крольчата достигнут зрелости и общее число зрелых пар будет равно двум: a 3 = 2. Пусть мы вычислили уже количество 1 Фибоначчи, или Леонардо Пизанский, итальянский средневековый математик (около 1200 г.) оставил после себя книгу «Об абаке», содержащую обширные арифметические и алгебраические сведения, заимствованные у народов Средней Азии и византийцев и творчески им переработанные и развитые. 7
8 зрелых пар через 1 месяцев a и через месяцев a +1. Так как к этому времени a ранее имевшихся зрелых пар дадут ещё a пар приплода, то через + 1 месяцев общее число зрелых пар будет: a +2 = a +1 + a. (6) Отсюда a 4 = a 3 + a 2 = 3, a 5 = a 4 + a 3 = 5, a 6 = a 5 + a 4 = 8, a 7 = a 6 + a 5 = 13,. Мы получили, таким образом, последовательность a 1 = 1, a 2 = 1, a 3 = 2, a 4 = 3, a 5 = 5, a 6 = 8, a 7 = 13, a 13 = 233, (7) в которой каждый последующий член равен сумме двух предыдущих. Последовательность эта называется последовательностью Фибоначчи, а члены её числами Фибоначчи. Уравнение (6) показывает, что последовательность Фибоначчи есть рекуррентная последовательность второго порядка. Пример 4. В качестве следующего примера рассмотрим последовательность квадратов натуральных чисел: a 1 = 1 2, a 2 = 2 2, a 3 = 3 2, a = 2,. (8) Здесь a +1 = (+ 1) 2 = и, следовательно, a +1 = a (9) Увеличивая на единицу, получим: a +2 = a (10) И, следовательно (вычитая почленно (9) из (10)), a +2 a +1 = a +1 a + 2, или a +2 = 2a +1 a + 2. (11) Увеличивая в равенстве (11) на единицу, будем иметь: a +3 = 2a +2 a ; (12) откуда (вычитая почленно (11) из (12)) a +3 a +2 = 2a +2 3a +1 + a, 8
9 или a +3 = 3a +2 3a +1 + a. (13) Мы получили рекуррентное уравнение третьего порядка. Следовательно, последовательность (8) есть рекуррентная последовательность третьего порядка. Пример 5. Рассмотрим последовательность кубов натуральных чисел: a 1 = 1 3, a 2 = 2 3, a 3 = 3 3, a = 3,. (14) Подобным же образом, как в примере 4, можно убедиться в том, что последовательность кубов натуральных чисел есть рекуррентная последовательность четвёртого порядка. Члены её удовлетворяют уравнению a +4 = 4a +3 6a a +1 a. (15) В случае простейших рекуррентных последовательностей, например арифметической и геометрической прогрессий, последовательности квадратов или кубов натуральных чисел, мы можем находить любой член последовательности, не прибегая к вычислению предшествующих членов. В случае же последовательности чисел Фибоначчи мы, на первый взгляд, не имеем возможности для этого и, чтобы вычислить тринадцатое число Фибоначчи a 13, находим предварительно, один за другим, все предшествующие члены (пользуясь уравнением a +2 = a +1 + a (6)): a 1 = 1, a 2 = 1, a 3 = 2, a 4 = 3, a 5 = 5, a 6 = 8, a 7 = 13, a 8 = 21, a 9 = 34, a 10 = 55, a 11 = 89, a 12 = 144, a 13 = 233. В ходе детального исследования структуры членов рекуррентной последовательности можно получить формулы, позволяющие вычислить в самом общем случае любой член рекуррентной последовательности, не прибегая к вычислению предшествующих членов. Другими словами, следующая задача состоит в том, чтобы отыскать формулу -го члена последовательности, зависящую только от номера. 9
10 Рекуррентное соотношение в общем случае может быть записано в виде a +k = F(, a +k 1, a +k 2, a), где F функция от k + 1 переменной, а число k называют порядком соотношения. Решением рекуррентного соотношения называется числовая последовательность b 1, b 2, b 3, b, для которой выполняется равенство: b +k = F(, b +k 1, b +k 2, b) при любом = 0, 1, 2,. Вообще говоря, произвольное рекуррентное соотношение имеет бесконечно много решений. Например, если рассмотреть рекуррентное соотношение второго порядка a +2 = a +1 + a, то ему, кроме последовательности Фибоначчи: 1, 1, 2, 3, 5, 8, 13, 21, 34,..., характеризующейся тем, что здесь a 1 = a 2 = 1, удовлетворяет ещё бесконечное множество других последовательностей, получающихся при различном выборе значений a 1 и a 2. Так, например, при a 1 = 3 и a 2 = 1 получаем последовательность: 3, 1, 2, 1, 3, 4, 7, 11, 18, 29,. Чтобы однозначно определить решение рекуррентного соотношения, необходимо задать начальные условия (начальных условий должно быть ровно столько, каков порядок рекуррентного соотношения). Решить рекуррентное соотношение значит найти формулу -го члена последовательности. К сожалению, не существует общего метода решения произвольных рекуррентных соотношений. Исключением является класс так называемых линейных рекуррентных соотношений с постоянными коэффициентами. Рекуррентное соотношение вида a +k = α 1 a +k 1 + α 2 a +k α k a, где a i некоторые числа, i = 1, 2, k, называется линейным однородным рекуррентным соотношением (ЛОРС) с постоянными коэффициентами порядка k. 10
11 Рекуррентное соотношение вида a +k = α 1 a +k 1 + α 2 a +k α k a + f(), где a i некоторые числа, i = 1, 2, k, f() 0 функция от, называется линейным рекуррентным соотношением (ЛРС) с постоянными коэффициентами порядка k Алгоритмы решения ЛОРС и ЛРС Алгоритм решения ЛОРС. Имеем ЛОРС: a +k = α 1 a +k 1 + α 2 a +k α k a. 1 шаг. Каждому ЛОРС порядка k соответствует алгебраическое уравнение степени k с теми же коэффициентами, и оно называется характеристическим уравнением ЛОРС. Составляем характеристическое уравнение x k = α 1 x k 1 + α 2 x k α k x 0 и находим его корни x i, где i = 1, k. 2 шаг. Если x i корни кратности 1 (т. е. все различны между собой), то общее решение ЛОРС имеет вид: a = c 1 (x 1) + c 2 (x 2) + c 3 (x 3) + + c k (x k) = c i x i Если x i корни кратности r i, то общее решение ЛОРС имеет вид k a = i= 1 (c 1 2 ri 1 i1 + ci2 + ci cir) (например, если корень x кратности 2, то a = (c 1 + c 2) x). i x i k i= 1 3 шаг. Коэффициенты c i находятся с помощью начальных условий. 11
12 Алгоритм решения ЛРС. Имеем ЛРС: a +k = α 1 a +k 1 + α 2 a +k α k a + f(). Функцию f() можно представить в виде R m () λ, где R m () многочлен степени m от переменной. В самом деле, например: f() = 10 3= (10 3)1 = R 1 () 1, или f() = = (2 + 3) 3 = R 2 () 3. Перепишем ЛРС в виде a +k α 1 a +k 1 α 2 a +k 2 α k a = R m () λ. 1 шаг. Выписываем соответствующий ЛОРС: a +k α 1 a +k 1 α 2 a +k 2 α k a = 0 и находим его общее решение. Для этого составляем характеристическое уравнение x k α 1 x k 1 α 2 x k 2 α k x 0 = 0 и находим его корни x i, где i = 1, k. Пусть, например, x i различные корни, тогда общее решение соответствующего ЛОРС имеет вид: a = c 1 (x 1) + c 2 (x 2) + c 3 (x 3) + + c k (x k). 2 шаг. Находим a частное решение ЛРС: а) если λ не корень характеристического уравнения x k α 1 x k 1 α 2 x k 2 α k = 0, то a = Q m () λ, где Q m () многочлен степени m от переменной; б) если λ корень характеристического уравнения x k α 1 x k 1 α 2 x k 2 α k = 0 кратности r, то a = r Q m () λ, где Q m () многочлен степени m от переменной. Далее, подставляем a в исходное ЛРС и находим коэффициенты в многочлене Q m (). 12
13 3 шаг. Находим общее решение ЛРС, оно представляет собой сумму общего решения соответствующего ЛОРС a и частного решения ЛРС a, то есть a = a + a. Коэффициенты c i находятся с помощью начальных условий Примеры решения ЛОРС и ЛРС Пользуясь приведенным алгоритмом нахождения решения ЛОРС и ЛРС, разберём несколько задач. Задача 1. Найти решение линейного однородного рекуррентного соотношения второго порядка: a +2 = 6 a +1 8 a, a 0 = 3, a 1 = Составляем характеристическое уравнение x 2 = 6 x 8 x 0 и находим его корни. x 2 6x + 8 = 0; x 1 = 2, x 2 = 4 корни различные, следовательно, их кратность равна Находим общее решение ЛОРС: a = c 1 (x 1) + c 2 (x 2) = c c Так как заданы начальные условия, то коэффициенты c 1 и c 2 определяются однозначно. a 0 = c c = c 1 + c 2 = 3; a 1 = c c = 2c 1 + 4c 2 = 4. Получили систему: c1 + c2 = 3, 2c1 + 4c2 = 4. Решая её, найдём коэффициенты: c 1 = 8, c 2 = 5. Таким образом, решение ЛОРС имеет вид a = Задача 2. Найти решение линейного однородного рекуррентного соотношения: 13
14 a +2 = 6 a +1 9 a, a 0 = 5, a 1 = Составляем характеристическое уравнение x 2 = 6x 9 и находим его корни. x 2 6x + 9 = 0; (x 3) 2 = 0; x 1 = x 2 = 3 два корня, при этом x 1 и x 2 совпали, следовательно, кратность корня равна Находим общее решение ЛОРС: a = (c 1 + c 2) (x 1) = (c 1 + c 2) С помощью начальных условий определяем коэффициенты c 1 и c 2: a 0 = (c 1 + c 2 0) 3 0 = c 1 = 5; a 1 = (c 1 + c 2 1) 3 1 = (c 1 + c 2) 3 = 6. Получили систему c1 = 5, c1 + c2 = 2. Решая её, найдём коэффициенты c 1 = 5, c 2 = 3. Таким образом, решение ЛОРС имеет вид: a = (5 3) 3. Замечание. Как известно, корнями квадратного уравнения могут служить рациональные, иррациональные, комплексные числа и т. п. Метод решения линейных рекуррентных соотношений с такими корнями решается аналогично. Задача 3. Найти решение линейного однородного рекуррентного соотношения третьего порядка: a +3 = 3 a a +1 8 a, a 0 = 9, a 1 = 9, a 2 = Составляем характеристическое уравнение x 3 = 3 x x 8 и находим его корни. x 3 3x 2 6x + 8 = 0; (x 1)(x + 2)(x 4) = 0; x 1 = 1, x 2 = 2, x 3 = 4 корни различные, следовательно, их кратность равна Находим общее решение ЛОРС: a = c 1 (x 1) + c 2 (x 2) + c 3 (x 3) = c c 2 (2) + c
15 3. С помощью начальных условий, находим коэффициенты c 1, c 2 и c 3. a 0 = c c 2 (2) 0 + c = c 1 + c 2 + c 3 = 9; a 1 = c c 2 (2) 1 + c = c 1 2c 2 + 4c 3 = 9; a 2 = c c 2 (2) 2 + c = c 1 + 4c c 3 = 9. c1 + c2 + ñ3 = 9, Решая систему c1 2c2 + 4c3 = 9, получим c 1 = 7, c 2 = 4, c 3 = 2. Таким c1 + 4c2 + 16c3 = 9, образом, решение ЛОРС имеет вид: a = (2) 2 4. Задача 4. Найти решение линейного однородного рекуррентного соотношения третьего порядка: a +3 = a a +1 3 a, a 0 = 6, a 1 = 15, a 2 = Составляем характеристическое уравнение x 3 = x 2 + 5x 3 и находим его корни. x 3 + x 2 5x + 3 = 0; (x 1) 2 (x + 3) = 0; x 1 = x 2 = 1 корень кратности 2; x 3 = 3 корень кратности Находим общее решение ЛОРС: a = (c 1 + c 2) (x 1) + c 3 (x 3) = (c 1 + c 2) 1 + c 3 (3). 3. С помощью начальных условий находим коэффициенты c 1, c 2 и c 3. a 0 = (c 1 + c 2 0) c 3 (3) 0 = c 1 + c 3 = 6; a 1 = (c 1 + c 2 1) c 3 (3) 1 = c 1 + c 2 3c 3 = 15; a 2 = (c 1 + c 2 2) c 3 (3) 2 = c 1 + 2c 2 + 9c 3 = 8. c1 + ñ3 = 6, Решая систему c1 + c2 3c3 = 15, получим c 1 = 8, c 2 = 1 и c 3 = 2. Таким c1 + 2c2 + 9c3 = 8, образом, решение ЛОРС имеет вид: a = (8 +) 1 2 (3). 15
16 Задача 5. Найти решение линейного рекуррентного соотношения второго порядка: Перепишем ЛРС в виде a +2 = 18 a a + 128, a 0 = 5, a 1 = 2. a a a = () 1. Выписываем соответствующий ЛОРС: a a a = 0. Составляем характеристическое уравнение и находим его корни. x 2 18x + 81 = 0; (x 9) 2 = 0; x 1 = x 2 = 9 корни характеристического уравнения совпали, следовательно, их кратность равна 2. Тогда общее решение a = (c 1 + c 2) (x 1) = (c 1 + c 2) Находим a частное решение ЛРС. По условию f() = R m () λ = = = R 0 () λ, где R 0 () = 128 многочлен нулевой степени от переменной, а λ = 1 не корень характеристического уравнения соответствующего ЛОРС. Следовательно, a = Q m () λ = Q 0 () 1, где Q 0 () многочлен нулевой степени от переменной, в общем виде Q 0 () = с. Таким образом, a = с 1. Далее, подставляем a в исходное ЛРС () и находим коэффициент с в многочлене Q 0 (): с с с 1 = ; с 18с + 81с = 128; 64с = 128; с = 2. Следовательно, получили a = с 1 = 2 1 = 2. 16
17 3. Находим общее решение ЛРС, оно представляет собой сумму общего решения соответствующего ЛОРС a и частного решения ЛРС a, то есть a = a + a = (c 1 + c 2) Осталось с помощью начальных условий найти коэффициенты c 1, и c 2. a 0 = (c 1 + c 2 0) = c = 5; a 1 = (c 1 + c 2 1) = 9c 1 + 9c = 2; Решая систему c1 + 2 = 5, 9c1 + 9c2 + 2 = 2, получим c 1 = 3, c 2 = 3. Таким образом, решение ЛРС имеет вид: a = (3 3) Задача 6. Найти решение линейного рекуррентного соотношения: a +2 = 10 a a , a 0 = 7, a 1 = 50. Перепишем ЛРС в виде a a a = Выписываем соответствующий ЛОРС: a a a = 0; составляем характеристическое уравнение и находим его корни. x 2 10 x + 25 = 0; (x 5) 2 = 0; x 1 = x 2 = 5 корень кратности 2. Тогда общее решение ЛОРС имеет вид: a = (c 1 + c 2) (x 1) = (c 1 + c 2) Находим a частное решение ЛРС. По условию f() = R m () λ = 50 5 = R 0 () λ, где R 0 () = 50 многочлен нулевой степени от переменной, а λ = 5 совпадает с корнем x 1 кратности 2 характеристического уравнения соответствующего ЛОРС. Следовательно, a = r Q m () λ = = 2 Q 0 () 5, где Q 0 () = с многочлен нулевой степени от переменной. Таким образом, a = 2 с 5. Далее, подставляем a в исходное ЛРС и находим коэффициент с: 17
18 с (+ 2) с (+ 1) с 2 5 = 50 5 (разделим на 5 0); 25с (+ 2) 2 50с (+ 1) с 2 = 50; с () 2с () + с 2 = 2; с = 1. Следовательно, a = 2 с 5 = Выписываем общее решение ЛРС: a = a + a = (c 1 + c 2) С помощью начальных условий находим коэффициенты c 1, и c 2: a 0 = (c 1 + c 2 0) = c 1 = 7; a 1 = (c 1 + c 2 1) = 5c 1 + 5c = 50; Решая систему c1 = 7, c1 + c2 + 1 = 10, получим c 1 = 7, c 2 = 2. Таким образом, решение ЛРС имеет вид: a = (7 + 2) = () 5. Задача 7. Найти решение линейного рекуррентного соотношения: a +2 = 6 a +1 8 a , a 0 = 0, a 1 = 11. Перепишем ЛРС в виде a +2 6 a a = Выписываем соответствующий ЛОРС: a +2 6 a a = 0; составляем характеристическое уравнение и находим его корни. x 2 6x + 8 = 0; x 1 = 2, x 2 = 4 корни кратности равной 1. Тогда общее решение ЛОРС имеет вид a = c 1 (x 1) + c 2 (x 2) = c c Находим a частное решение ЛРС. По условию f() = R m () λ = = (3 + 2) 1 = R 1 () λ, где R 1 () = многочлен первой степени от переменной, а λ = 1 не корень характеристического уравнения соответствующего ЛОРС. Следовательно, a = Q m () λ = Q 1 () 1, где Q 1 () многочлен первой степени от переменной, в общем виде Q 1 () = = a + b. Таким образом, a = (a + b) 1. 18
19 a и b: Далее, подставляем a в исходное ЛРС и находим коэффициенты (a (+ 2) + b) (a (+ 1) + b) (a + b) 1 = 3 + 2; 25с (+ 2) 2 50с (+ 1) с 2 = 3 + 2; 3a + (3b 4a) = Таким образом, получили, что два многочлена равны, а тогда равны соответствующие коэффициенты: 3a = 3, a = 1, 3b 4a = 2 b = 2. Следовательно, a = (a + b) 1 = Выписываем общее решение ЛРС: a = a + a = c c (+ 2). С помощью начальных условий находим коэффициенты c 1, и c 2: a 0 = c c (0 + 2) = 0; a 1 = c c (1 + 2) = 11; Решая систему c1 + c2 = 2, 2c1 + 4c2 = 14, получим c 1 = 3, c 2 = 5. Таким образом, решение ЛРС имеет вид: a = Задача 8. Найти решение линейного рекуррентного соотношения: a +2 = 5 a +1 6 a + (10 4) 2, a 0 = 5, a 1 = 12. Перепишем ЛРС в виде a +2 5 a a = (10 4) Выписываем соответствующий ЛОРС: a +2 5 a a = 0; составляем характеристическое уравнение и находим его корни. x 2 5x + 6 = 0; x 1 = 3, x 2 = 2 корни различные кратности 1. Тогда общее решение ЛОРС имеет вид: a = c 1 (x 1) + c 2 (x 2) = c c
20 2. Находим a частное решение ЛРС. По условию имеем, что f() = = R m () λ = (10 4) 2 = R 1 () λ, где R 1 () = (10 4) многочлен первой степени от переменной, а λ = 2, то есть совпадает с корнем характеристического уравнения соответствующего ЛОРС. Следовательно, a = r Q m () λ = 1 Q 1 () 2, где Q 1 () многочлен первой степени от переменной, в общем виде Q 1 () = a + b. Таким образом, получаем a = = (a + b) 2. Далее, подставляем a в исходное соотношение и находим коэффициенты a и b. (+ 2)(a (+ 2) + b) (+ 1) (a (+ 1) + b) (a + b) 2 = = (10 4) 2. Разделим это уравнение на 2 0: 4(+ 2)(a (+ 2) + b) 10(+ 1) (a (+ 1) + b) + 6(a + b) = 10 4; 4a + (6a 2b) = Таким образом, получили, что два многочлена равны, а тогда равны соответствующие коэффициенты: 4a = 4, a = 1, 6a 2b = 10 b = 2. Следовательно, a = (a + b) 2 = (2) Выписываем общее решение ЛРС, то есть a = a + a = c c (2) 2. С помощью начальных условий находим коэффициенты c 1, и c 2. a 0 = c c (0 2) 2 0 = 5; a 1 = c c (1 2) 2 1 = 12. Решая систему c1 + c2 = 5, 3c1 + 2c2 = 14, получим c 1 = 4, c 2 = 1. Таким образом, решение ЛРС имеет вид: a = (2) 2 = () 2. 20
21 Задача 9. Найти решение линейного рекуррентного соотношения: a +2 = 8 a a , a 0 = 1, a 1 = 7. Перепишем ЛРС в виде a +2 8 a a = () Выписываем соответствующий ЛОРС: a +2 8 a a = 0; составляем характеристическое уравнение и находим его корни. x 2 8 x + 16 = 0; x 1 = x 2 = 4 корни совпали, следовательно, кратность корня равна 2. Тогда общее решение ЛОРС имеет вид: a = (c 1 + c 2) (x 1) = (c 1 + c 2) Находим a частное решение ЛРС. По условию f() = R m () λ = = () 1 = R 2 () λ, где R 2 () = многочлен второй степени от переменной, а λ = 1 не совпадает с корнем характеристического уравнения соответствующего ЛОРС. Следовательно, a = Q m () λ = Q 2 () 1, где Q 2 () многочлен второй степени от переменной, в общем виде Q 2 () = a 2 + b + c. Таким образом, a = = (a 2 + b + c) 1. Далее, подставляем a в исходное соотношение и находим коэффициенты a, b и c. (a (+ 2) 2 + b (+ 2)+ c) (a (+ 1) 2 + b (+ 1) + c) (a b + c) 1 = () 1 ; a(+ 2) 2 + b(+ 2)+ c 8a(+ 1) 2 8b(+ 1) 8c + 16a b + 16c = = ; 9a 2 12a + 9b 4a 6b + 9c = Таким образом, получили, что два многочлена равны, а тогда равны соответствующие коэффициенты: 9a = 9, 12a + 9b = 6, 4a 6b + 9c = 2 a = 1, b = 2, c = 2. 21
22 Следовательно, a = (a 2 + b + c) 1 = Выписываем общее решение ЛРС, то есть a = a + a = (c 1 + c 2) (). С помощью начальных условий, находим коэффициенты c 1, и c 2. a 0 = (c 1 + c 2 0) () = 1; a 1 = (c 1 + c 2 1) () = 7. Решая систему c1 + 2 = 1, 4c1 + 4c2 + 5 = 7, получим c 1 = 1, c 2 = 2. Таким образом, решение ЛРС имеет вид: a = (1 2)
23 2. ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ 2.1. Задачи для решения ЛОРС и ЛРС Линейные однородные рекуррентные соотношения второго порядка 1. a +2 = 9 a a, a 0 = 2, a 1 = a +2 = 3,5 a +1 2,5 a, a 0 = 3,5, a 1 = a +2 = 8 a a, a 0 = 4, a 1 = a +2 = 2 a a, a 0 = 3, a 1 = i. 5. a +2 = 10 a a, a 0 = 3, a 1 = a +2 = 6 a a, a 0 = 0, a 1 = 2i a +2 = 8 a a, a 0 = 2, a 1 = a +2 = 4 a a, a 0 = 7, a 1 = a +2 = a +1 + a, a 0 = 2, a 1 = a +2 = 8 a a, a 0 = 8, a 1 = a +2 = () a a, a 0 = 7, a 1 = a +2 = 5 a +1 4 a, a 0 = 0, a 1 = a +2 = 2 a +1 5 a, a 0 = 5, a 1 = 6i a +2 = 3 a a, a 0 = 7, a 1 = a +2 = 6 a +1 9 a, a 0 = 8, a 1 = a +2 = 6 a a, a 0 = 3, a 1 = 9 2i. 17. a +2 = a a, a 0 = 4, a 1 = a +2 = 14 a a, a 0 = 5, a 1 = a +2 = 8 a a, a 0 = 2, a 1 = a +2 = 7 a a, a 0 = 5, a 1 = a +2 = 2 a +1 + a, a 0 = 2, a 1 =
24 1 22. a +2 = a +1 a, a 0 = 4, a 1 = a +2 = 4 a +1 a, a 0 = 12, a 1 = a +2 = a a, a 0 = 2, a 1 = a +2 = 2 a a, a 0 = 8, a 1 = a +2 = 6 a +1 9 a, a 0 = 12, a 1 = a +2 = 4 a +1 5 a, a 0 = 5, a 1 = 10 i a +2 = 3 a +1 a, a 0 = 8, a 1 = a +2 = 14 a a, a 0 = 5, a 1 = a +2 = 4 a a, a 0 = 2, a 1 = a +2 = 4 a +1 5 a, a 0 = 3, a 1 = 6 7i. 32. a +2 = a a, a 0 = 5, a 1 = a +2 = 16 a a, a 0 = 7, a 1 = a +2 = 5 a +1 6 a, a 0 = 2, a 1 = a +2 = 10 a a, a 0 = 2, a 1 = 10 4i a +2 = 6 a +1 5 a, a 0 = 11, a 1 = a +2 = 2 a a, a 0 = 11, a 1 = a +2 = 6 a a ; a 0 = 3, a 1 = 0. Линейные однородные рекуррентные соотношения третьего порядка 39. a +3 = 7 a a a, a 0 = 1, a 1 = 3, a 2 = a +3 = 4 a +2 a +1 6 a, a 0 = 4, a 1 = 5, a 2 = a +3 = 6 a a a, a 0 = 5, a 1 = 8, a 2 = a +3 = 8 a a a, a 0 = 4, a 1 = 31, a 2 = a +3 = 5 a +2 3 a +1 9 a, a 0 = 1, a 1 = 3, a 2 = a +3 = 15 a a a, a 0 = 8, a 1 = 40, a 2 =
25 45. a +3 = 27 a a, a 0 = 6, a 1 = 3, a 2 = a +3 = 6 a a a, a 0 = 15, a 1 = 32, a 2 = a +3 = 15 a a a, a 0 = 1, a 1 = 20, a 2 = a +3 = 9 a a a, a 0 = 0, a 1 = 4, a 2 = a +3 = 2 a a +1 6 a, a 0 = 4, a 1 = 5, a 2 = a +3 = 4 a +2 5 a a, a 0 = 2, a 1 = 6, a 2 = a +3 = 6 a +2 5 a a, a 0 = 4, a 1 = 2, a 2 = a +3 = 3 a a a, a 0 = 2, a 1 = 17, a 2 = a +3 = 9 a a a, a 0 = 1, a 1 = 3, a 2 = a +3 = 6 a a +1 6 a, a 0 = 13, a 1 = 31, a 2 = a +3 = 5 a +2 3 a +1 9 a, a 0 = 3, a 1 = 14, a 2 = a +3 = a a +1 4 a, a 0 = 2, a 1 = 1, a 2 = a +3 = 3 a a a, a 0 = 2, a 1 = 3, a 2 = a +3 = 12 a a a, a 0 = 2, a 1 = 16, a 2 = a +3 = 4 a a a, a 0 = 0,2, a 1 = 6, a 2 = a +3 = 8 a a a, a 0 = 3, a 1 = 13, a 2 = a +3 = 4 a a a, a 0 = 3, a 1 = 29, a 2 = a +3 = 5 a +2 7 a a, a 0 = 11, a 1 = 34, a 2 = a +3 = 11 a a a, a 0 = 27, a 1 = 17, a 2 = a +3 = 12 a a a, a 0 = 1, a 1 = 37, a 2 = a +3 = 3 a a a, a 0 = 11, a 1 = 23, a 2 = a +3 = 7 a a a, a 0 = 3, a 1 = 6, a 2 = a +3 = 4 a a a, a 0 = 4, a 1 = 1, a 2 = 4.; 68. a +3 = 7 a a a, a 0 = 1, a 1 = 0, a 2 = a +3 = 5 a a a, a 0 = 6, a 1 = 0, a 2 = a +3 = 5 a +2 3 a a, a 0 = 10, a 1 = 1, a 2 = a +3 = 3 a +2 3 a +1 + a, a 0 = 2, a 1 = 4, a 2 = a +3 = 3 a a a, a 0 = 6, a 1 = 5, a 2 =
26 73. a +3 = 10 a a a, a 0 = 0, a 1 = 1, a 2 = a +3 = 8 a a a, a 0 = 8, a 1 = 23, a 2 = a +3 = 5 a +2 8 a +1 4 a, a 0 = 11, a 1 = 15, a 2 = a +3 = a a a, a 0 = 6, a 1 = 5, a 2 = a +3 = 10 a a a, a 0 = 1, a 1 = 2, a 2 = a +3 = a a a, a 0 = 1, a 1 = 14, a 2 = a +3 = 2 a +2 + a a, a 0 = 10, a 1 = 1, a 2 = a +3 = 5 a +2 8 a a, a 0 = 9, a 1 = 9, a 2 = a +3 = 8i a a +1 10i a, a 0 = 8, a 1 = 14i, a 2 = 38. Линейные рекуррентные соотношения первого порядка 82. a +1 = 4 a + 6, a 0 = a +1 = a + + 1, a 0 = a +1 = 5 a , a 0 = a +1 = 3 a + 5 2, a 0 = a +1 = 3 a + (4) 5 1, a 0 = a +1 = 4 a + 8 4, a 0 = a +1 = 3 a , a 0 = 14. Линейные рекуррентные соотношения второго порядка 89. a +2 = 7 a a + 10, a 0 = 4, a 1 = a +2 = 10 a a + 32, a 0 = 1, a 1 = a +2 = 6 a +1 9 a 2 3, a 0 = 0, a 1 = a +2 = 7 a a , a 0 = 3, a 1 = a +2 = 9 a a + (18 20) 2, a 0 = 6, a 1 = a +2 = 8 a +1 7 a , a 0 = 9, a 1 = a +2 = 4 a +1 9 a , a 0 = 15, a 1 = 27 i a +2 = 12 a a , a 0 = 13, a 1 = 6. 26
А А КИРСАНОВ КОМПЛЕКСНЫЕ ЧИСЛА ПСКОВ ББК 57 К45 Печатается по решению кафедры алгебры и геометрии, и редакционно-издательского совета ПГПИ им СМ Кирова Рецензент: Медведева ИН, кандидат физ мат наук, доцент
Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования Ухтинский государственный технический университет (УГТУ) ПРЕДЕЛ ФУНКЦИИ Методические
ДИФФЕРЕНЦИАЛЬНЫЕ УРАВНЕНИЯ Общие понятия Дифференциальные уравнения имеют многочисленные и самые разнообразные приложения в механике физике астрономии технике и в других разделах высшей математики (например
Министерство образования и науки Российской Федерации Московский физико-технический институт (государственный университет) Заочная физико-техническая школа МАТЕМАТИКА Тождественные преобразования. Решение
Министерство сельского хозяйства Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования «Пермская государственная сельскохозяйственная академия имени
Министерство образования Российской Федерации Российский государственный университет нефти и газа имени ИМ Губкина ВИ Иванов Методические указания к изучению темы «ДИФФЕРЕНЦИАЛЬНЫЕ УРАВНЕНИЯ» (для студентов
СИСТЕМЫ ЛИНЕЙНЫХ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ С ПОСТОЯННЫМИ КОЭФФИЦИЕНТАМИ Приведение к одному уравнению -го порядка С практической точки зрения очень важны линейные системы с постоянными коэффициентами
ПРАКТИЧЕСКОЕ ЗАНЯТИЕ Интегрирование рациональных дробей Рациональной дробью называется дробь вида P Q, где P и Q многочлены Рациональная дробь называется правильной, если степень многочлена P ниже степени
03 Математика в высшем образовании УДК 54; 5799 СОДЕРЖАНИЕ И ТЕХНОЛОГИИ МАТЕМАТИЧЕСКОГО ОБРАЗОВАНИЯ В ВУЗЕ НЕКОТОРЫЕ МЕТОДЫ СУММИРОВАНИЯ ЧИСЛОВЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ А В Ласунский Новгородский государственный
ОБЫКНОВЕННЫЕ ДИФФЕРЕНЦИАЛЬНЫЕ УРАВНЕНИЯ ПЕР- ВОГО ПОРЯДКА.. Основные понятия Дифференциальным уравнением называется уравнение, в которое неизвестная функция входит под знаком производной или дифференциала.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего образования «ЮЖНО-УРАЛЬСКИЙ ГОСУДАРСТВЕННЫЙ ГУМАНИТАРНО- ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ»
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Национальный исследовательский Нижегородский государственный университет им НИ Лобачевского НП Семерикова АА Дубков АА Харчева РЯДЫ АНАЛИТИЧЕСКИХ ФУНКЦИЙ
А. И. Козко В. Г. Чирский Задачи с параметром и другие сложные задачи Москва Издательство МЦНМО 2007 УДК 512 ББК 22.141 К59 К59 Козко А. И., Чирский В. Г. Задачи с параметром и другие сложные задачи. М.:
ЛЕКЦИЯ N Дифференциальные уравнения высших порядков, методы решения Задача Коши Линейные дифференциальные уравнения высших порядков Однородные линейные уравнения Дифференциальные уравнения высших порядков,
КАЗАНСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ ИНСТИТУТ МАТЕМАТИКИ И МЕХАНИКИ ИМ. Н.И.ЛОБАЧЕВСКОГО Кафедра теории и технологий преподавания математики и информатики Фалилеева М.В. Первые шаги в решении уравнений и
Вестник КГУ им НА Некрасова 6 Скибицкий ЭГ Шкабура ОВ Стиль мышления как стратегия решения задач с использованием компьютера // Информатика и образование С 7 Яковлева НО Теоретико-методологические основы
УДК 373:512 ББК 22.14я721 М52 М52 Мерзляк, А.Г. Математика: Новый полный справочник для подготовки к ОГЭ / А.Г. Мерзляк, В.Б. Полонский, М.С. Якир. Москва: АСТ, 2017. 447, с.: ил. ISBN 978-5-17-096816-9
Образовательной программе на 2016-2017 учебный год (7-11 классы), утвержденной приказом МБОУ «Средняя общеобразовательная школа 21» г. Калуги 145/01-08 от 26.08.2016 РАБОЧАЯ ПРОГРАММА Предмета АЛГЕБРА
Тема 14 «Алгебраические уравнения и системы нелинейных уравнений» Многочленом степени n называется многочлен вида P n () a 0 n + a 1 n-1 + + a n-1 + a n, где a 0, a 1, a n-1, a n заданные числа, a 0,
Лекция ИНТЕГРИРОВАНИЕ РАЦИОНАЛЬНЫХ ДРОБЕЙ Рациональные дроби Интегрирование простейших рациональных дробей Разложение рациональной дроби на простейшие дроби Интегрирование рациональных дробей Рациональные
10 класс, базовый уровень Задание 1 Вариант 0 (демонстрационный, с решениями) Заочная математическая школа 009/010 учебный год 1 Представьте выражение в виде многочлена стандартного вида и найдите его
Тема: Общая теория систем линейных уравнений А. Я. Овсянников Уральский федеральный университет Институт математики и компьютерных наук кафедра алгебры и дискретной математики алгебра и геометрия для
Муниципальное казенное общеобразовательное учреждение средняя общеобразовательная школа 3 города Пудожа Рассмотрено на заседании МО математики и информатики Протокол 1 от 29.08.2016 Руководитель МО Купцова
57 Рассмотрим интегрирование простейшей рациональной дроби четвертого типа (M N) d () p q p Сделаем замену переменной, положив d. где a p q. Тогда Интеграл M N d p p p q q a, M p N Mp q d M (p q) p
Тема 1-8: Комплексные числа А. Я. Овсянников Уральский федеральный университет Институт математики и компьютерных наук кафедра алгебры и дискретной математики алгебра и геометрия для механиков (1 семестр)
Лекции -6 Глава Обыкновенные дифференциальные уравнения Основные понятия Различные задачи техники естествознания экономики приводят к решению уравнений в которых неизвестной является функция одной или
Занятие. Степень с произвольным действительным показателем, её свойства. Степенная функция, её свойства, графики.. Вспомнить свойства степени с рациональным показателем. a a a a a для натурального раз
Муниципальное бюджетное общеобразовательное учреждение средняя общеобразовательная школа 4 г. Балтийска Рабочая программа учебного предмета «Алгебра» 8 класс, базовый уровень Балтийск 2017 год 1 1. Пояснительная
ЭЛЕМЕНТЫ ОПЕРАЦИОННОГО ИСЧИСЛЕНИЯ ИЗДАТЕЛЬСТВО ТГТУ МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ГОУ ВПО «Тамбовский государственный технический университет» ЭЛЕМЕНТЫ ОПЕРАЦИОННОГО ИСЧИСЛЕНИЯ
Рассмотрим первый способ решения СЛУ по правилу Крамера для системы трех уравнений с тремя неизвестными: Ответ рассчитывается по формулам Крамера: D, D1, D2, D3 это определители Определителем третьего
Алгебраические многочлены. 1 Алгебраические многочлены степени n над полем K Определение 1.1 Многочленом степени n, n N {0}, от переменной z над числовым полем K называется выражение вида: fz = a n z n
Модуль Тема Функциональные последовательности и ряды Свойства равномерной сходимости последовательностей и рядов Степенные ряды Лекция Определения функциональных последовательностей и рядов Равномерно
ГАОУ ВПО ДАГЕСТАНСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ НАРОДНОГО ХОЗЯЙСТВА Бабичева ТА Кафедра высшей математики УЧЕБНОЕ ПОСОБИЕ ПО ДИСЦИПЛИНЕ ДИФФЕРЕНЦИАЛЬНЫЕ УРАВНЕНИЯ Махачкала УДК 5(75) ББК я 7 Учебное пособие
Теоремы «пифагоровых троек» Мурсеев Михаил Петрович Существует различные методы определения вариантов «пифагоровых треугольников» Иногда их называют «пифагоровы тройки» или «египетские треугольники» К
1. Требования к уровню подготовки учащихся. Учащийся, заканчивающий 9 класс, должен уметь: выполнять арифметические действия, сочетая устные и письменные приёмы; находить значения корня натуральной степени,
Федеральное агентство по образованию Томский государственный университет систем управления и радиоэлектроники Кафедра высшей математики (ВМ) Приходовский М.А. ЛИНЕЙНЫЕ ОПЕРАТОРЫ И КВАДРАТИЧНЫЕ ФОРМЫ Практическое
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СПЕЦИАЛИЗИРОВАННЫЙ УЧЕБНО-НАУЧНЫЙ ЦЕНТР Математика 9 класс СУММИРОВАНИЕ КОНЕЧНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ Новосибирск
Министерство образования и науки Российской Федерации ФГБОУ ВО «Тверской государственный университет» УТВЕРЖДАЮ Руководитель ООП Цветков ВП 2015г Рабочая программа дисциплины (с аннотацией) Теория чисел
ПРОИЗВОДНАЯ, ЕЕ ГЕОМЕТРИЧЕСКИЙ И ФИЗИЧЕСКИЙ СМЫСЛ Приращением функции = f() называется разность f f, где - приращение аргумента Из рис видно, что g () Рис Производной функции = f() в точке называется конечный
Лекция 2. Свойства биномиальных коэффициентов. Подсчет сумм и метод производящих функций (конечный случай). Полиномиальные коэффициенты. Оценки биномиальных и полиномиальных коэффициентов. Оценки сумм
1. Пояснительная записка. Рабочая программа по предмету «Алгебра» для глухих обучающихся 8, 9, 10, 11 классов, разработана на основе программы общеобразовательных учреждений «Алгебра» 7-9 классы / авторы
ББК 74.262.21 Б94 Б94 Буцко Е.В. Алгебра: 7 класс: методическое пособие / Е.В. Буцко, А.Г. Мерзляк, В.Б. Полонский и др. М. : Вентана-Граф, 2017. 104 с. : ил. ISBN 978-5-360-08673-4 Пособие содержит
Аннотация к рабочей программе по алгебре Класс: 7 Уровень изучения учебного материала: базовый УМК, учебник Рабочая программа по алгебре для 7 класса составлена на основе программы «Алгебра» (Ю.Н. Макарычев,
I вариант 8В класс, 4 октября 007 1 Вставьте пропущенные слова: Определение 1 Арифметическим квадратным корнем из число, которого равен a из числа a (a 0) обозначается так: выражением Действие нахождения
Министерство образования и науки Российской Федерации Федеральное агентство по образованию Пензенский государственный университет Руденко АК, Руденко МН, Семерич ЮС СБОРНИК ЗАДАЧ С РЕШЕНИЯМИ ДЛЯ ПОДГОТОВКИ
ББК.4я7т+.4я7.6 М5 Учебник включён в федеральный перечень Мерзляк А.Г. М5 Алгебра: 9 класс: учебник для учащихся общеобразовательных организаций / А.Г. Мерзляк, В.М. Поляков. М. : Вентана-Граф, 07. 368
Математический анализ Раздел: дифференциальные уравнения Тема: Линейные однородные системы ДУ с постоянными коэффициентами Лектор Пахомова ЕГ 0 г 4 Системы линейных однородных дифференциальных уравнений
Í. Â. Áîãîìîëîâ ÌÀÒÅÌÀÒÈÊÀ ÇÀÄÀ È Ñ ÐÅØÅÍÈßÌÈ àñòü 1 УЧЕБНОЕ ПОСОБИЕ ДЛЯ СПО 2-е издание, исправленное и дополненное Ðåêîìåíäîâàíî Ó åáíî-ìåòîäè åñêèì îòäåëîì ñðåäíåãî ïðîôåññèîíàëüíîãî îáðàçîâàíèÿ â êà
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Факультет прикладной математики и кибернетики Кафедра теории вероятностей и математической статистики ПРЕДЕЛЫ Методическое
Раздел 2 Теория пределов Тема Числовые последовательности Определение числовой последовательности 2 Ограниченные и неограниченные последовательности 3 Монотонные последовательности 4 Бесконечно малые и
ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ Московский государственный технический университет имени Н.Э. Баумана Факультет «Фундаментальные науки» Кафедра «Математическое моделирование» À.Í. Êàíàòíèêîâ,
Иррациональные уравнения и неравенства Оглавление Иррациональные уравнения Метод возведения обеих частей уравнения в одну и ту же степень Задание Задание Задание Замена иррационального уравнения смешанной
Об одном обобщении чисел Стирлинга Устинов А. В. Моему учителю, Н. М. Коробову, к его 85 летию В работе вводятся обобщенные числа Стирлинга. Для них доказываются свойства, аналогичные свойствам обычных
А. Н. РУРУКИН ПОУРОЧНЫЕ РАЗРАБОТКИ ПО АЛГЕБРЕ к учебнику Ю.Н. Макарычева и др. (М.: Просвещение) НОВОЕ ИЗДАНИЕ 8 класс МОСКВА «ВАКО» 015 УДК 7:167.1:51 ББК 74.6.1 Р87 Р87 Рурукин А.Н. Поурочные разработки
Математический анализ Раздел: Неопределенный интеграл Тема: Интегрирование рациональных дробей Лектор Пахомова Е.Г. 0 г. 5. Интегрирование рациональных дробей ОПРЕДЕЛЕНИЕ. Рациональной дробью называется
Пояснительная записка Рабочая программа учебного предмета «Алгебра. 8-9 класс» составлена на основе: 1. Федерального компонента государственного стандарта основного общего и среднего (полного) общего образования
Лекция Дифференциальные уравнения -го порядка (ДУ-) Общий вид дифференциального уравнения порядка n запишется: (n) F, = 0 () Уравнение -го порядка (n =) примет вид F(,) = 0 Подобные уравнения
Тема 1-7: Определители А. Я. Овсянников Уральский федеральный университет Институт математики и компьютерных наук кафедра алгебры и дискретной математики алгебра и геометрия для механиков (1 семестр) Перестановки
МЕТОДИЧЕСКИЕ УКАЗАНИЯ К РАСЧЕТНЫМ ЗАДАНИЯМ ПО КУРСУ ВЫСШЕЙ МАТЕМАТИКИ «ОБЫКНОВЕННЫЕ ДИФФЕРЕНЦИАЛЬНЫЕ УРАВНЕНИЯ РЯДЫ КРАТНЫЕ ИНТЕГРАЛЫ» ЧАСТЬ III ТЕМА ОБЫКНОВЕННЫЕ ДИФФЕРЕНЦИАЛЬНЫЕ УРАВНЕНИЯ ОГЛАВЛЕНИЕ
Федеральное агентство по образованию Архангельский государственный технический университет строительный факультет РЯДЫ Методические указания к выполнению задания для самостоятельной работы Архангельск
Муниципальное бюджетное общеобразовательное учреждение «Лицей им. академика Б.Н. Петрова» города Смоленска «СОГЛАСОВАНО» Заместитель директора Казанцева Т.В. «29» «08» 206 г. «ПРИНЯТО» педагогическим советом
9., 9. класс Модуль 5 «Последовательности. Степени и корни» В тесте проверяются теоретическая и практическая части. Последовательности Числовые последовательности. Способы задания числовых последовательностей.