ЭСБЕ/Комбинаторный анализ

Комбинаторный анализ — математическая теория, занимающаяся определением числа различных способов распределения данных предметов в известном порядке; имеет особенно важное значение в теории уравнений и в теории вероятностей. Простейшие задачи этого рода заключаются в определении числа: размещений, сочетаний и перестановок. Размещениями m предметов по n называются группы, которые можно составить из m предметов таким образом, чтобы каждая группа заключала в себе n предметов и все такие группы отличались бы одна от другой — или предметами в них входящими, или порядком распределения предметов. Число всех возможных размещений, какие можно составить из m предметов по n обозначается символом $A_m^n$ и доказывается, что $A_m^n=m(m-1)(m-2)(m-3)\dots (m-n+1).$ Сочетаниями из m предметов по n называются группы, которые можно составить из m предметов таким образом, чтобы каждая группа заключала в себе n предметов и все такие группы отличались бы одна от другой предметами в них входящими. Число сочетаний из m по n обозначается символом $C_m^n$ и доказывается, что $C_m^n=\frac{m(m-1)(m)\dots (m-n+1)}{1\cdot 2\cdot 3\dots n}.$ Перестановками из n предметов называются группы, которые можно составить из n предметов таким образом, чтобы все n предметов входили в каждую группу и одна группа от другой отличалась бы порядком распределения предметов. Число всех возможных перестановок из n предметов обозначается символом $P_n$ и доказывается, что $P_n=1\cdot 2\cdot 3\cdot 4\dots n.$ Вычисление чисел $A_m^n$, $C_m^n$, и $P_n$ при больших m и n обыкновенным способом по приведенным формулам весьма затруднительно. В таких случаях удобнее пользоваться формулой Гудермана:

$\log 1\cdot 2\cdot 3\dots n=\frac{1}{2}\log 2\pi -n+(n+\frac{1}{2})\log n+\sum _{m=0}^{m=\mathrm{\infty }}[(n+m+\frac{1}{2})\log (1+\frac{1}{m+n})-1].$

В К. анализе употребляются три метода: прямой, способ производящих функций Лапласа и формулы теории конечных разностей.