Біноміальний_коеффіціент definition of біноміальний_коеффіціент and synonyms of

Arabic Bulgarian Chinese Croatian Czech Danish Dutch English Estonian Finnish French German Greek Hebrew Hindi Hungarian Icelandic Indonesian Italian Japanese Korean Latvian Lithuanian Malagasy Norwegian Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swedish Thai Turkish Vietnamese

definition - Біноміальний_коеффіціент

В математиці біноміальні коефіцієнти - це коефіцієнти в розкладанні бінома Ньютона за ступенями x. Коефіцієнт при позначається (іноді) і Новомосковскется «біноміальний коефіцієнт з n по k» (або «це з n по k»):

В комбінаториці біноміальний коефіцієнт інтерпретується як кількість сполучень з n по k. тобто кількість всіх підмножин (вибірок) розміру k в n -елементном безлічі.

Біноміальні коефіцієнти часто виникають в задачах комбінаторики і теорії ймовірностей. Узагальненням біноміальних коефіцієнтів є поліноміальний коефіцієнти.

явні формули

Значення біноміального коефіцієнта визначено для всіх цілих чисел n і k. Явні формули для обчислення біноміальних коефіцієнтів:

для для або для

де позначає факторіал числа m.

трикутник Паскаля

дозволяє розташувати біноміальні коефіцієнти для невід'ємних цілих чисел n. k у вигляді трикутника Паскаля. в якому кожне число дорівнює сумі двох вищих:

Біноміальний_коеффіціент definition of біноміальний_коеффіціент and synonyms of

Трикутна таблиця, запропонована Паскалем в «Трактаті про арифметичний трикутник» (1 654), відрізняється від виписаної тут поворотом на 45 °. Таблиці для зображення біноміальних коефіцієнтів були відомі і раніше (Тартальї. О. Хайямові і ін.).

Рядки в трикутнику Паскаля в межі прагнуть до функції нормального розподілу.

Якщо взяти квадратну матрицю, відрахувавши N елементів по катетам трикутника і повернувши квадрат на будь-який з чотирьох кутів, то детермінант цих чотирьох матриць по модулю дорівнює 1 при будь-якому N. Якщо поставити уголом з 1 в верхній лівий кут, то детермінант матриці буде дорівнює 1.

У матриці числа на діагоналі i + j = const повторюють числа рядків трикутника Паскаля. (I, j = 0. ∞)

Матрицю де i, j = 0 ... p можна розкласти в добуток двох строго діагональних матриць. Перша ніжнетреугольная, а друга виходить з першої шляхом транcпонірованія. Елементи такої матриці

де i, j = 0. p Далі зворотна матриця до U

таким чином можна розкласти зворотну матрицю до в твір двох строго діагональних матриць і дати явне вираз для зворотних елементів. Перша верхнетреугольная, а друга виходить з першої шляхом транспонування.

i, j, m, n = 0. p, якщо вираз в кваратних дужках помилково, то елемент суми дорівнює 0. Елементи оберненої матриці змінюються при зміна її розміру і на відміну від матриці недостатньо приписати новий рядок і стовпець.

виробляють функції

Для фіксованого значення n виробляє функцією послідовності біноміальних коефіцієнтів є:

Для фіксованого значення k виробляє функцією послідовності біноміальних коефіцієнтів є:

Двовимірної виробляє функцією біноміальних коефіцієнтів є:

нечётен в двійковій запису числа k одиниці не стоять в тих розрядах, де в числі n стоять нулі.
некратен простому p в p -ічной записи числа k все розряди не перевищують відповідних розрядів числа n.
У послідовності біноміальних коефіцієнтів:
- всі числа не кратні заданому простому p, де натуральне число m
- всі числа, крім першого і останнього, кратні заданому простому p;
- кількість непарних чисел дорівнює ступеню двійки (ступінь двійки дорівнює кількості одиниць в двійковій запису числа n);
- не може бути порівну парних і непарних чисел;
- кількість не кратних простому p чисел одно, де числа - розряди p -ічной записи числа n; а число - її довжина.

Основні тотожності

(Правило симетрії).
(Винесення за дужки).
(Заміна індексів).

Біном Ньютона і слідства

для.
Це тотожність можна посилити

Згортка Вандермонда, слідства та ін.

0
a> = n
якщо - більш загальний вид тотожності вище.
- m -е гармонійне число.
Мультісекція ряду дає тотожність, що виражає суму біноміальних коефіцієнтів з довільним кроком s і зміщенням t у вигляді замкнутої суми з s доданків:

Асимптотика і оцінки

(Нерівність Чернова).

алгоритми обчислення

Біноміальні коефіцієнти можуть бути обчислені за допомогою формули, якщо на кожному кроці зберігати значення при. Цей алгоритм особливо ефективний, якщо потрібно отримати всі значення при фіксованому. Алгоритм вимагає пам'яті (при обчисленні всієї таблиці біноміальних коефіцієнтів) і часу (в припущенні, що кожне число займає одиницю пам'яті і операції з числами виконуються за одиницю часу).

При фіксованому значенні k біноміальні коефіцієнти можуть бути обчислені по рекуррентной формулою з початковим значенням. Для обчислення значення цей метод вимагає пам'яті і часу.