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

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

(1 + x)^{n} = (\binom{n}{0}) x^{0} + (\binom{n}{1}) x + (\binom{n}{2}) x^{2} + \dots + (\binom{n}{n}) x^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) x^{k},

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

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

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

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

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

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

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

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

çакшăн

0 \leq k \leq n

;

(\binom{n}{k}) = 0

для

k < 0

или

0 \leq n < k

;

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

для

n < 0 \leq k

,

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

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

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

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

Пахалăвĕсем

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

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

(\binom{n}{k}) = (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k})

Çак танлăх

(\binom{n}{k}) = (\binom{n - 1}{k - 1}) + (\binom{n - 1}{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 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \end{matrix}

Çак сĕннĕ виçкĕтеслĕ таблицăна Блез Паскаль «Арифметикăллă виçкĕтеслĕх çинченхи трактат» (1654) статьяра кăтартнă, статьяри тааблици кунтинчен 45° пăранăçпа уйрăлса тăрать.

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

Пахалăхĕсем

Танлăхсем

$(\binom{n}{k}) = (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k})$
$(\binom{n}{k}) = (\binom{n}{n - k})$ (симметри йĕрки (правили)
$(\binom{n}{0}) + (\binom{n}{1}) + \dots + (\binom{n}{n}) = 2^{n}$
$(\binom{n}{0}) + (\binom{n}{2}) + \dots + (\binom{n}{2 ⌊ n / 2 ⌋}) = 2^{n - 1}$
${(\binom{n}{0})}^{2} + {(\binom{n}{1})}^{2} + \dots + {(\binom{n}{n})}^{2} = (\binom{2 n}{n})$
$\sum_{k = 0}^{n} (\binom{r}{m + k}) (\binom{s}{n - k}) = (\binom{r + s}{m + n})$ (Вандермондăн свёртки)

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

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

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

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

Каçăсем

О. В. Кузьмин. Треугольник и пирамида Паскаля: свойства и обобщения, Шаблон:Webarchive СОЖ, 2000, No 5, с. 101–109.

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

Тупмалли

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

Пахалăвĕсем

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

Пахалăхĕсем

Танлăхсем

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

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

Каçăсем

Навигаци

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

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

Пахалăвĕсем

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

Пахалăхĕсем

Танлăхсем

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

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

Каçăсем

Навигаци

Шырамалли