Как рассчитать биномиальный коэффициент

ПРОИЗВОДЯЩИЕ
ФУНКЦИИ

[ последовательностей ]

Расширенные биномиальные коэффициенты

В данном очень важном приложении речь пойдёт о биномиальных коэффициентах, точнее, об их расширении на случай произвольных значений верхнего индекса. Иногда такая тема в литературе называется «расширенный треугольника Паскаля», поскольку расширение биномиальных коэффициентов влечёт за собой расширение треугольника Паскаля, который из этих коэффициентов состоит, а также рассматриваемая здесь функция (1+z) n (точнее, её разложение в ряд) называется биномиальным рядом.

Свойства биномиальных коэффициентов и доказательства основных тождеств в этом разделе не предусматривается, речь о них идёт только в контексте производящих функций. Предполагается, что читатель знаком с основными положениями комбинаторики или, по крайней мере, встречался с ними в реальной жизни. Ведь математика окружает нас со всех сторон. Числа, закономерности и разнообразные комбинации могут появиться где угодно: во время похода в магазин, расчета шансов на победу в казино, в теории управления и даже в футурологических прогнозах. В целом, все умеют считать. Но иногда комбинаторика оказывается более сложной, чем это необходимо в повседневной жизни. Скажем, при расчётах энтропии некоторой сложной физической системы, когда требуется вычислять количество допустимых конфигураций соответствующей физической модели. Так вот расширенные биномиальные коэффициенты как раз больше относятся к научным, а не повседневным расчетам.

Основные определения

Здесь я вынужден немного остановиться на определениях и обозначениях, чтобы не возникало недоразумений. Подготовленный читатель может пропустить этот пункт.

Биномиальный коэффициент обозначается символом , или (что часто встречается в русской литературе) .

Давайте сразу определимся с обозначениями. Правильное обозначение для биномиальных коэффициентов не , как учат в российских школах (и в университетах), а . К сожалению, я не знаю, по какой причине в России чаще используется обозначение , а в остальном Мире — . Поэтому учтите, что если вы пишите статью для российских журналов, вас поймут, как бы вы эти коэффициенты не обозначили, а для зарубежных журналов советую писать правильно.

Читается этот символ разными способами: «число сочетаний из n по k », или просто «из n по k », а также говорят «выбор k из n ». Смысл указанных выражений заключён в комбинаторной интерпретации этого символа — это число способов выбрать k объектов из n различных объектов, причём порядок выбора не важен. Например, из множества <1,2,3,4,5>можно выбрать два элемента десятью способами:

В общем случае известно, что

В процессе вычислений, чтобы не считать лишние факториалы, можно сразу часть множителей сократить:

От этой формулы и будем отталкиваться в будущем. Именно она и является правильным определением биномиальных коэффициентов. Число n называется верхним индексом, а k — нижним. В соответствии с комбинаторной интерпретацией, числа n и k должны быть целыми неотрицательными. Наша задача будет заключаться в том, чтобы расширить определение на произвольные значения n .

Биномиальные коэффициенты, упорядоченные специальным образом, образуют треугольник Паскаля.

В XVII веке французский математик, физик, философ Блез Паскаль впервые в своем «трактате об арифметическом треугольнике» наиболее полно рассказал о свойствах этого самого треугольника (хотя сам треугольник встречался в работах других математиков задолго до Паскаля).

Строится этот замечательный треугольник очень просто:

По краям треугольника ставятся единицы, а любое число, стоящее не с краю, вычисляется как сумма двух чисел, расположенных сверху слева и сверху справа от него. Например, 10=4+6 , или 3=1+2 . Итак, речь зашла о треугольнике Паскаля в связи с тем, что он как раз образован биномиальными коэффициентами:

Для наших целей (и для удобства) лучше записывать треугольник, выравнивая его по левому краю:

Нули появляются за счёт нуля в числителе (когда k>n ). Заметьте, что в нулевом столбце ставятся единицы, так как

В числителе стоит произведение нулевого числа элементов, которое по определению равно 1. Данная формула верна для любого (в том числе, комплексного) n .

Ну вот, мы уже приближаемся к тому, чтобы изучить биномиальные коэффициенты для любого n . Наше расширение, во-первых, должно быть таким, чтобы формула осталась прежней (для удобства), во-вторых, треугольник Паскаля, образованный биномиальными коэффициентами (с целым отрицательным значением индекса), не должен потерять своё основное свойство:

оно гласит, что число в клетке (n,k) равно сумме верхнего числа и верхнего левого (когда числа выровнены по левому краю).

В-третьих (что самое важное), должна остаться справедливой биномиальная теорема, утверждение которой напоминается в следующем пункте.

Биномиальная теорема

Содержание данной теоремы в классической формулировке известно еще из средних классов школы:

Это выражение также носит название бином Ньютона. Коэффициенты бинома Ньютона и называются биномиальными коэффициентами.

Теперь, пользуясь биномом Ньютона и треугольником Паскаля, можно посчитать, например (взяв третью строчку треугольника),

Данный сайт посвящён производящим функциям, поэтому нас данная теорема интересует лишь с этой позиции. Запишем производящую функцию в следующем виде:

Представленная производящая функция генерирует последовательность биномиальных коэффициентов с верхним индексом, равным n . Верхний индекс в сумме можно записать равным ∞ , это ничего не меняет, когда n целое неотрицательное (почему?). Обратите внимание, что подстановка z=1 даёт замечательное тождество (ряд конечный, поэтому подстановка справедлива):

которое показывает, что сумма всех чисел в n -й строке треугольника Паскаля равняется двойке, возведённой в степень n .

Данное разложение функции (1+z) n в ряд согласуется с формулой Тейлора, в соответствие с которой коэффициент, стоящий при z k равен

Напомню, что для этой функции ряд Тейлора сходится при |z|

Все права защищены © 2010–2020, Zealint — 08.02.2020 06:37:42 +0300
Копирование материала только с указанием источника

Биномиальные коэффициенты

Биномиальные коэффициенты — коэффициенты в разложении (1 + x) n по степеням x (т. н. бином Ньютона):

Иначе говоря, (1 + x) n является производящей функцией для биномиальных коэффициентов.

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

для ; для k для ,

Биномиальный коэффициент является обобщением числа сочетаний , которое определено только для неотрицательных целых чисел n , k .

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

Обобщением биномиальных коэффициентов являются мультиномиальные коэффициенты.

Содержание

Треугольник Паскаля

позволяет расположить биномиальные коэффициенты для неотрицательных n , k в виде треугольника Паскаля, в котором каждое число равно сумме двух вышестоящих:

Треугольная таблица, предложенная Паскалем в «Трактате об арифметическом треугольнике» (1654), отличается от выписанной здесь поворотом на 45°. Таблицы для изображения биномиальных коэффициентов были известны и ранее (Тарталье, О. Хайяму и др.).

Свойства

Интересно, что если рассмотреть ряды в треугольнике Паскаля, состоящие из биномиальных коэффициентов, то в пределе получим функцию нормального распределения — распределение Гаусса.

• нечётен в двоичной записи числа k единицы не стоят в тех разрядах, где в числе n стоят нули,
• некратен простому pв p -ичной записи числа k все разряды не превосходят соотв. разрядов числа n ,
• В ряду биномиальных коэффициентов :
  • все числа не кратны заданному простому pn = mpk − 1 , где натуральное mk , где натуральное mn дает следующее тождество, выражающее суммы биномиальных коэффициентов с произвольным шагом sв виде замкнутой суммы из s слагаемых:

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

  • при m 2 ) при вычислении всей таблицы биномиальных коэффициентов) и O(n 2 ) времени (в предположении, что каждое число занимает единицу памяти и операции с числами выполняются за единицу времени).

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

  См. также

  • Биномиальное распределение
  • Треугольное число
  • Треугольник Паскаля
  • Пирамида Паскаля
  • Композиция (теория чисел)
  • Разбиение числа

  Ссылки

  • О. В. КузьминТреугольник и пирамида Паскаля: свойства и обобщения // Соросовский Образовательный Журнал. — 2000. — Т. 6. — № 5. — С. 101—109.
  • С. К. Абачиев Радужная фрактальность треугольника Паскаля

  Wikimedia Foundation . 2010 .

  Смотреть что такое “Биномиальные коэффициенты” в других словарях:

  Биномиальные коэффициенты — коэффициенты в формуле разложения Ньютона бинома … Большая советская энциклопедия

  БИНОМИАЛЬНЫЕ КОЭФФИЦИЕНТЫ — коэффициенты при степенях 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 … Википедия

  Бином ньютона — Бином Ньютона это формула , где биномиальные коэффициенты, n неотрицательное целое число. Содержание 1 Доказательство … Википедия

  Бином Ньютона

  Бином Ньютона – формула

  С натуральным n формула Бинома Ньютона принимает вид a + b n = C n 0 + a n + C n 1 + a n – 1 · b + C n 2 + a n – 2 · b 2 + . . . + C n n – 1 + a · b n – 1 + C n n · b n , где имеем, что C n k = ( n ) ! ( k ) ! · ( n – k ) ! = n ( n – 1 ) · ( n – 2 ) · . . . · ( n – ( k – 1 ) ) ( k ) ! – биномиальные коэффициенты, где есть n по k , k = 0 , 1 , 2 , … , n , а ” ! ” является знаком факториала.

  В формуле сокращенного умножения a + b 2 = C 2 0 · a 2 + C 2 1 · a 1 · b + C 2 2 · b 2 = a 2 + 2 a b + b 2
  просматривается формула бинома Ньютона, так как при n = 2 является его частным случаем.

  Первая часть бинома называют разложением ( a + b ) n , а С n k · a n – k · b k – ( k + 1 ) -ым членом разложения, где k = 0 , 1 , 2 , … , n .

  Коэффициенты бинома Ньютона, свойства биномиальных коэффициентов, треугольник Паскаля

  Представление биномиальных коэффициентов для различных n осуществляется при помощи таблицы, которая имеет название арифметического треугольника Паскаля. Общий вид таблицы:

  При натуральных n такой треугольник Паскаля состоит из значений коэффициентов бинома:

  Боковые стороны треугольника имеют значение единиц. Внутри располагаются числа, которые получаются при сложении двух чисел соседних сторон. Значения, которые выделены красным, получают как сумму четверки, а синим – шестерки. Правило применимо для всех внутренних чисел, которые входят в состав треугольника. Свойства коэффициентов объясняются при помощи бинома Ньютона.

  Доказательство формулы бинома Ньютона

  Имеются равенства, которые справедливы для коэффициентов бинома Ньютона:

  • коэффициента располагаются равноудалено от начала и конца, причем равны, что видно по формуле C n p = C n n – p , где р = 0 , 1 , 2 , … , n ;
  • C n p = C n p + 1 = C n + 1 p + 1 ;
  • биномиальные коэффициенты в сумме дают 2 в степени показателя степени бинома, то есть C n 0 + C n 1 + C n 2 + . . . + C n n = 2 n ;
  • при четном расположении биноминальных коэффициентов их сумма равняется сумме биномиальных коэффициентов, расположенных в нечетных местах.

  Равенство вида a + b n = C n 0 + a n + C n 1 + a n – 1 · b + C n 2 + a n – 2 · b 2 + . . . + C n n – 1 + a · b n – 1 + C n n · b n считается справедливым. Докажем его существование.

  Для этого необходимо применить метод математической индукции.

  Для доказательства необходимо выполнить несколько пунктов:

  1. Проверка справедливости разложения при n = 3 . Имеем, что
     a + b 3 = a + b a + b a + b = a 2 + a b + b a + b 2 a + b = = a 2 + 2 a b + b 2 a + b = a 3 + 2 a 2 b + a b 2 + a 2 b + 2 a b + b 3 = = a 3 + 3 a 2 b + 3 a b 2 + b 3 = C 3 0 a 3 + C 3 1 a 2 b + C 3 2 a b 2 + C 3 3 b 3
  2. Если неравенство верно при n – 1 , тогда выражение вида a + b n – 1 = C n – 1 0 · a n – 1 · C n – 1 1 · a n – 2 · b · C n – 1 2 · a n – 3 · b 2 + . . . + C n – 1 n – 2 · a · b n – 2 + C n – 1 n – 1 · b n – 1
  1. Доказательство равенства a + b n – 1 = C n – 1 0 · a n – 1 · C n – 1 1 · a n – 2 · b · C n – 1 2 · a n – 3 · b 2 + . . . + C n – 1 n – 2 · a · b n – 2 + C n – 1 n – 1 · b n – 1 , основываясь на 2 пункте.

  Доказательство 1

  a + b n = a + b a + b n – 1 = = ( a + b ) C n – 1 0 · a n – 1 · C n – 1 1 · a n – 2 · b · C n – 1 2 · a n – 3 · b 2 + . . . + C n – 1 n – 2 · a · b n – 2 + C n – 1 n – 1 · b n – 1

  Необходимо раскрыть скобки, тогда получим a + b n = C n – 1 0 · a n + C n – 1 1 · a n – 1 · b + C n – 1 2 · a n – 2 · b 2 + . . . + C n – 1 n – 2 · a 2 · b n – 2 + + C n – 1 n – 1 · a · b n – 1 + C n – 1 0 · a n – 1 · b + C n – 1 1 · a n – 2 · b 2 + C n – 1 2 · a n – 3 · b 3 + . . . + C n – 1 n – 2 · a · b n – 1 + C n – 1 n – 1 · b n

  Производим группировку слагаемых

  a + b n = = C n – 1 0 · a n + C n – 1 1 + C n – 1 0 · a n – 1 · b + C n – 1 2 + C n – 1 1 · a n – 2 · b 2 + . . . + + C n – 1 n – 1 + C n – 1 n – 2 · a · b n – 1 + C n – 1 n – 1 · b n

  Имеем, что C n – 1 0 = 1 и C n 0 = 1 , тогда C n – 1 0 = C n 0 . Если C n – 1 n – 1 = 1 и C n n = 1 , тогда C n – 1 n – 1 = C n n . При применении свойства сочетаний C n p + C n p + 1 = C n + 1 p + 1 , получаем выражение вида

  C n – 1 1 + C n – 1 0 = C n 1 C n – 1 2 + C n – 1 1 = C n 2 ⋮ C n – 1 n – 1 + C n – 1 n – 2 = C n n – 1

  Произведем подстановку в полученное равенство. Получим, что

  a + b n = = C n – 1 0 · a n + C n – 1 1 + C n – 1 0 · a n – 1 · b + C n – 1 2 + C n – 1 1 · a n – 2 · b 2 + . . . + + C n – 1 n – 1 + C n – 1 n – 2 · a · b n – 1 = C n – 1 n – 1 · b n

  После чего можно переходить к биному Ньютона, тогда a + b n = C n 0 · a n + C n 1 · a n – 1 · b + C n 2 · a n – 2 · b 2 + . . . + C n n – 1 · a · b n – 1 + C n n · b n .

  Формула бинома доказана.

  Бином Ньютона – применение при решении примеров и задач

  Для полного понятия использования формулы рассмотрим примеры.

  Разложить выражение ( a + b ) 5 , используя формулу бинома Ньютона.

  Решение

  По треугольнику Паскаля с пятой степенью видно, что биноминальные коэффициенты – это 1 , 5 , 10 , 10 , 5 , 1 . То есть, получаем, что a + b 5 = a 5 + 5 a 4 b + 10 a 3 b 2 + 10 a 2 b 3 + 5 a b 4 + b 5 является искомым разложением.

  Ответ: a + b 5 = a 5 + 5 a 4 b + 10 a 3 b 2 + 10 a 2 b 3 + 5 a b 4 + b 5

  Найти коэффициенты бинома Ньютона для шестого члена разложения выражения вида a + b 10 .

  Решение

  По условию имеем, что n = 10 , k = 6 – 1 = 5 . Тогда можно перейти к вычислению биномиального коэффициента:

  C n k = C 10 5 = ( 10 ) ! ( 5 ) ! · 10 – 5 ! = ( 10 ) ! ( 5 ) ! · ( 5 ) ! = = 10 · 9 · 8 · 7 · 6 ( 5 ) ! = 10 · 9 · 8 · 7 · 6 1 · 2 · 3 · 4 · 5 = 252

  Ответ: C n k = C 10 5 = 252

  Ниже приведен пример, где используется бином для доказательства делимости выражения с заданным числом.

  Доказать, что значение выражения 5 n + 28 · n – 1 , при n , являющимся натуральным числом, делится на 16 без остатка.

  Решение

  Необходимо представить выражение в виде 5 n = 4 + 1 n и воспользоваться биномом Ньютона. Тогда получим, что

  5 n + 28 · n – 1 = 4 + 1 n + 28 · n – 1 = = C n 0 · 4 n + C n 1 · 4 n – 1 · 1 + . . . + C n n – 2 · 4 2 · 1 n – 2 + C n n – 1 · 4 · 1 n – 1 + C n n · 1 n + 28 · n – 1 = = 4 n + C n 1 · 4 n – 1 + . . . + C n n – 2 · 4 2 + n · 4 + 1 + 28 · n – 1 = = 4 n + C n 1 · 4 n – 1 + . . . + C n n – 2 · 4 2 + 32 · n = = 16 · ( 4 n – 2 + C n 1 · 4 n – 3 + . . . + C n n – 2 + 2 · n )

  Ответ: Исходя из полученного выражения, видно, что исходное выражение делится на 16 .

  Источники:

  https://www.genfunc.ru/theory/pril02/
  https://dic.academic.ru/dic.nsf/ruwiki/810965
  https://zaochnik.com/spravochnik/matematika/vyrazhenija/binom-njutona/

  голоса

  Рейтинг статьи