Добавить материал

и получить 10 документов
и свидетельство автора

Изнауров Ахмед Изнаурович

основные тождества с биномиальными коэффициентами

Научно-исследовательская работа
Образовательные программы
Повышение квалификации
Подготовка к тестированию
docx
14.02.2017

Публикация педагогических разработок

Бесплатное участие. Свидетельство автора сразу.
Мгновенные 10 документов в портфолио.

Добавить материал

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

основные тождества с биномиальными коэффициентами.docx

основные тождества с биномиальными коэффициентами Биномиальный коэффициент В математике биномиальные коэффициенты — это коэффициенты вразложении бинома Ньютона (1 + x)n по степеням x. Коэффициент приxk обозначается (или «це из n по k»): (иногда ) и читается «биномиальный коэффициент из n по k» В комбинаторике биномиальный коэффициент число сочетаний из n по k, равное количеству всех подмножеств (выборок) размера k в n элементном множестве. интерпретируется как Биномиальные коэффициенты часто возникают в задачахкомбинаторики и теории вероятностей. Обобщением биномиальных коэффициентов являются мультиномиальные коэффициенты. Явные формулы Значение биномиального коэффициента Явные формулы для вычисления биномиальных коэффициентов: определено для всех целых чисел n и k. для для k < 0 или 0. Следовательно, а правая часть (5.19) также удовлетворяет этому рекуррентному соотношению. По индукции, обе части должны быть равны — Но есть более тонкое доказательство. Если — целое число из промежутка то биномиальная теорема показывает, что обе части (5.19) равны . А поскольку обе части представляют собой многочлены относительно степени или меньшей, то совпадения их только в различных точках достаточно (но толькотолько!) для установления равенства в общем случае. Вроде бы глупо обзаводиться соотношением, где одна сумма равна другой. Тем более, что ни одна из них не выражается в замкнутой форме. Но иногда вычислить одну суммуоказывается проще, чем другую. К примеру, если положить то получим альтернативную форму соотношения (5.16): А если положить то получим В левой части просуммирована только половина биномиальных коэффициентов с верхним индексом а эти коэффициенты равны своим двойникам в правой половине, поскольку треугольник Следовательно, левая часть — это просто Паскаля обладает левоправосторонней симметрией. и мы получаем формулу, которую никак не ожидали получить: Проверим ее при Поразительно, но факт. До сих пор мы рассматривали либо отдельные биномиальные коэффициенты, либо суммы, в члены которых входило только по одному биномиальному коэффициенту. Но многие из бросающих нам вызов задач включают в себя произведения двух и более биномиальных коэффициентов, поэтому оставшуюся часть этого раздела мы посвятим рассмотрению именно таких случаев. Вот удобное правило, которое зачастую помогает упростить произведение двух биномиальных коэффициентов:Мы уже встречались с частным случаем — правилом внесения Хотя как одна, так и другая части (5.21) суть произведения биномиальных коэффициентов, зачастую одну из них просуммировать проще, чем другую, благодаря взаимодействию с другими частями формулы. Так, встречается в левой части дважды, а в правой — лишь однажды. Поэтому при суммировании по мы, естественно, предпочитаем заменить на Равенство (5.21) справедливо исключительно по причине взаимного сокращения в факториальных представлениях Если все переменные — целые числа , то Здесь не было ничего сложного. К тому же, если или то обе части (5.21) равны нулю, так что данное соотношение выполняется при любых целых . Наконец, посредством полиномиальной аргументации его можно распространить на все вещественные Биномиальный коэффициент вида можно переписать в виде после соответствующего переобозначения переменных. Аналогично, величину в серединепредыдущей выкладки можно переписать в виде . Это „триномиальный коэффициент" который возникает в „триномиальной теореме": Таким образом, это на самом деле триномиальный коэффициент в другом обличии. Время от времени триномиальные коэффициенты возникают в приложениях, и их обычно записывают как чтобы подчеркнуть наличие симметрии. Обобщением биномиальных и триномиальных коэффициентов служат мультиномиальные коэффициенты, которые всегда выражаются в виде произведения биномиальных коэффициентов: Таблица 195 Суммы произведений биномиальных коэффициентов. А потому, при встрече с подобным страшилищем, нам поможет наше испытанное оружие. Вот мы и добрались до табл. 195, в которой перечислены наиболее важные из числа испытанных нами тождеств. Это те тождества, на которые мы опираемся в противоборстве с суммой, включающей в себя произведение двух биномиальных коэффициентов. Каждое из этих тождеств представляет собой сумму по к с одним к в каждом биномиальном коэффициенте; помимо этого, в нее входит по четыре почти не зависящих друг от друга параметра, обозначаемых через и т.д., — по одному на месте каждого индекса. В зависимости от того, входит или нет к в верхний или нижний индекс, а также от того, с каким знаком он входит, мы имеем дело с разными случаями. А внекоторых случаях имеется и дополнительный множитель необходимый для того, чтобы сумма вычислялась в замкнутой форме. Таблица 195 слишком уж сложна для запоминания; она предназначена только для справок. Однако первоетождество из этой таблицы запоминается гораздо легче остальных и его не следует забывать. Оно устанавливает, что сумма (по всем целым к) произведения двух биномиальных коэффициентов, в которых верхние индексы постоянны порознь, а нижние индексы постоянны в сумме при любом к, равна биномиальному коэффициенту, полученному путем сложения как верхних, так и нижних индексов. Данное тождество известно как сверткаВандермонда, поскольку Александр Вандермонд написал по этому поводу в конце 18го века важную статью [45]; однако еще в 1303 г. оно было известно Чжу Шицзе из Китая. Все остальные тождества в табл. 195 можно получить из свертки Вандермонда, аккуратно выполняя преобразования обращения верхнего индекса, применяя правило симметрии и т. п., следовательно, свертка Вандермонда является „самым основным" из всех основных тождеств. Правило свертки Вандермонда можно доказать, исходя из замечательной комбинаторной интерпретации. Если заменить к на то можно считать, что , а на следовательно, требуется доказать тождество Пусть — целые неотрицательные числа (общий случай получается посредством полиномиальной аргументации). В правой части — это число способов выбрать человек из мужчин и женщин. В левой части каждый член суммы — это числоспособов выбрать к человек из мужчин и человек из женщин. А суммирование по всем к учитывает каждую возможность ровно по одному разу. Как правило, эти тождества применяются слева направо, так как упрощение идет именно в этом направлении. Но иногда оправданно движение в обратном направлении, даже если приходится временно идти на усложнение. При этом обычно образуется двойная сумма, в которой можно изменить порядок суммирования и потом упростить. Перед тем как двинуться дальше, посмотрим, как доказываются еще два тождества из табл. 195. Тождество(5.23) доказать легко: нужно всего лишь заменить первый биномиальный коэффициент на а потом применить свертку Вандермонда (522). Следующее тождество, (5.24), несколько сложнее. Путем последовательных преобразований его можно свести ксвертке Вандермонда, но можно доказать его столь же просто, если прибегнуть к старому испытанному методуматематической Зачастую индукция — это первое, к чему мы прибегаем, если в голову не приходит ничего другого, но здесь индукция по I подходит как нельзя лучше. индукции. Действительно, при все члены суммы равны нулю, за исключением члена с так что обе части данного равенства равны . А теперь предположим, что данное тождество справедливо при всех значениях, меньших некоторого фиксированного I, где Можно воспользоваться формулой сложения для замены тогда на первоначальная сумма распадается на две суммы, каждую из которых можно вычислить, исходя из предположения А если еще раз применить формулу сложения, то это упрощается и получается правая часть (5.24).В этом выводе заслуживают внимания две вещи. Вопервых, мы вновь убеждаемся в огромном преимуществе суммирования по всем целым к, а не по к в определенных пределах, поскольку не нужно беспокоиться по поводу граничных условий. Вовторых, формула сложения чудесно стыкуется с математической представляет рекуррентную зависимость для биномиальных коэффициентов. Биномиальный коэффициент, верхний индекс которого есть I, выражается в виде суммы это именно то, что требуется двух коэффициентов, верхние индексы которых суть индукцией, поскольку она для предположения индукции. Пожалуй, хватит о табл. 195. А что можно сказать о суммах с тремя и более биномиальными коэффициентами? Если индекс суммирования разбросан по всем коэффициентам, то шансы отыскать сумму в замкнутой форме невелики: известно лишь несколько сумм такого рода, которые выражаются в замкнутой форме, и нужная нам сумма вполне могла не соответствовать предъявленным требованиям. Одна из таких редкостей, доказанная в упр. 43, это сумма А вот другой, более симметричный экземпляр: У него есть двойник с двумя коэффициентами: который, между прочим, не фигурирует в табл. 195. Аналогичная сумма с четырьмя коэффициентами не выражается в замкнутой форме, зато выражается другая подобная ей сумма: Это было обнаружено Джоном Дуголом [111] в начале двадцатого столетия. Является ли тождество Дугола самой лохматой из известных сумм биномиальных коэффициентов? Вовсе нет! Чемпионом такого рода до сих пор остается суммаЭто сумма по переменным индексам при Равенство всего лишь ее частный случай при в случае ее можно переписать следующим образом, если воспользоваться обозначениями вместо (си, вместо Левая часть (5.31) — это коэффициент при получающийся после полного разложения произведения дробей по положительным и отрицательным степеням z. Предположение о виде правой части (5.31) было высказано Фримэном Дайсоном в 1962 г. и вскоре после этого было доказано сразу несколькими людьми. В упр. 95 приводится „простое" доказательство (5.31). Заслуживает внимания еще одно тождество, включающее в себя массу биномиальных коэффициентов: У данного тождества, доказанного в упр. 83, даже есть шансы встретиться в практических приложениях. Впрочем, мы уже отклоняемся от нашей темы „основные тождества" так что лучше остановиться и подвести итог пройденному материалу. Мы убедились, что биномиальные коэффициенты удовлетворяют такому разнообразию тождеств, которое способно сбить

Материалы на данной страницы взяты из открытых источников либо размещены пользователем в соответствии с договором-офертой сайта. Вы можете сообщить о нарушении.

Посмотрите также