Бином коэффициенчĕсем

Биномла коэффициент — Ньютонăн $(1+x)^{n}$ биномне x капашĕсем майăн сарса тухнин (сарăмăн) коффициенчĕсене çапла калаççĕ. Çапла вара, $x^{k}$ çумĕнчи коэффициента $\textstyle {\binom {n}{k}}$ е $\textstyle C_{n}^{k}$ пек çыраççĕ те вăл çапла вуланать: « n -ран k майĕн биномла коэффициент» (е «n-ран k тĕлĕшпе пайлашусен хисепĕ», $\textstyle C_{n}^{k}$ вара «n-ран п k майĕн C»):

(1+x)^{n}={n \choose 0}x^{0}+{n \choose 1}x+{n \choose 2}x^{2}+\cdots +{n \choose n}x^{n}=\sum _{k=0}^{n}{n \choose k}x^{k},

мĕнпур натураллă $n$ капашсемшĕн.

Биномла коэффициентсене çавăн пекех хуть те мĕнле чăн $n$ хисепсемшĕн те палăртма пулать. Кирек епле чăн $n$ хисепшĕн биномла коэффициента $(1+x)^{n}$ сăнарлăха вĕçсĕр Тейлор речĕ пек сарнин коэффициенчĕсем пек палăртаççĕ:

(1+x)^{n}=\sum _{k=0}^{\infty }{\binom {n}{k}}x^{k},

кунта минуслă мар тата тулли n-семшĕн $k>n$ чухне мĕнпур $\textstyle {\binom {n}{k}}$ коэффициентсем нуле куçаççĕ те çавна кура унашкал сарăм вĕçлĕ сумма пек пулать (çÿлерех пăхăр).

Комбинаторикăра биномла $\textstyle {\binom {n}{k}}$ коэффициент минуслă мар тулли n тата k хисепсемшĕн n-ран k майăн майлашусен шутлавлăхĕ пек интерпретациленет.

Биномла коэффициентсем час-часах комбинаторика тĕллевчĕкĕсенче тата пулаяслăхсен теорийĕнче сиксе тухаççĕ. Тата биномла коэффициентсене анлăлатсан мультиномиаллĕ коэффициентсем патне пырса тухаççĕ.

Биномлă коэффициентсене шутласа тупмалли уçă хормулăсем:

{n \choose k}={\frac {n!}{k!\;(n-k)!}}={\frac {n(n-1)(n-2)\cdot \dots \cdot (n-k+1)}{k!}}

çакшăн

0\leq k\leq n

;

{n \choose k}=0

для

k<0

или

0\leq n<k

;

{n \choose k}=(-1)^{k}{-n+k-1 \choose k}

для

n<0\leq k

,

ăçта $n!$ и $k!$ — $n$ тата $k$ хисепсен факториалĕсем. ${n \choose k}$ биномлă коэффициенчĕ $C_{n}^{k}$ майлашу хисепĕн пĕтĕмлетĕвĕ пулать, ăна çуклă мар $n$ , $k$ тулли хисепсемшĕн кăна палăртнă. Биномлă коэффициентсем часах комбинаторика ĕç хушăвĕсенче тата пуласлăх теорийĕсенче кирлĕ пулаççĕ. Биномлă коэффициентсен пĕтĕмлетĕвĕсем мультиномлă коэффициентсем шутланаççĕ.

Биномлă коэффициентсене шутласа тупмалли алгоритăмсем

Биномлă коэффициентсене ${n \choose k}={n-1 \choose k}+{n-1 \choose k-1}$ хормулăпа тупма пулать, эхер те кашни утăмрах ${n \choose k}$ паллисене $k=0,1,\dots ,n$ чух сыхласа пырсан. Çак алгоритм уйрăмах çивĕч ĕçлĕ пулать, эхер хытарнă $n$ чух ${n \choose k}$ пĕтĕм паллисене тупас тесен. Алгоритм ыйтнипе $O(n)$ астăвăн ( $O(n^{2})$ биномлă коэффициентсен пĕтĕм таблицине шутласа илнĕ чух) тата вăхăтăн $O(n^{2})$ (кашни хисеп астăвăн пĕр виçине йышăнать тата хисепсен операцисем вăхăтăн пĕр виçинче пулса иртеççĕ тесе ăнкартса хурсан).

Иккĕмĕш меслечĕ ${n \choose k}={\frac {n}{n-k}}{n-1 \choose k}$ танлăхĕпе çыхăннă. Вăл çирĕплетнĕ $k$ чух ${n \choose k}$ шутлама пулăшать.

Пахалăвĕсем

Кăсăклă, биномлă коэффициенчĕсен тытăнса тăракан Паскаль виçкĕтеслĕхĕн ĕречĕсене пăхсан, чикĕ вĕçенче (в пределе) нормăллă уйăрланин функцине - Гаусăн уйăрланине — тупса илетпĕр.

Паскалĕн виçкĕтеслĕхĕ

{n \choose k}={n-1 \choose k-1}+{n-1 \choose k}

Çак танлăх

{n \choose k}={n-1 \choose k-1}+{n-1 \choose k}

биномлă коэффициентсене çуклă мар $n$ , $k$ Паскалĕн виçкĕтеслĕхĕ евĕр майлаштарса хума çамăл парать, çакăнта кашни хисеп çӳлте тăракан икĕ хисепĕн суммипе тан пулать:

{\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° пăранăçпа уйрăлса тăрать.

Биномлă коэффициентсене палăртмалли таблицăсене унчченех пĕлнĕ (Николо Тарталье, Омар Хайям тата ыттисем те).

Пахалăхĕсем

Танлăхсем

${n \choose k}={n-1 \choose k-1}+{n-1 \choose k}$
${n \choose k}={n \choose n-k}$ (симметри йĕрки (правили)
${n \choose 0}+{n \choose 1}+\cdots +{n \choose n}=2^{n}$
${n \choose 0}+{n \choose 2}+\cdots +{n \choose 2\lfloor n/2\rfloor }=2^{n-1}$
${n \choose 0}^{2}+{n \choose 1}^{2}+\cdots +{n \choose n}^{2}={2n \choose n}$
$\sum _{k=0}^{n}{r \choose m+k}{s \choose n-k}={r+s \choose m+n}$ (Вандермондăн свёртки)

Асимптотика тата хаклав

${2n \choose n}\sim {\frac {2^{2n}}{\sqrt {\pi n}}}$
$\sum _{k=0}^{m}{n \choose k}\leq {\frac {n}{(n/2-m)^{2}}}2^{n-3}$ при $m\leq n/2$ (неравенство Чебышёва)
$\sum _{k=0}^{m}{n \choose k}\leq 2^{nH(m/n)}$ (энтропиллĕ хаклав), ăçта $H(x)=-x\log _{2}x-(1-x)\log _{2}(1-x)$ — энтропи.
$\sum _{k=0}^{n/2-\lambda }{n \choose k}\leq 2^{n}e^{-2\lambda ^{2}/n}$ (Чернов танмарлăхĕ)