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

Біноміальні коефіцієнти - коефіцієнти в розкладанні (1 + x) n за ступенями x (т. Н. Біном Ньютона):

Інакше кажучи, (1 + x) n є виробляє функцією для біноміальних коефіцієнтів.

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

для; для k <0 или ; для ,

Біноміальний коефіцієнт є узагальненням числа сполучень, яке визначено тільки для невід'ємних цілих чисел n. k.

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

Узагальненням біноміальних коефіцієнтів є поліноміальний коефіцієнти.

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

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

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

Цікаво, що якщо розглянути ряди в трикутнику Паскаля, що складаються з біноміальних коефіцієнтів. то в межі отримаємо функцію нормального розподілу - розподіл Гаусса.

• нечётен в двійковій запису числа k одиниці не стоять в тих розрядах, де в числі n стоять нулі,
• некратен простому p в p -ічной записи числа k все розряди не перевищують соотв. розрядів числа n,
• В ряду біноміальних коефіцієнтів:
  • всі числа не кратні заданому простому pn = mpk - 1. де натуральне m

  • всі числа, крім першого і останнього, кратні заданому простому pn = pk. де натуральне m

  • кількість непарних чисел дорівнює ступеню двійки,
  • не може бути порівну парних і непарних чисел,
  • кількість не кратних простому p чисел одно, де числа - розряди p -ічной записи числа n; а число m = [logpn] + 1

• (Правило симетрії)
• (Згортка Вандермонда)
• Мультісекція ряду (1 + x) n дає наступне тотожність, що виражає суми біноміальних коефіцієнтів з довільним кроком s у вигляді замкнутої суми з s доданків:

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

• при m
• (Ентропійна оцінка), де H (x) = - x log2x - (1 - x) log2 (1 - x) - ентропія.
• (Нерівність Чернова)

Алгоритми обчислення біноміальних коефіцієнтів

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

Другий спосіб заснований на тотожність. Він дозволяє обчислити значення при фіксованому k. Алгоритм вимагає O (1) пам'яті (O (l) якщо потрібно порахувати l послідовних коефіцієнтів з фіксованим k) і O (k) часу.

Дивитися що таке "Біноміальні коефіцієнти" в інших словниках:

Біноміальні коефіцієнти - коефіцієнти у формулі розкладання Ньютона бінома ... Велика радянська енциклопедія

Біноміальних коефіцієнтів - коефіцієнти при ступенях z в розкладів Ньютона бінома. Б. к. Позначається або і дорівнює Позначення сходить до Л. Ейлера (L. Euler); друге позначення з'явилося в 19 ст. і пов'язано, по видимому, з інтерпретацією Б. к. як числа помітних ... ... Математична енциклопедія

Біноміальні коефіцієнти - так називаються кількості: l, n / 1, n (n 1) / (1.2), n (n 1) (n 2) / (1.2.3). n (n 1) (n 2). (N m + 1) / (1.2.3. M), що становлять коефіцієнти послідовних членів бінома Ньютона (див. Біном). Їх позначають в даний час часто знаком. Загальний вигляд Б ... Енциклопедичний словник Ф.А. Брокгауза і І.А. Ефрона

Паскаля трикутник - Біноміальні коефіцієнти коефіцієнти в розкладанні (1 + x) n за ступенями x (т. Н. Біном Ньютона): Інакше кажучи, (1 + x) n є виробляє функцією для біноміальних коефіцієнтів. Значення біноміального коефіцієнта визначено для всіх цілих ... ... Вікіпедія

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

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

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

біноміальний розподіл - (розподіл Бернуллі), розподіл ймовірностей числа появ деякої події при повторних незалежних випробуваннях, якщо ймовірність появи цієї події в кожному випробуванні дорівнює р (0≤р≤1). Саме, число μ появ цієї події ... ... Енциклопедичний словник

Послідовність Падована - Послідовність Падована це целочисленная послідовність P (n) з початковими значеннями і лінійним рекурентним співвідношенням Перші значення P (n) такі 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151, 200, 265 ... Вікіпедія