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

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

${\displaystyle (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},}$

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

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

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

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

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

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

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

${\displaystyle {n \choose k}={\frac {n!}{k!\;(n-k)!}}={\frac {n(n-1)(n-2)\cdot \dots \cdot (n-k+1)}{k!}}}$ çакшăн ${\displaystyle 0\leq k\leq n}$;

${\displaystyle {n \choose k}=0}$ для ${\displaystyle k<0}$ или ${\displaystyle 0\leq n<k}$;

${\displaystyle {n \choose k}=(-1)^{k}{-n+k-1 \choose k}}$ для ${\displaystyle n<0\leq k}$,

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

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

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

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

Пахалăвĕсем

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

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

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

Çак танлăх

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

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

Пахалăхĕсем

Танлăхсем

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

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

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

Çавăн пекех пăхăр

• Биномиллĕ уйăрлани

Каçăсем

• О. В. Кузьмин. Треугольник и пирамида Паскаля: свойства и обобщения, 2006 ҫулхи Кӑрлач уйӑхӗн 16-мӗшӗнче архивланӑ. СОЖ, 2000, No 5, с. 101–109.