Файл: 1. Общие правила комбинаторики правила суммы, произведения и биекции. Булеан конечного множества. Примеры.docx
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 26.10.2023
Просмотров: 70
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
общим , если оно зависит от произвольных постоянных , и путем подбора этих постоянных можно получить любое решение данного соотношения. Например, для соотношения
общим решением будет .
Найти число двоичных слов длины , в которых никакие две единицы не идут подряд.
Будем называть такие слова правильными и обозначим их число через . Разобьем множество этих правильных слов на два класса: слова, оканчивающиеся на ноль, и слова, оканчивающиеся на единицу. Обозначим количество слов в этих классах и соответственно. По правилу сложения
(5)
Очевидно, что у слова, оканчивающегося на ноль, первые символов образуют правильное слово длины , или другими словами, имеется биекция между множеством правильных слов длины , оканчивающихся на ноль, и множеством правильных слов длины , то есть .
Если правильное слово длины оканчивается на единицу, то предыдущий символ этого слова должен быть нулем, а первые символа должны образовывать правильное слово длины . Как и в предыдущем случае, снова имеем биекцию между множеством правильных слов длины , оканчивающихся на единицу, и множеством правильных слов длины . Следовательно. . Из формулы (5) получаем рекуррентное соотношение .
Пример 2. Задача о расстановке скобок в выражении с неассоциативной бинарной операцией.Пусть “ ” обозначает некоторую бинарную операцию. Рассмотрим выражение , в котором символ обозначает некоторую бинарную неассоциативную операцию. Сколько имеется различных способов расстановки скобок в этом выражении?
Как пример неассоциативной операции можно привести векторное произведение. Другой пример – обычное сложение и умножение, выполняемое на компьютере. В силу того, что представление каждого числа в памяти компьютера ограничено определенным количеством разрядов, при выполнении каждой операции возникает погрешность и суммарный результат этих погрешностей зависит от расстановки скобок. Пусть – машинный ноль. Это означает, что . Тогда , в то время как .
Обозначим число всевозможных способов расстановки скобок через . Тогда
;
.
Назовем операцию условно произведением. Для произвольного разобьем все способы расстановки скобок на классы, включив в -ый класс способы, при которых сначала вычисляется произведение первых и последних операндов с какой-то расстановок скобок, а потом вычисляется их произведение: (7)
где .
По определению количество способов расстановки скобок для вычисления первых операндов равно , последних – . По правилу произведения число расстановок скобок для выражения (4) равно . По правилу сложения , (8)
Например, .
Пусть функция в соотношении (1) является линейной
, , (9)
где – некоторые числа. Такие соотношения называют линейными соотношениями -го порядка с постоянными коэффициентами
Лемма 1. Пусть – решение соотношения (10), а – любое число. Тогда последовательность также является решением этого соотношения.
Лемма 2. Пусть и – решения соотношения (10). Тогда последовательность также является решением этого соотношения.
Из этих двух простых лемм можно сделать следующий важный вывод. Совокупность всевозможных последовательностей с операциями покоординатного сложения и умножения на скаляр образует векторное пространство. Совокупность последовательностей, являющихся решениями соотношения (10), представляет собой подпространство этого пространства. Объемлющее пространство всевозможных последовательностей бесконечномерно, но подпространство решений линейного рекуррентного соотношения имеет конечную размерность, равную порядку уравнения.
Лемма 3. Размерность пространства решений рекуррентного соотношения (10) равна двум.
Из леммы 3 следует, что для определения всех решений уравнения (12) необходимо отыскать два линейно независимых решения. Любое другое решение будет представляться линейной комбинацией этих базисных решений.
Построение базисных решений зависит от корней и характеристического уравнения (14).
путем соответствующего выбора констант можно получить любое решение соотношения (10). Рассмотрим произвольное решение . Выберем константы и так, чтобы при и : (16)
Определитель линейной системы (16)
следовательно, система имеет единственное решение, а значит формула (15) – общее решения соотношения (10).
Формула Бине. Поставим задачу получить формулу в явном виде для чисел Фибоначчи. Для этого найдем решение рекуррентного соотношения (4) при условии, что . Составим характеристическое уравнение , найдем его корни и получим общее решение . Константы и определим из начальных условий: . Тогда или ,
где – золотое сечение. Формула (21) называется формулой Бине. При этом . Из формулы Бине следует, что .
10. Определение производящей функции. Свойства линейности, дифференцирования, умножения на параметр , интегрирования. Примеры.
Производящей функцией, или обычной производящей функцией, последовательности чисел называется формальный ряд (1)
где – формальная переменная. При этом будем писать .
Свойства производящих функций
Например, дифференцируя функцию , получим , то есть производящей функцией последовательности является функция : .
Дифференцируя раз функцию , будем иметь
.
После деления на получим производящую функцию для сочетаний
. (3)
3) Умножение производящей функции на соответствует сдвигу членов последовательности на одну позицию вправо. Если , то .
Например, производящей функцией последовательности (0, 1, 2, …, , …) является функция : .
В качестве примера найдем . Используем формулу бинома Ньютона
. (4)
Числа называют биномиальными коэффициентами. При : . (5)
Из равенства (5) следует, что функция является производящей для последовательности . Можно также написать . (6)
Интегрируя левую часть соотношения (5), получим
.
Для правой части имеем .
При находим .
Производящая функция для свертки последовательностей. Сверткой последовательностей и называется последовательность , элементы которой вычисляются по правилу: , , , …, , …
Операция свертки является основной в цифровой обработке сигналов: после свертывания последовательности отсчетов сигнала со специально подобранной последовательностью происходит фильтрация – усиление одних частот и подавление других.
Свертка обозначается звездочкой: .
Производящая функция свертки равна произведению производящих функций свертываемых последовательностей: .
Действительно, при перемножении и -ая степень переменной складывается из всевозможных произведений , в которых первый сомножитель из , а второй из
Формула Вандермонда. Пусть , .
По правилу свертки . С другой стороны,
.
Следовательно, .
Формула бинома Ньютона для вещественного показателя. Название формулы (4) биномом Ньютона исторически неверно, так как эту формулу хорошо знали среднеазиатские математики Омар Хайям, Гиясэддин и др. В Западной Европе задолго до Ньютона ее знал Паскаль. Заслуга же Ньютона заключалась в том, что ему удалось обобщить формулу для на случай произвольного вещественного показателя степени , если в качестве биномиальных коэффициентов использовать числа , (7)
причем вместо конечного числа слагаемых мы имеем бесконечный ряд: (8)
Из формулы (8) многие производящие функции получаются как частные случаи. Во-первых, при имеем формулу (4), так как при . Во-вторых, при , и замене на приходим к формуле (3)
Определение числа расстановок скобок в выражении с неассоциативной бинарной операцией. Ранее для числа расстановки скобок в неассоциативном произведении была получена формула (10)
Введем для последовательности производящую функцию: .
Заменим коэффициенты их выражениями из рекуррентного соотношения (10). Так как это соотношение имеет место, начиная с , то первый член отделим от суммы:
.
Последовательность представляет собой свертку последовательности с собой. В силу свойства 5) имеем . (12)
Таким образом, можно найти как решение квадратного уравнения (12): (13)
Перед корнем выбран знак минус, так как . Чтобы найти , надо разложить в ряд по степеням правую часть уравнения (13). Для этого используем формулу бинома Ньютона (8) при и : ,
где .
Умножим числитель и знаменатель последней дроби на произведение последовательных четных чисел от 2 до : .
Тогда .
Из формулы (13) получим
.
Таким образом, число расстановок скобок в неассоциативном произведении равно
.
Пусть последовательность является решением линейного рекуррентного соотношения , (14)
Для производящей функции (1) этой последовательности обозначим начальные отрезки ряда
Заменим коэффициенты, начиная с -го, по формуле (14)
. (15)
Внутреннюю сумму представим в виде
и подставим в (15):
.
Из этого уравнения найдем производящую функцию : , (16)
где , .
Сравнивая с характеристическим многочленом ,
найдем .
Если имеет корни , ,…, кратности соответственно , ,…, , то
.
Тогда
.
Раскладывая дробь (16) на простые, получим
, (17)
где – константы.
Используя степенные ряды (3) для простых дробей, получим
. (18)
Подставляя (18) в (17) и определяя коэффициент при , можно убедиться, что представляется линейной комбинацией функций (19)
общим решением будет .
Найти число двоичных слов длины , в которых никакие две единицы не идут подряд.
Будем называть такие слова правильными и обозначим их число через . Разобьем множество этих правильных слов на два класса: слова, оканчивающиеся на ноль, и слова, оканчивающиеся на единицу. Обозначим количество слов в этих классах и соответственно. По правилу сложения
(5)
Очевидно, что у слова, оканчивающегося на ноль, первые символов образуют правильное слово длины , или другими словами, имеется биекция между множеством правильных слов длины , оканчивающихся на ноль, и множеством правильных слов длины , то есть .
Если правильное слово длины оканчивается на единицу, то предыдущий символ этого слова должен быть нулем, а первые символа должны образовывать правильное слово длины . Как и в предыдущем случае, снова имеем биекцию между множеством правильных слов длины , оканчивающихся на единицу, и множеством правильных слов длины . Следовательно. . Из формулы (5) получаем рекуррентное соотношение .
Пример 2. Задача о расстановке скобок в выражении с неассоциативной бинарной операцией.Пусть “ ” обозначает некоторую бинарную операцию. Рассмотрим выражение , в котором символ обозначает некоторую бинарную неассоциативную операцию. Сколько имеется различных способов расстановки скобок в этом выражении?
Как пример неассоциативной операции можно привести векторное произведение. Другой пример – обычное сложение и умножение, выполняемое на компьютере. В силу того, что представление каждого числа в памяти компьютера ограничено определенным количеством разрядов, при выполнении каждой операции возникает погрешность и суммарный результат этих погрешностей зависит от расстановки скобок. Пусть – машинный ноль. Это означает, что . Тогда , в то время как .
Обозначим число всевозможных способов расстановки скобок через . Тогда
;
.
Назовем операцию условно произведением. Для произвольного разобьем все способы расстановки скобок на классы, включив в -ый класс способы, при которых сначала вычисляется произведение первых и последних операндов с какой-то расстановок скобок, а потом вычисляется их произведение: (7)
где .
По определению количество способов расстановки скобок для вычисления первых операндов равно , последних – . По правилу произведения число расстановок скобок для выражения (4) равно . По правилу сложения , (8)
Например, .
-
Линейные рекуррентные соотношения с постоянными коэффициентами. Пространство решений и его размерность. Определение базисных решений. Формула Бине.
Пусть функция в соотношении (1) является линейной
, , (9)
где – некоторые числа. Такие соотношения называют линейными соотношениями -го порядка с постоянными коэффициентами
Лемма 1. Пусть – решение соотношения (10), а – любое число. Тогда последовательность также является решением этого соотношения.
Лемма 2. Пусть и – решения соотношения (10). Тогда последовательность также является решением этого соотношения.
Из этих двух простых лемм можно сделать следующий важный вывод. Совокупность всевозможных последовательностей с операциями покоординатного сложения и умножения на скаляр образует векторное пространство. Совокупность последовательностей, являющихся решениями соотношения (10), представляет собой подпространство этого пространства. Объемлющее пространство всевозможных последовательностей бесконечномерно, но подпространство решений линейного рекуррентного соотношения имеет конечную размерность, равную порядку уравнения.
Лемма 3. Размерность пространства решений рекуррентного соотношения (10) равна двум.
Из леммы 3 следует, что для определения всех решений уравнения (12) необходимо отыскать два линейно независимых решения. Любое другое решение будет представляться линейной комбинацией этих базисных решений.
Построение базисных решений зависит от корней и характеристического уравнения (14).
-
( ). В этом случае имеем два решения и , которые линейно независимы. Чтобы убедиться в этом, покажем, что из формулы
путем соответствующего выбора констант можно получить любое решение соотношения (10). Рассмотрим произвольное решение . Выберем константы и так, чтобы при и : (16)
Определитель линейной системы (16)
следовательно, система имеет единственное решение, а значит формула (15) – общее решения соотношения (10).
-
. В случае кратных корней характеристическое уравнение (13) имеет вид или . Тогда , , а для соотношения (10) получим уравнение , которое дает два базисных решения и . Общее решение представляется в виде .
Формула Бине. Поставим задачу получить формулу в явном виде для чисел Фибоначчи. Для этого найдем решение рекуррентного соотношения (4) при условии, что . Составим характеристическое уравнение , найдем его корни и получим общее решение . Константы и определим из начальных условий: . Тогда или ,
где – золотое сечение. Формула (21) называется формулой Бине. При этом . Из формулы Бине следует, что .
10. Определение производящей функции. Свойства линейности, дифференцирования, умножения на параметр , интегрирования. Примеры.
Производящей функцией, или обычной производящей функцией, последовательности чисел называется формальный ряд (1)
где – формальная переменная. При этом будем писать .
Свойства производящих функций
-
Линейной комбинации последовательностей взаимно однозначно соответствует линейная комбинация их производящих функций:
-
Дифференцирование производящей функции : .
Например, дифференцируя функцию , получим , то есть производящей функцией последовательности является функция : .
Дифференцируя раз функцию , будем иметь
.
После деления на получим производящую функцию для сочетаний
. (3)
3) Умножение производящей функции на соответствует сдвигу членов последовательности на одну позицию вправо. Если , то .
Например, производящей функцией последовательности (0, 1, 2, …, , …) является функция : .
-
Интегрирование производящей функции :
В качестве примера найдем . Используем формулу бинома Ньютона
. (4)
Числа называют биномиальными коэффициентами. При : . (5)
Из равенства (5) следует, что функция является производящей для последовательности . Можно также написать . (6)
Интегрируя левую часть соотношения (5), получим
.
Для правой части имеем .
При находим .
-
Производящая функция для свертки последовательностей. Формула Вандермонда. Формула бинома Ньютона для вещественного показателя.
Производящая функция для свертки последовательностей. Сверткой последовательностей и называется последовательность , элементы которой вычисляются по правилу: , , , …, , …
Операция свертки является основной в цифровой обработке сигналов: после свертывания последовательности отсчетов сигнала со специально подобранной последовательностью происходит фильтрация – усиление одних частот и подавление других.
Свертка обозначается звездочкой: .
Производящая функция свертки равна произведению производящих функций свертываемых последовательностей: .
Действительно, при перемножении и -ая степень переменной складывается из всевозможных произведений , в которых первый сомножитель из , а второй из
Формула Вандермонда. Пусть , .
По правилу свертки . С другой стороны,
.
Следовательно, .
Формула бинома Ньютона для вещественного показателя. Название формулы (4) биномом Ньютона исторически неверно, так как эту формулу хорошо знали среднеазиатские математики Омар Хайям, Гиясэддин и др. В Западной Европе задолго до Ньютона ее знал Паскаль. Заслуга же Ньютона заключалась в том, что ему удалось обобщить формулу для на случай произвольного вещественного показателя степени , если в качестве биномиальных коэффициентов использовать числа , (7)
причем вместо конечного числа слагаемых мы имеем бесконечный ряд: (8)
Из формулы (8) многие производящие функции получаются как частные случаи. Во-первых, при имеем формулу (4), так как при . Во-вторых, при , и замене на приходим к формуле (3)
-
Определение числа расстановок скобок в выражении с неассоциативной бинарной операцией методом производящих функций.
Определение числа расстановок скобок в выражении с неассоциативной бинарной операцией. Ранее для числа расстановки скобок в неассоциативном произведении была получена формула (10)
Введем для последовательности производящую функцию: .
Заменим коэффициенты их выражениями из рекуррентного соотношения (10). Так как это соотношение имеет место, начиная с , то первый член отделим от суммы:
.
Последовательность представляет собой свертку последовательности с собой. В силу свойства 5) имеем . (12)
Таким образом, можно найти как решение квадратного уравнения (12): (13)
Перед корнем выбран знак минус, так как . Чтобы найти , надо разложить в ряд по степеням правую часть уравнения (13). Для этого используем формулу бинома Ньютона (8) при и : ,
где .
Умножим числитель и знаменатель последней дроби на произведение последовательных четных чисел от 2 до : .
Тогда .
Из формулы (13) получим
.
Таким образом, число расстановок скобок в неассоциативном произведении равно
.
-
Решение линейных рекуррентных соотношений с постоянными коэффициентами методом производящих функций.
Пусть последовательность является решением линейного рекуррентного соотношения , (14)
Для производящей функции (1) этой последовательности обозначим начальные отрезки ряда
Заменим коэффициенты, начиная с -го, по формуле (14)
. (15)
Внутреннюю сумму представим в виде
и подставим в (15):
.
Из этого уравнения найдем производящую функцию : , (16)
где , .
Сравнивая с характеристическим многочленом ,
найдем .
Если имеет корни , ,…, кратности соответственно , ,…, , то
.
Тогда
.
Раскладывая дробь (16) на простые, получим
, (17)
где – константы.
Используя степенные ряды (3) для простых дробей, получим
. (18)
Подставляя (18) в (17) и определяя коэффициент при , можно убедиться, что представляется линейной комбинацией функций (19)