КОМБИНАТО́РНЫЕ ЧИ́СЛА И МНОГОЧЛЕ́НЫ
-
Рубрика: Математика
-
-
Скопировать библиографическую ссылку:
КОМБИНАТО́РНЫЕ ЧИ́СЛА И МНОГОЧЛЕ́НЫ, общее название специальных чисел и многочленов, которые играют важную роль в решении комбинаторных задач. Как правило, комбинаторные числа имеют наглядную комбинаторную интерпретацию (зачастую не единственную), выражаемую в терминах числа способов выбора и расположения элементов некоторого, обычно конечного, множества, приводящих к конфигурациям данного класса или числа объектов из некоторого множества объектов, обладающих тем или иным выделенным свойством.
Простейшими примерами комбинаторных чисел являются числа сочетаний, размещений и перестановок. Если имеется множество из $N$ разл. элементов, то его подмножества называются сочетаниями, число разл. сочетаний размера $k$ равно$$C_N^k=\big(\frac{N}{k}\big)=\frac{N(N-1) \ldots(N-k+1)}{k!}=\frac{N!}{k!(N-k)!}.$$
Числа $\big(\frac{N}{k}\big)$, $k=0,1,...,N$, называют биномиальными коэффициентами, поскольку они входят в формулу Ньютона бинома. Упорядоченные наборы из разл. элементов множества $N$ называются размещениями, число разл. размещений размера $k $ равно $$A_N^k=k!C_N^k=N(N-1)\ldots(N-k+1).$$
В случае $N=k$ размещения называются перестановками, число всех перестановок из $N$ элементов равно $PN=N!,$ где $N!=N(N-1)...2·1$. Сочетания, размещения и перестановки используются в разл. разделах математики.
Если допускаются повторения элементов, то число всех сочетаний размера $k$ из $N$ разл. элементов равно $C_{N-k+1}^k$, а число всех упорядоченных наборов размера $k$ равно $N^k$. Эти числа используют при нахождении вероятностей разл. событий при классич. определении вероятности (см. Вероятностей теория). Напр., если имеется урна с $N$ шарами, занумерованными числами $1,2,...,N$, причём шары с номерами $1,2,...,M$ белого цвета, а остальные – чёрного, то вероятность получить ровно $m$ белых шаров при случайном выборе из урны $n$ шаров равна
$$\frac{C_n^mA_M^mA_{N-M}^{n-m}}{A_N^n}=\frac{C_n^mC_{N-M}^{n-m}}{C_N^n},$$если выбор производится без возвращения шаров, и равна$$\frac{C_n^mM^m(N-M)^{n-m}}{N^n}=C_n^m\bigg(\frac{M}{N}\bigg)^m\bigg(1-\frac{M}{N}\bigg)^{n-m}$$при выборе с возвращением.
Из числа более специальных комбинаторных чисел наиболее часто используются т. н. числа Каталана$$C_n=\frac{1}{n+1}C_{2n}^n;$$числа Моргана$$$$$$\Delta_k^n=\Delta^nx^k\big|_{x=0}=\sum_{j=0}^n(-1)^jC_k^j(k-j)^n,$$где $Δ$ – оператор разности $Δf(x)=f(x+1)-f(x)$; числа Стирлинга $S(n,k)$ и $σ(n,k)$ соответственно 1-го и 2-го рода; числа Белла$$B_n=\sum_{k=0}^nS(n,k).$$
Все эти числа, как правило, имеют наглядные комбинаторные интерпретации. Так, напр., число Каталана $C_n$ равно числу векторов $(\varepsilon_1,...,\varepsilon_{2n}), \varepsilon_i=±1, i=1,...,2_n$, таких, что $\sum_{i=1}^k \varepsilon_i\geq0,$ $k=1,...,$ $2n-1$, $\sum_{i=1}^{2n}\varepsilon_i=0$; число Моргана $\Delta_k^n$ равно числу отображений $f$ множества $A$ из $k$ элементов на множество $B$ из $n$ элементов, т. е. таких отображений, что $f(A)=f(B);$ число Белла $B_n$ есть число разл. разбиений множества из $n $ элементов на непересекающиеся подмножества.
При исследовании свойств комбинаторных чисел широко используют производящие функции, рекуррентные соотношения и конечно-разностные уравнения. Во многих случаях на рассматриваемом множестве объектов удаётся построить подходящую вероятностную модель и тем самым комбинаторную задачу перечислительного характера сформулировать как задачу изучения распределения вероятностей соответствующей случайной величины. Такая интерпретация даёт возможность применять при изучении комбинаторных чисел разл. методы теории вероятностей.
Под комбинаторными многочленами понимают производящие функции комбинаторных чисел или производящие функции этих чисел с некоторыми весами. Напр., производящей функцией чисел сочетаний $C_N^k$, $k=0,1,...,N,$ является бином Ньютона$$\sum_{k=0}^NC_N^kx^k=(1+x)^N;$$для чисел Стирлинга$$\sum_{k=0}^nS(n,k)x^k=x(x-1)\ldots(x-n+1),\\ \sum_{k=0}^n \sigma(n,k)x_k=x^n,$$где $(x)_k=x(x-1)\ldots(x-k+1), k=0,1, \ldots, n.$