Редактирование: Произведение Адамара рациональных производящих функций

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 +
===Лемма о квазимногочленах ===
 
Одно из наиболее привлекательных свойств рациональных [[Производящая функция|производящих функций]] {{---}} их замкнутость относительно произведения Адамара.
 
Одно из наиболее привлекательных свойств рациональных [[Производящая функция|производящих функций]] {{---}} их замкнутость относительно произведения Адамара.
 
{{Определение
 
{{Определение
Строка 4: Строка 5:
 
}}
 
}}
 
Таким образом, произведение Адамара двух последовательностей {{---}} это последовательность, состоящая из почленных произведений соответственных членов этих последовательностей. Необходимость в производящей функции для произведения Адамара уже встречалась: в [[Задача о счастливых билетах|задаче о числе счастливых билетов]] нам понадобилось вычислить сумму квадратов коэффициентов производящего многочлена <tex>A_3</tex>. Эта необходимость возникает при перечислении пар объектов одинакового порядка: если число объектов первого типа равно <tex>a_n</tex>, а число объектов второго типа <tex>b_n</tex> то число пар объектов, составленных из элементов первого и второго типа, равно <tex>a_n b_n</tex>.
 
Таким образом, произведение Адамара двух последовательностей {{---}} это последовательность, состоящая из почленных произведений соответственных членов этих последовательностей. Необходимость в производящей функции для произведения Адамара уже встречалась: в [[Задача о счастливых билетах|задаче о числе счастливых билетов]] нам понадобилось вычислить сумму квадратов коэффициентов производящего многочлена <tex>A_3</tex>. Эта необходимость возникает при перечислении пар объектов одинакового порядка: если число объектов первого типа равно <tex>a_n</tex>, а число объектов второго типа <tex>b_n</tex> то число пар объектов, составленных из элементов первого и второго типа, равно <tex>a_n b_n</tex>.
 
==Рациональность произведения Адамара==
 
  
 
{{Лемма
 
{{Лемма
Строка 12: Строка 11:
 
  \dots, p_l(n)</tex>, что начиная с некоторого номера <tex>n</tex>  
 
  \dots, p_l(n)</tex>, что начиная с некоторого номера <tex>n</tex>  
 
<tex>a_n = p_1(n) q_1^n + \dots + p_l(n) q_l^n.</tex>
 
<tex>a_n = p_1(n) q_1^n + \dots + p_l(n) q_l^n.</tex>
Выражение в правой части равенства называется '''квазимногочленом''' (англ. ''quasypolynomial'') от переменной <tex>n</tex>.
+
Выражение в правой части равенства называется квазимногочленом от переменной <tex>n</tex>.
 
|proof=
 
|proof=
  
Строка 19: Строка 18:
 
Заметим прежде всего, что производящая функция <tex>(1 - q s)^{-k}</tex> имеет вид
 
Заметим прежде всего, что производящая функция <tex>(1 - q s)^{-k}</tex> имеет вид
  
<tex>(1 - q s)^{-k} = 1 - \begin{pmatrix} -k \\ 1 \end{pmatrix} q s + \begin{pmatrix} -k \\ 2 \end{pmatrix} q^{2} s^{2} - \begin{pmatrix} -k \\ 3 \end{pmatrix} q^{3} s^{3} + \dots = </tex>
+
<tex>(1 - q s)^{-k} = 1 - {-k \choose 1} q s + {-k \choose 2} q^{2} s^{2} - {-k\choose 3} q^{3} s^{3} + \dots = </tex>
:::<tex> = 1+ \begin{pmatrix} k \\ 1 \end{pmatrix} q s + \begin{pmatrix} k+1 \\ 2 \end{pmatrix} q^{2} s^{2} + \begin{pmatrix} k+2 \\ 3 \end{pmatrix} q^{3} s^{3} + \dots =</tex>
+
:::<tex> = 1+ {k \choose 1} q s + {k + 1 \choose 2} q^{2} s^{2} + {k + 2 \choose 3} q^{3} s^{3} + \dots =</tex>
:::<tex> = 1 + \begin{pmatrix} k \\ k-1 \end{pmatrix} q s + \begin{pmatrix} k+1 \\ k-1 \end{pmatrix} q^{2} s^{2} + \begin{pmatrix} k+2 \\ k-1 \end{pmatrix}q^{3} s^{3} + \dots</tex>
+
:::<tex> = 1 + {k \choose k - 1} q s + {k + 1 \choose k - 1} q^{2} s^{2} + {k + 2 \choose k - 1} q^{3} s^{3} + \dots</tex>
  
 
Коэффициент при <tex>s^n</tex> в этой производящей функции равен
 
Коэффициент при <tex>s^n</tex> в этой производящей функции равен
Строка 33: Строка 32:
 
Наоборот, предположим, что коэффициенты производящей функции, начиная с некоторого номера, представляются в виде квазимногочлена. Покажем, что в случае квазимногочлена <tex>p(n) q^{n}</tex> соответствующая производящая функция рациональна. Пусть степень многочлена <tex>p</tex> равна <tex>k - 1</tex>. Многочлены <tex>P_0, P_1, \dots, P_{k - 1}</tex>, определенные равенством <tex>\dfrac{(n + 1)(n + 2)\dots(n + k - 1)}{(k - 1)!} q^{n} = P_{k - 1}(n) q^{n}</tex>, образуют базис в пространстве многочленов степени не выше <tex> k - 1</tex>. Действительно, любая последовательность многочленов степеней <tex>0, 1, \dots, k - 1</tex> образует базис в этом пространстве. Поэтому многочлен <tex>p</tex> представляется в виде линейной комбинации многочленов <tex>P_i</tex> и соответствующая производящая функция есть просто линейная комбинация функций <tex>(1 - q s)^{-j}</tex>, <tex>j = 0, 1, \dots, k - 1</tex>.
 
Наоборот, предположим, что коэффициенты производящей функции, начиная с некоторого номера, представляются в виде квазимногочлена. Покажем, что в случае квазимногочлена <tex>p(n) q^{n}</tex> соответствующая производящая функция рациональна. Пусть степень многочлена <tex>p</tex> равна <tex>k - 1</tex>. Многочлены <tex>P_0, P_1, \dots, P_{k - 1}</tex>, определенные равенством <tex>\dfrac{(n + 1)(n + 2)\dots(n + k - 1)}{(k - 1)!} q^{n} = P_{k - 1}(n) q^{n}</tex>, образуют базис в пространстве многочленов степени не выше <tex> k - 1</tex>. Действительно, любая последовательность многочленов степеней <tex>0, 1, \dots, k - 1</tex> образует базис в этом пространстве. Поэтому многочлен <tex>p</tex> представляется в виде линейной комбинации многочленов <tex>P_i</tex> и соответствующая производящая функция есть просто линейная комбинация функций <tex>(1 - q s)^{-j}</tex>, <tex>j = 0, 1, \dots, k - 1</tex>.
 
Для произвольного квазимногочлена мы получаем линейную комбинацию функций такого вида при разных <tex>q_i</tex>.}}
 
Для произвольного квазимногочлена мы получаем линейную комбинацию функций такого вида при разных <tex>q_i</tex>.}}
 +
 +
===Теорема о рациональности произведения Адамара===
  
 
{{Теорема
 
{{Теорема
Строка 45: Строка 46:
 
является тоже рациональной. Проще говоря, произведение Адамара двух рациональных производящих функций рационально.
 
является тоже рациональной. Проще говоря, произведение Адамара двух рациональных производящих функций рационально.
  
|proof= Для доказательства теоремы осталось заметить, что произведение квазимногочленов является квазимногочленом. Это утверждение непосредственно вытекает из формулы <tex>a_n = p_1(n) q_1^n + \dots + p_l(n) q_l^n</tex>.}}
+
|proof= Для доказательства теоремы осталось заменить, что произведение квазимногочленов является квазимногочленом. Это утверждение непосредственно вытекает из формулы <tex>a_n = p_1(n) q_1^n + \dots + p_l(n) q_l^n.</tex>}}
  
 
== См. также ==
 
== См. также ==

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)