Что такое биномиальный коэффициент

БИНОМИАЛЬНЫЕ КОЭФФИЦИЕНТЫ

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

Обозначение восходит к Л. Эйлеру (L. Euler); второе обозначение появилось в 19 в. и связано, по-видимому, с интерпретацией Б. к. как числа различимых неупорядоченных сочетаний из Nразличных объектов по пв каждом сочетании. Б. к. наиболее удобно выписываются в виде арифметического треугольника, или Паскаля треугольника, построение к-рого основано на свойстве Б. к.

Как понятие Б. к., так и арифметич. треугольник в более или менее развитой форме были известны еще математикам древности, Б. Паскаль (В. Pascal) составил подробное исследование (1665) свойств Б. к. Кроме соотношения (2), имеется много других полезных соотношений между Б. к., напр.:

В частности, отсюда получается

Использование Стирлинга формулы позволяет получать приближенные выражения для Б. к. Напр., если Nмного больше п:

На случай любого комплексного числа Б. к. обобщаются по формуле

Таблицы Б. к. см. [2], [3].

Лит.:[1] Кори Г., Корн Т., Справочник по математике, пер. с англ., 2 изд., М., 1973; [2] Большев Л. Н., Смирнов Н. В., Таблицы математической статистики, 2 изд., М., 1968; [3] Table of binomial coefficients, Cambridge, 1954. Е. Д. Соломенцев.

Смотреть что такое «БИНОМИАЛЬНЫЕ КОЭФФИЦИЕНТЫ» в других словарях:

Биномиальные коэффициенты — коэффициенты в разложении (1 + x)n по степеням x (т. н. бином Ньютона): Иначе говоря, (1 + x)n является производящей функцией для биномиальных коэффициентов. Значение биномиального коэффициента определено для всех целых чисел n и k. Явные формулы … Википедия

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

Паскаля треугольник — Биномиальные коэффициенты коэффициенты в разложении (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 … Википедия

Источник

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

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

Биномиальные коэффициенты — коэффициенты в разложении (1 + x)n по степеням x (т. н. бином Ньютона): Иначе говоря, (1 + x)n является производящей функцией для биномиальных коэффициентов. Значение биномиального коэффициента определено для всех целых чисел n и k. Явные формулы … Википедия

Паскаля треугольник — Биномиальные коэффициенты коэффициенты в разложении (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 … Википедия

Источник

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

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

Биномиальные коэффициенты — коэффициенты в разложении (1 + x)n по степеням x (т. н. бином Ньютона): Иначе говоря, (1 + x)n является производящей функцией для биномиальных коэффициентов. Значение биномиального коэффициента определено для всех целых чисел n и k. Явные формулы … Википедия

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

Паскаля треугольник — Биномиальные коэффициенты коэффициенты в разложении (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 … Википедия

Источник

Расчет биномиальных коэффициентов на Си (С++) и Python

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

или он же, но немного в другом виде. В левой колонке строки значение n, дальше в строке значения для k=0..n

В полном соответствии с рекуррентной формулой значения равны 1 и любое число равно сумме числа, стоящего над ним и числа «над ним+шаг влево». Например, в 7й строке число 21, а в 6й строке числа 15 и 6: 21=15+6. Видно также, что значения в строке симметричны относительно середины строки, т.е. . Это свойство симметричности бинома Ньютона относительно a и b и оно видно в факториальной формуле.
Ниже для биномиальных коэффициентов я буду также использовать представление C(n,k) (его проще набирать, да и формулу-картинку не везде можно вставить.

Расчет биномиальных коэффициентов через факториальную формулу

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

Значение в очередной строке должно быть примерно в 2 раза больше, чем в предыдущей. Поэтому последний правильно вычисленный коэффициент (см треугольник выше) — это C(12,6) Хотя unsigned int вмещает 4млрд, правильно вычисляются значения меньше 1000. Вот те раз, почему так? Все дело в нашей процедуре bci, точнее в строке, которая сначала вычисляет большое число в числителе, а потом делит его на большое число в знаменателе. Для вычисления C(13,6) сначала вычисляется 13!, а это число > 6млрд и оно не влезает в unsigned int.
Как оптимизировать расчет ? Очень просто: раскроем 13! и сократим числитель и знаменатель на 7! В результате получится . Запрограммируем расчет по этой формуле

Явно лучше, ошибка возникла при расчете C(31,15). Причина понятна — все то же переполнение. Сначала умножаем на 31 (оп-па — переполнение, потом делим на 15). А что, если использовать рекурсивную формулу? Там только сложение, переполнения быть не должно.
Что ж, пробуем:

Все, что влезло в unsigned int, посчиталось правильно. Вот только строчка с n=34 считалась около минуты. При расчете C(n,n/2) делается два рекурсивных вызова, поэтому время расчета экспоненциально зависит от n. Что же делать — получается либо неточно, либо медленно. Выход — в использовании 64 битных переменных.

Замечание по результатам обсуждений: в конце статьи добавлен раздел, где приведен простой и быстрый вариант «bcr с запоминанием» одного из участников обсуждения.

Использование 64 битных типов для расчета C(n,k)

2.8*10 19 уже не влезает в unsigned long long

Дальнейшее повышение точности и расчет при n>67

Для экстремалов и «олимпийцев»

В принципе, для практических задач точности функции bcd достаточно, но в олимпиадных задачах часто даются тесты «на грани». Т.е. теоретически может встретится задача, где точности double недостаточно и C(n,k) влезает в unsigned long long еле-еле. Как избежать переполнения для таких крайних случаев? Можно использовать рекурсивный алгоритм. Но если он для n=34 считал минуту, то для n=67 будет считать лет 100. Можно запоминать рассчтанные значения (см Дополнение после публиукации).Также можно использовать рекурсию не для всех n и k, а только для «достаточно больших». Вот процедура расчета, которая считает правильно для n 67 при малых k (к примеру, считает C(82,21)=1.83*10 19 ).

В какой-то из олимпиадных задач мне потребовалось вычислять много C(n,k) для n >70, т.е. они заведомо не влезали в unsigned long long. Естественно, пришлось использовать «длинную арифметику» (свою). Для этой задачи я написал «рекурсию с памятью»: вычисленные коэффициенты запоминались в массиве и экспоненциального роста времени расчета не было.

Дополнение после публикации

При обсуждении часто упоминаются варианты с запоминанием рассчитанных значений. У меня есть код с динамическим выделением памяти, но я его не привел. На даный момент вот самый простой и эффективный из комментария chersanya: http://habrahabr.ru/post/274689/#comment_8730359http://habrahabr.ru/post/274689/#comment_8730359

Если в программе надо использовать [почти] все коэффициенты треугольника Паскаля (до какого-то уровня), то приведенный рекурсивный алгоритм с запоминанием — самый быстрый способ. Аналогичный код годится и для unsigned long long и даже для длинной арифметики (хотя там, наверное, лучше динамически вычислять и выделять требуемый объем памяти). Конкретные значения N_MAX могут быть такими:
35 — посчитает все коэффициенты C(n,k), n 19
K_MAX — это может быть N_MAX/2+1, но не больше 35, поскольку C(68,34) за границей unsigned long long.
Для простоты можно всегда брать K_MAX=35 и не думать «войдет — не войдет» (до тех пор, пока не перейдем к числами с разрядностью >64 бита).

Расчет биномиальных коэффициентов на Python

Это дополнение появилось спустя примерно погода после публикации статьи. Автор начал осваивать Python и для тренироки я решаю олимпиадные задачи, сделанные ранее на C++. Для задач связанных в точными/длинными вычислениями приходится либо всячески исхитряться (как при расчетах биномиальных коэфиициентов), дабы избежать раннего переполнения, либо смиряться с потерей точности (перейдя к типу double) либо писать(или искать) длинную арифметику. В Python длинная арифметика уже есть, поэтому тут для вычисления биномиальных коэффициентов достаточно реализовать запоминание. Запоминать их будем в списке (передается в функцию как папаметр).

Вот вывод (без таблички)
270288240945436569515614693625975275496152008446548287007392875106625428705522193898612483924502370165362606085021546104802209750050679917549894219699518475423665484263751733356162464079737887344364574161119497604571044985756287880514600994219426752366915856603136862602484428109296905863799821216320
0.4200884663301988
Меньше полсекуды для такого коэффициента
C(68,34) (напомню — он не влезает в long long) считается за 0.017 сек и равен 28453041475240576740

Источник

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

Определение свойств чисел и выражение соотношений между подмножествами одного множества. Арифметический треугольник Паскаля. Алгоритм вычисления биномиальных коэффициентов. Рассмотрение комбинаторных тождеств: правила симметрии и свертки Вандермонда.

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

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

3. Комбинаторные тождества

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

Целью моей работы является проектирование содержания темы «Биномиальные коэффициенты» как элемента стохастической линии в курсе школьной математики.

Задачи при достижении этой цели ставятся следующие:

— разработать содержание темы «Сочетания и число сочетаний»;

Её можно записать после очевидных сокращений следующим образом:

Числа C_n k обладают рядом замечательных свойств. Эти свойства в конечном счёте выражают различные соотношения между подмножествами данного множества X. Их можно доказывать непосредственно, исходя из формулы (1), но более содержательными являются доказательства, опирающиеся на теоретико-множественные рассуждения.

1. Справедлива формула

2. Справедлива формула

Это равенство нетрудно получить с помощью формулы (1). В самом деле,

4. Арифметический треугольник Паскаля.

IV. Решите уравнение:

x = 4; C₈ 4 = 8•7•6•5 = 2•7•5 = 70.

Искомое значение x = 4.

Ответ: а) 8; b) 6; c) 7 d) 4.

Из школьного курса читателю известны формулы:

Обобщением этих формул является следующая формула, называемая обычно формулой бинома Ньютона:

В этой формуле может быть любым натуральным числом.

Вывод формулы (6) несложен. Прежде всего запишем:

где число перемножаемых скобок равно n. Из обычного правила умножения суммы на сумму вытекает, что выражение (7) равно сумме всевозможных произведений, которые можно составить следующим образом: любое слагаемое первой из сумм а + b умножается на любое слагаемое второй суммы a +b, на любое слагаемое третьей суммы и т.д. Hапример, при n = 3 имеем:

(a +b)(a + b)(a + b) = aaa + aab + aba + abb + baa + bab + bba + bbb.

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

Из формулы (6) можно получить целый ряд свойств этих коэффициентов. Например, полагая а =1, b = 1, получим:

С другой стороны, она равна

При x = 0 получим равенство

При всех k = 1, 2, …, n.

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

Разумеется, можно вычислить все биномиальные коэффициенты для любого n путём непосредственного перемножения n множителей (a + b), раскрытия скобок и приведения подобных членов. Правда, математикам древности и среднековья сделать это мешало отсутствие алгебраической символики. Например, в одном средневековом математическом тексте, имевшем хождение в Западной Европе в XV в. и, по-видимому, восходящем к арабам, биномиальные коэффициенты вычисляются очень наглядно путём возведения в степени числа 10001 и приводятся в виде таблицы.

Таблица 1. степень числа 1001 воспроизводит биномиальные коэффициенты.

Ат-Тутси (XIII в.) располагал таблицей биномиальных коэффициентов до n = 2 и, что важнее, привёл общее правило для их получения, которое в современных обозначениях может быть выражено так:

Таблица 2. Биномиальные коэффициенты.

Таблица 3. Треугольник Паскаля.

Вот ещё несколько свойств таблицы 3, доказанных Паскалем:

Треугольные и пирамидальные числа

Если обратиться к форме треугольник Паскаля, представленный в таблице 2, и рассмотреть её столбцы и нисходящие диагонали, то это рассмотрение ничего не даст: фактически, столбцы у таблиц 2 и 3 одни и те же, а нисходящие диагонали таблицы 2 совпадают со строками таблицы 3. Строки же таблицы 2 совпадают с восходящими диагоналями таблицы 3. Последовательность (1, 1, 2, 3, 5, 8, …), полученная при разборе восходящих диагоналей: 1; 1; 1+1 = 2; 1+2 = 3; 1+3 = 5, 1+3+1 = 5; 1+4+3 = 8 и т.д., обладает тем свойством, что каждое число в ней равно сумме двух предыдущих. Эти числа носят название чисел Фибоначчи и обладают многими интересными математическими свойствами, возникая в самых неожиданных задачах.

Гораздо проще вопрос о том, чему равны суммы чисел, стоящих на каждой из строк таблицы 2 ( и ли на каждой из восходящих диагоналей таблицы 3).

Приведём одно из свойств, связанных с делимостью биномиальных коэффициентов. Рассмотрим таблицу 2. Легко видеть, что все числа её 5-й строки, кроме крайних единиц, делятся на 5; все числа 7-й строки, кроме крайних единиц, делятся на 7. Очевидно, у 2-й и 3-й строки есть такое же свойство. А у остальных, легко видеть, такого свойства нет. Что объединяет числа 2, 3, 5 и 7 и отличает их от других чисел первого десятка? Верно, все они простые. Можно доказать, что, действительно, все числа n-ой строки треугольника Паскаля (в форме таблицы 2), кроме крайних единиц, делятся на n тогда и только тогда, когда n простое.

И наконец приведём сравнительно недавно, в общем, то, случайно обнаруженное свойство треугольника Паскаля, связывающее его с простыми числами (Г.В. Манн, Д. Шенкс, 1972г.). запишем строки треугольника Паскаля (в форме таблицы 2), каждый раз сдвигая строки в право на две позиции.

Таблица 4. Связь ряда простых чисел и треугольника Паскаля.

Числа, стоящие в таблице, выделены, если они делятся на номер строки. Числа в нижней строке, нумерующие столбцы, выделены, если в этом столбце все числа выделены. Выходит, что выделенные номера столбцов в точнсти соответствуют простым числам.

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

c) Используя равенство (а + b) 4 = (a + b) 3 ·(a + b), выведите формулу сокращённого умножения для суммы двух чисел в четвёртой степени.

Решённые примеры являются частными случаями бинома Ньютона.

b) При каком значении числа k получится наибольшее значение числа C k ₅?

c) Найдите сумму чисел во второй строке составленной таблицы.

d) Отметьтье на координатной плоскости точки (k, C k ₅).

а) Вторая строка в таблице будет пятой строкой в треугольнике Паскаля:

Источник