Производящая функция последовательности: различия между версиями
| [отпатрулированная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
Tosha (обсуждение | вклад) Нет описания правки |
Tosha (обсуждение | вклад) |
||
Строка 29:
=== В комбинаторике ===
;Число композиций
Пусть <math>B_m^n</math> — это количество [[Композиция (теория чисел)|композиций]] неотрицательного целого числа ''n'' длины ''m'', то есть, представлений ''n'' в виде <math>n=k_1+k_2+\cdots+k_m</math>, где <math>\{k_i\}</math> — неотрицательные [[Целое число|целые числа]]. Число <math>B_m^n</math> также является [[число сочетаний#Сочетания с повторениями|числом сочетаний с повторениями]] из ''m'' по ''n'', то есть, количество выборок ''n'' возможно повторяющих элементов из множества <math>\{ 1, 2, \dots, m\}</math> (при этом каждый член <math>k_i</math> в композиции можно трактовать как количество элементов ''i'' в выборке).
Строка 35 ⟶ 37 :
Поэтому число <math>B_m^n</math> может быть найдено как коэффициент при <math>x^n</math> в разложении <math>(1-x)^{-m}</math> по степеням ''x''. Для этого можно воспользоваться определением [[биномиальный коэффициент|биномиальных коэффициентов]] или же непосредственно взять ''n'' раз [[Производная функции|производную]] в нуле:
: <math>B_m^n = (-1)^n {-m\choose n} = \frac{m(m+1)\cdots(m+n-1)}{n!} = {m+n-1 \choose n}.</math>
;Чилсо связных графов
Обозначим через <math>a_n</math> число всех графов с вершинами <math>\{1,\dots,n\}</math> и через <math>c_n</math> число всех связанных графов с этими вершинами.
Заметим, что <math>a_n=2^{\binom n 2}</math>.
Рассмотрим экспоненциальные производящие функции этих последовательностей:
:<math>a(x)=a_1\cdot x+\tfrac12\cdot a_2\cdot x^2+\dots+\tfrac1{n!}\cdot a_n\cdot x^n+\dots</math>
:<math>c(x)=c_1\cdot x+\tfrac12\cdot c_2\cdot x^2+\dots+\tfrac1{n!}\cdot c_n\cdot x^n+\dots</math>
Оба ряда расходятся при <math>x\ne 0</math>, тем не менее их можно рассматривать как формальные степенные ряды и для этих рядов выполняется следующее соотношение:
:<math>1+a(x)=e^{c(x)},</math>
из которого следует простое рекуррентное соотношение для <math>c_n</math>, позволяющее быстро найти первые члены этой последовательности<ref>{{книга|автор=Frank Horary, Edgar M. Palmer|заглавие=Graphical enumeration|год=|серия=|ссылка=|место=|издательство=|тираж=|страниц=|isbn=}}</ref>
:<math>1, 1, 4, 38, 728, 26704, 1866256, 251548592, 66296291072, \dots</math>
=== В теории вероятностей ===
| |||