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

«Википеди» ирĕклĕ энциклопединчи материал

Биномлă коэффициентсем(1+x)^n бинома степенĕсемпе сарса хунин x коэффициенчĕсем (тепĕр сăмахпа Ньютон биномĕ):

(1+x)^n = {n\choose 0} + {n\choose 1}x + {n\choose 2}x^2 + \cdots = \sum_k {n\choose k} x^k.

Биномлă коэффициентăн пĕлтерĕшне {n\choose 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^k_n майлашу хисепĕн пĕтĕмлетĕвĕ пулать, ăна çуклă мар 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° пăранăçпа уйрăлса тăрать.

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

Пахалăхĕсем[тӳрлет]

Танлăхсем[тӳрлет]

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

Асимптотика тата хаклав[тӳрлет]

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

Çавăн пекех пăхăр[тӳрлет]

Каçăсем[тӳрлет]