31.12.2022 04:36
OBIEESupport 2 2300 Источник

Комбинаторная и вычислительная математика в силу решения на компьютерах последних поколений задач с большой точностью должны идти вместе.

Автор, однако, преподавая комбинаторную теорию сталкивался с тем, что общая красота как вычислительной математики, так и комбинаторики не находит себе место в одном каком-либо учебнике.

От монографий по вычислительным методам веет фундаментальностью и доказуемостью результатов, а от учебников типа Гаврилов Г.П., Сапоженко А.А. - Задачи и упражнения по дискретной математике - веет как раз формулами, доказательство которых хоть и просто, но, чаще всего, не рассматривается вообще.

Теорема о количестве сюръективных отображений между конечными непустыми множествами.

Пусть X,Y - конечные непустые множества. Обозначим через surY^X- множество сюръективных отображений, а через |X|,|Y|,|surY^X|- количество элементов в соответствующих множествах. Тогда имеет место отношение:

|surY^X|=|Y|^{|X|}-C_{|Y|}^{1}(|Y|-1)^{|X|}+C_{|Y|}^{2}(|Y|-2)^{|X|}-\dots+\\(-1)^{|Y|-2}C_{|Y|}^{|Y|-2}2^{|X|}+(-1)^{|Y|-1}C_{|Y|}^{|Y|-1}

Если |X|=|Y|\ и \ surY^X \ совпадает\ со\ множеством\ всех\ биекций\ BiY^X,\\ | BiY^X|=|X|!=|Y|!,\ то\ получаем\ выражение\ для\ n!

Рассмотрим формулу:

n!=n^n-C_n^1(n-1)^n+C_n^2(n-2)^n-C_n^3(n-3)^n+...+(-1)^{(n-1)}C{_n}^{(n-1)} (*)

Если рассмотреть формулу Стирлинга в виде ряда:

n! = \sqrt{2\pi n}(\frac{n}{e})^n(1+\frac{1}{12 n}+\frac{1}{288n^2}-\frac{139}{51840 n^3}+...)

Введем следующие обозначения:

-\delta(n)=n!-n^n

Получаем формулу:

n! \approx \delta(n)[\frac{\sqrt{2\pi n}(1+\frac{1}{12 n}+\frac{1}{288n^2}-\frac{139}{51840 n^3}+...)}{e^n-\sqrt{2\pi n}(1+\frac{1}{12 n}+\frac{1}{288n^2}-\frac{139}{51840 n^3}+...)}] (**)

Посчитаем формулу (**), допустим для n=20.

20!-20^{20}=-10485759756709799182336000020! \approx 2.4329028230918*10^{18}

При этом точное значение: 20!=2432902008176640000

Формула вида (**) показывает отношение между рядом Стирлинга и рядом из n слагаемых из правой части формулы (*).

Если же учесть, что

n!=(\frac{n}{e})^n \sqrt{2 \pi n}\sum_{k=0}^{\infty}\frac{a_k}{n^k}a_k=\sum_{j=1}^{2k}(-1)^j\frac{d_3(2k+2j,j)}{2^{j+k}(j+k)!},k \in N, (***)

где d_3(n,m)- количество перестановок из n элементов с m циклами, каждый из которых имеет длину не менее 3.

Comtet L. Advanced Combinatorics: The Art of Finite and Infinite Expansions. - D. Reidel Publishing Company, 1974. - 267 p.

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

Комментарии (2)


  1. Naf2000
    31.12.2022 09:09
    #25065164
    +2

    Это просто замечательный факт или имеет применение? На первый взгляд считать факториал "в лоб" эффективнее.


    1. OBIEESupport Автор
      31.12.2022 22:29
      #25066442

      Если откинуть все подробности вычислений по приведенным формулам, то статья посвящена именно сравнению очень хорошего приближения Стирлинга и точных вычислений на основании комбинаторной теории. И еще, выписан потрясающий ряд, который для больших n показывает, насколько точными могут быть вычисления на основании серьезного математического анализа. Если у вас есть нужные биномиальные коэффициенты и "под рукой" есть степени чисел, меньших n - можно это все скомбинировать для точности. Если же означенной информации нет - то (n/e)^n нужно множить на ряд Стирлинга и постоянную.