Производящие функции

Содержание:

  1. Производящие функции
  2. Сочетания

Производящие функции

Производящие функции

Производящие функции

Производящие функции

 

По этой ссылке вы найдёте полный курс лекций по математике:

Решение задач по математике

 

Производящей функцией для последовательности называется формальный степенной ряд , Термин «формальный» означает, что мы не находим область сходимости ряда нигде не будем вычислять значений А(х) для конкретных значений переменной х, будем лишь выполнять некоторые операции над такими рядами и определять коэффициенты при степенях х; таким образом, А(х) интересует нас не как числовая функция от переменной х, а как «носитель» последовательности .

Производящие функции

Суммой произвольных рядов называется ряд Производящие функции Произведением ряда -А(х) на число А называется ряд )Этот факт можно было предвидеть сразу, исходя из общих алгебраических соотношений: матрицы являются матрицами перехода от одного базиса к другому и обратно. Произведением рядов А(х) и В(х) называется ряд Если в последовательности (а*) лишь конечное числочленовотлично от нуля, то ряд А(х) можно рассматривать как многочлен.

Если и в последовательности (Ьк) все члены, начиная с некоторого, равны нулю, то ряд В(х) — также многочлен, и формула (4) переходит в обычную формулу умножения многочленов. Из курса математического анализа известно, что если степенной ряд сходится в некоторой окрестности нуля, то в этой окрестности его сумма является функцией, по отношению к которой сам ряд является рядом Маююрена:

Производящие функции для любого Заметим, что если А(х) и В(х) — аналитические функции в окрестности нуля, то соотношения (2), (3), (4) будут справедливы для них и как для числовых функций. Со>фаняюшее операции сложения и умножения взаимно однозначное соответствие между функциями, аналитическими в окрестности нуля, и их рядами Маклорена, позволяет отождествить формальный ряд (1) с определяемой им аналитической функцией. В табл. 5 представлены производящие функции для некоторых простых последовательностей.

Покажем, например, как может быть получена производящая функция для последовательности неотрицательных целых чисел: последовательность (а*) производящая функция А(х).

Применим аппарат производящих функций к решению следующей весьма общей по постановке задачи. . Найти а* — число всех неупорядоченных к-элементных выборок с повторениями, удовлетворяющих заданным ограничениям на число вхождений в них каждого элемента генеральной совокупности , элемент я, может присутствовать в выборке у, раз у где У{ — элемент некоторого числового множества Проиллюстрируем постановку задачи на нескольких «игрушечных» примерах.

 

Возможно вам будут полезны данные страницы:

Положение плоскости относительно плоскостей проекций
Элементарные функции
Построение взаимно параллельных плоскостей
Равномерная непрерывность. Условие Липшица

 

1) Сколько разных наборов из к шаров можно получить, имея I синий шар, 2 одинаковых белых шара и А одинаковых красных шара? Здесь генеральная совокупность состоит из синего, белого и красного шара. Возможное число вхождений каждого шара в набор определяется множествами 2) В условии предыдущей задачи вводится дополнительное ограничение: чисю красных шаров в наборе должно быть нечетно.

Изменение коснется множества, определяющего допустимое число вхождений красного шара: Х$ = {1,3}. Пусть А(х) — производящая функция для последовательности (а*). Тогда справедливо следующее соотношение: Производящие функции Действительно, если «раскрыть скобки» в правой части (5), то получим: где в* = в выражении для ак суммирование производится по всем наборам таким, что в результате чего получится искомое число fc-выборок.

Возвращаясь к примеру 1), запишем

для него производящую функцию: Производящие функции Коэффициент при хк есть число А:-элементных наборов. Таким образом, можно составить 3 одноэлементных набора, 5 — двухэлементных, 6 — трехэлементньж и т.д. Во втором примере Теперь одноэлементный набор может быть только один, существует 2 набора из двух элементов и т.д. В заключение рассмотрим применение аппарата производящих функций к выводу формул для числа сочетаний (без повторений и с повторениями).

Сочетания

В обоих случаях будем считать, что генеральная совокупность состоит из п элементов. Сочетания. Каждый элемент в выборке встречается не более одного раза, к-выборка при этом является сочетанием (без повторений) из п по к. Производящая функция имеет вид: Сочетания с повторениями. Каждый элемен¥ в выборке может появиться любое число par. Vi Л", = No, fc-выборка при этом суть сочетание с повторениями из п по к. Производящая функция имеет вид: [ биномиальный ряд ) к=0 к~0 Таким образом, вновь получена формула для числа сочетаний с повторениями: В следующих парафафах данной главы аппарат производящих функций будет применен к решению ряда комбинаторных задач.