Меню Главная Случайная статья Настройки Биномиальный коэффициент Материал из https://ru.wikipedia.org Биномиальный коэффициент — коэффициент перед членом разложения бинома Ньютона ${\displaystyle (1+x)^{n}}$ по степеням ${\displaystyle x}$. Коэффициент при ${\displaystyle x^{k}}$ обозначается ${\displaystyle \textstyle {\binom {n}{k}}}$ или ${\displaystyle \textstyle C_{n}^{k}}$ и читается «биномиальный коэффициент из ${\displaystyle n}$ по ${\displaystyle k}$» (или «число сочетаний из ${\displaystyle n}$ по ${\displaystyle k}$»): ${\displaystyle (1+x)^{n}={\binom {n}{0}}+{\binom {n}{1}}x+{\binom {n}{2}}x^{2}+\ldots +{\binom {n}{n}}x^{n}=\sum _{k=0}^{n}{\binom {n}{k}}x^{k}}$ для натуральных степеней ${\displaystyle n}$. Биномиальные коэффициенты могут быть также определены для произвольных действительных показателей ${\displaystyle n}$. В случае произвольного действительного числа ${\displaystyle n}$ биномиальные коэффициенты определяются как коэффициенты разложения выражения ${\displaystyle (1+x)^{n}}$ в бесконечный степенной ряд: ${\displaystyle (1+x)^{n}=\sum _{k=0}^{\infty }{\binom {n}{k}}x^{k}}$, где в случае неотрицательных целых ${\displaystyle n}$ все коэффициенты ${\displaystyle \textstyle {\binom {n}{k}}}$ при ${\displaystyle k>n}$ обращаются в нуль и поэтому данное разложение является конечной суммой. В комбинаторике биномиальный коэффициент ${\displaystyle \textstyle {\binom {n}{k}}}$ для неотрицательных целых чисел ${\displaystyle n}$ и ${\displaystyle k}$ интерпретируется как количество сочетаний из ${\displaystyle n}$ по ${\displaystyle k}$, то есть как количество всех (нестрогих) подмножеств (выборок) размера ${\displaystyle k}$ в ${\displaystyle n}$-элементном множестве. Биномиальные коэффициенты часто возникают в задачах комбинаторики и теории вероятностей. Обобщением биномиальных коэффициентов являются мультиномиальные коэффициенты. Содержание 1 Явные формулы 2 Треугольник Паскаля 3 Свойства 3.1 Производящие функции 3.2 Делимость 3.3 Основные тождества 3.4 Бином Ньютона и следствия 3.5 Свёртка Вандермонда и следствия 3.6 Другие тождества 3.7 Матричные соотношения 3.8 Асимптотика и оценки 3.9 Целозначные полиномы 4 Алгоритмы вычисления 5 Примечания 6 Литература Явные формулы Вычисляя коэффициенты в разложении ${\displaystyle (1+x)^{n}}$ в степенной ряд, можно получить явные формулы для биномиальных коэффициентов ${\displaystyle \textstyle {\binom {n}{k}}}$. Для всех действительных чисел ${\displaystyle n}$ и целых чисел ${\displaystyle k}$: ${\displaystyle {\binom {n}{k}}={\begin{cases}{\frac {n(n-1)(n-2)\cdot \ldots \cdot (n-k+1)}{k!}},&k\geqslant 0\\0,&k<0\end{cases}}}$, где ${\displaystyle k!}$ обозначает факториал числа ${\displaystyle k}$. Для неотрицательных целых ${\displaystyle n}$ и ${\displaystyle k}$ также справедливы формулы: ${\displaystyle {\binom {n}{k}}={\begin{cases}{\frac {n!}{k!(n-k)!}},&0\leqslant k\leqslant n\\0,&k>n\end{cases}}}$. Для целых отрицательных показателей коэффициенты разложения бинома ${\displaystyle (1+x)^{-n}}$ равны: ${\displaystyle {\binom {-n}{k}}={\begin{cases}(-1)^{k}\cdot {\frac {(n+k-1)!}{k!(n-1)!}},&k\geqslant 0\\0,&k<0\end{cases}}}$. Треугольник Паскаля Тождество: ${\displaystyle {n \choose k}={n-1 \choose k-1}+{n-1 \choose k}}$ позволяет расположить биномиальные коэффициенты для неотрицательных целых чисел ${\displaystyle n}$, ${\displaystyle k}$ в виде треугольника Паскаля, в котором каждое число равно сумме двух вышестоящих: ${\displaystyle {\begin{matrix}n=0:&&&&&1&&&&\\n=1:&&&&1&&1&&&\\n=2:&&&1&&2&&1&&\\n=3:&&1&&3&&3&&1&\\n=4:&1&&4&&6&&4&&1\\\vdots &&\vdots &&\vdots &&\vdots &&\vdots &\end{matrix}}}$. Треугольная таблица, предложенная Паскалем в «Трактате об арифметическом треугольнике» (1654), отличается от той, что выписана здесь, поворотом на 45°. Таблицы для изображения биномиальных коэффициентов были известны и ранее (Тарталье, Омару Хайяму, аль-Караджи, Яну Хуэю). Если в каждой строке треугольника Паскаля все числа разделить на ${\displaystyle 2^{n}}$ (это сумма всех чисел в строке), то все строки при стремлении ${\displaystyle n}$ к бесконечности примут вид функции нормального распределения. Свойства Производящие функции Для фиксированного значения ${\displaystyle n}$ производящей функцией последовательности биномиальных коэффициентов ${\displaystyle {\tbinom {n}{0}},\;{\tbinom {n}{1}},\;{\tbinom {n}{2}},\dots }$ является: ${\displaystyle \sum _{k=0}^{\infty }{\binom {n}{k}}x^{k}=(1+x)^{n}}$. Для фиксированного значения ${\displaystyle k}$ производящая функция последовательности коэффициентов ${\displaystyle {\tbinom {0}{k}},\;{\tbinom {1}{k}},\;{\tbinom {2}{k}},\dots }$ равна: ${\displaystyle \sum _{n}{\binom {n}{k}}y^{n}={\frac {y^{k}}{(1-y)^{k+1}}}}$. Двумерной производящей функцией биномиальных коэффициентов ${\displaystyle {\tbinom {n}{k}}}$ для целых ${\displaystyle n,k}$ является: ${\displaystyle \sum _{n,k}{\binom {n}{k}}x^{k}y^{n}={\frac {1}{1-y-xy}}}$, или ${\displaystyle \sum _{n=0}^{\infty }\sum _{k=0}^{n}{\binom {n}{k}}x^{k}y^{n}={\frac {1}{1-y-xy}}}$. Делимость Из теоремы Люка следует, что: коэффициент ${\displaystyle \textstyle {\binom {n}{k}}}$ нечётен ${\displaystyle \iff }$ в двоичной записи числа ${\displaystyle k}$ единицы не стоят в тех разрядах, где в числе ${\displaystyle n}$ стоят нули; коэффициент ${\displaystyle \textstyle {\binom {n}{k}}}$ некратен простому числу ${\displaystyle p}$ ${\displaystyle \iff }$ в ${\displaystyle p}$-ичной записи числа ${\displaystyle k}$ все разряды не превосходят соответствующих разрядов числа ${\displaystyle n}$; в последовательности биномиальных коэффициентов ${\displaystyle \textstyle {\binom {n}{0}},\;{\binom {n}{1}},\;\ldots ,\;{\binom {n}{n}}}$: все числа не кратны заданному простому ${\displaystyle p}$ ${\displaystyle \iff }$ число ${\displaystyle n}$ представимо в виде ${\displaystyle mp^{k}-1}$, где натуральное число ${\displaystyle m<p}$; все числа, кроме первого и последнего, кратны заданному простому ${\displaystyle p}$ ${\displaystyle \iff }$ ${\displaystyle n=p^{k}}$; количество нечётных чисел равно степени двойки, показатель которой равен количеству единиц в двоичной записи числа ${\displaystyle n}$; чётных и нечётных чисел не может быть поровну; количество чисел, не кратных простому ${\displaystyle p}$, равно ${\displaystyle (a_{1}+1)\cdots (a_{m}+1)}$, где числа ${\displaystyle a_{1},\;\ldots ,a_{m}}$ — разряды ${\displaystyle p}$-ичной записи числа ${\displaystyle n}$; а число ${\displaystyle \textstyle m=\lfloor \log _{p}{n}\rfloor +1}$, где ${\displaystyle \lfloor \cdot \rfloor }$ — функция «пол», — это длина данной записи. Основные тождества ${\displaystyle {n \choose k}={n-1 \choose k-1}+{n-1 \choose k}}$. ${\displaystyle {\binom {n}{k}}=(-1)^{k}{\binom {-n+k-1}{k}}}$. ${\displaystyle {n \choose k}={n \choose n-k}}$ (правило симметрии). ${\displaystyle {n \choose k}={\frac {n}{k}}{n-1 \choose k-1}}$ (вынесение за скобки). ${\displaystyle {n \choose {\color {Green}m}}{{\color {Green}m} \choose n-{\color {Green}k}}={n \choose {\color {Green}k}}{{\color {Green}k} \choose n-{\color {Green}m}}}$ (замена индексов). ${\displaystyle (n-k){n \choose k}=n{n-1 \choose k}}$. Бином Ньютона и следствия ${\displaystyle {n \choose 0}+{n \choose 1}+\ldots +{n \choose n}=2^{n}}$, где ${\displaystyle n\in \mathbb {N} }$. ${\displaystyle \sum _{i+j=m}{\binom {n}{j}}{\binom {n}{i}}(-1)^{j}={\begin{cases}{\binom {n}{m/2}}(-1)^{m/2},&{\text{если}}\ m\equiv 0{\pmod {2}},\\0,&{\text{если}}\ m\equiv 1{\pmod {2}}.\end{cases}}}$ ${\displaystyle \sum _{j=k}^{n}{\binom {n}{j}}(-1)^{j}=(-1)^{k}{\binom {n-1}{k-1}}}$. ${\displaystyle {n \choose 0}-{n \choose 1}+\ldots +(-1)^{n}{n \choose n}=0}$, где ${\displaystyle n\in \mathbb {N} }$. Более сильное тождество: ${\displaystyle {n \choose 0}+{n \choose 2}+\ldots +{n \choose 2\lfloor n/2\rfloor }=2^{n-1}}$, где ${\displaystyle n\in \mathbb {N} }$. ${\displaystyle \sum _{k=-a}^{a}(-1)^{k}{2a \choose k+a}^{3}={\frac {(3a)!}{(a!)^{3}}}}$, а более общем виде ${\displaystyle \sum _{k=-a}^{a}(-1)^{k}{a+b \choose a+k}{b+c \choose b+k}{c+a \choose c+k}={\frac {(a+b+c)!}{a!\,b!\,c!}}}$. Свёртка Вандермонда и следствия