Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Біноміальний коефіцієнт



План:


Введення

У математиці Біноміальні коефіцієнти - це коефіцієнти в розкладанні бінома Ньютона (1 + x) n за ступенями x. Коефіцієнт при x k позначається {N \ choose k} (Іноді C_n ^ k ) І читається "біноміальний коефіцієнт з n по k" (або "це з n по k"):

(1 + x) ^ n = {n \ choose 0} + {n \ choose 1} x + {n \ choose 2} x ^ 2 + \ ldots = \ sum_ {k = 0} ^ {\ infty} {n \ choose k} x ^ k.

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

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


1. Явні формули

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

{N \ choose k} = \ frac {n!} {k! (nk)!} = \ Frac {n (n-1) (n-2) \ cdot \ ldots \ cdot (n-k +1)} {k!} для 0 \ leqslant k \ leqslant n;
{N \ choose k} = 0 для k <0 або 0 \ leqslant n <k;
{N \ choose k} = (-1) ^ k {-n + k-1 \ choose k} для n <0 \ leqslant k,

де n! - факторіал числа n.


2. Трикутник Паскаля

Трикутник Паскаля.svg

Тотожність

{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 елементів по катетам трикутника і повернувши квадрат на будь-який з чотирьох кутів, то детермінант цих чотирьох матриць по модулю дорівнює 1 незалежно N. Якщо поставити вугілля з 1 в верхній лівий кут, то детермінант матриці дорівнюватиме 1.

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

Матрицю {I + j \ choose i} де i, j = 0 ... p можна розкласти в добуток двох суворо діагональних матриць. Перша ніжнетреугольная, а друга виходить з першої шляхом транcпонірованія. Елементи такої матриці U = {i \ choose j} [j <= i]

{I + j \ choose i} = UU ^ T де i, j = 0 ... p Далі зворотна матриця до U

U ^ {-1} = (-1) ^ {i + j} {i \ choose j} [j <= i] таким чином можна розкласти зворотну матрицю до {I + j \ choose i} у твір двох суворо діагональних матриць і дати явний вираз для зворотних елементів. Перша верхнетреугольная, а друга виходить з першої шляхом транспонування.

{I + j \ choose i} ^ {-1} _ {m, n} = \ sum_ {k = 0} ^ {p} (-1) ^ {m + n} {k \ choose m} {k \ choose n} [k> = m] [k> = n] i, j, m, n = 0 ... p, якщо вираз в дужках кваратних помилково, то елемент суми дорівнює 0. Елементи зворотної матриці міняються при зміна її розміру і на відміну від матриці {I + j \ choose i} недостатньо приписати новий рядок і стовпець.


3. Властивості

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

Для фіксованого значення n виробляє функцією послідовності біноміальних коефіцієнтів {N \ choose 0}, \; {n \ choose 1}, \; {n \ choose 2}, \; \ ldots є:

\ Sum_k {n \ choose k} x ^ k = (1 + x) ^ n.

Для фіксованого значення k виробляє функцією послідовності біноміальних коефіцієнтів {0 \ choose k}, \; {1 \ choose k}, \; {2 \ choose k}, \; \ ldots є:

\ Sum_n {n \ choose k} y ^ n = \ frac {y ^ k} {(1-y) ^ {k +1}}.

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

\ Sum_ {n, k} {n \ choose k} x ^ ky ^ n = \ frac {1} {1-y-xy}.

3.2. Подільність

З теореми Люка випливає, що:

  • {N \ choose k} Непара \ Iff в двійковій запису числа k одиниці не стоять у тих розрядах, де в числі n стоять нулі.
  • {N \ choose k} некратен простому p \ Iff в p-ічной запису числа k всі розряди не перевершують відповідних розрядів числа n.
  • У послідовності біноміальних коефіцієнтів {N \ choose 0}, \; \ ldots, \; {n \ choose k}, \; \ ldots, \; {n \ choose n} :
    • всі числа не кратні заданому простому p \ Iff n = m p k - 1 , Де натуральне m ;
    • всі числа, крім першого і останнього, кратні заданому простому p \ Iff n = p k ;
    • кількість непарних чисел дорівнює ступеня двійки (ступінь двійки дорівнює кількості одиниць в двійковій запису числа n);
    • не може бути порівну парних і непарних чисел;
    • кількість не кратних простому p чисел дорівнює (A_1 +1) \ ldots (a_m +1) , Де числа a_1, \; \ ldots, \; a_m - Розряди p-ічной запису числа n; а число m = [log p n] + 1 .

3.3. Тотожності

\ Binom {n} {t} + \ binom {n} {t + s} + \ binom {n} {t +2 s} + \ ldots = \ frac {1} {s} \ sum_ {j = 0} ^ {s-1} \ left (2 \ cos \ frac {\ pi j} {s} \ right) ^ n \ cos \ frac {\ pi (n-2t) j} {s}.

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

де H (x) = - x log 2 x - (1 - x) log 2 (1 - x) - ентропія.

  • \ Sum ^ {n/2- \ lambda} _ {k = 0} {n \ choose k} \ leqslant 2 ^ ne ^ {-2 \ lambda ^ 2 / n} (Нерівність Чернова).

4. Алгоритми обчислення

Біноміальні коефіцієнти можуть бути обчислені за допомогою формули {N \ choose k} = {n-1 \ choose k} + {n-1 \ choose k-1} , Якщо на кожному кроці зберігати значення {N \ choose k} при k = 0, \; 1, \; \ ldots, \; n . Цей алгоритм особливо ефективний, якщо потрібно отримати всі значення {N \ choose k} при фіксованому n . Алгоритм вимагає O (n) пам'яті ( O (n 2) при обчисленні всієї таблиці біноміальних коефіцієнтів) і O (n 2) часу (у припущенні, що кожне число займає одиницю пам'яті та операції з числами виконуються за одиницю часу).

При фіксованому значенні k Біноміальні коефіцієнти можуть бути обчислені за рекуррентной формулою {N \ choose k} = \ frac {n} {n-k} {n-1 \ choose k} з початковим значенням {K \ choose k} = 1 . Для обчислення значення {N \ choose k} цей метод вимагає O (1) пам'яті та O (n) часу.


Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Біноміальний розподіл
Негативне біноміальний розподіл
Коефіцієнт
P / B коефіцієнт
Коефіцієнт ексцесу
PEG коефіцієнт
Бета-коефіцієнт
Коефіцієнт ємності
Коефіцієнт змішування
© Усі права захищені
написати до нас
Рейтинг@Mail.ru