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

Полиномиальная теорема Полиномиальная теорема ­ обобщение бинома Ньютона. Числа Cn(k1,k2,...,km), которые  участвуют в этой теореме, называют полиномиальными коэффициентами. Формула Полиномиальной теоремы (a1+a2+...+am)n=∑k1+k2+...+km=nCn(k1,k2,...,km)∗ak11∗ak22∗...∗akmm= =∑k1+k2+...+km=nn!k1!∗k2!∗...∗km!∗ak11∗ak22∗...∗akmm Доказательство ▼ Перемножим a1+a2+...+am последовательно n раз. При этом получим слагаемые  вида d1∗d2∗...∗dm, где из i­ой скобки берется множитель di, который и есть  буквой a1 или a2, или же буквой am. Сведем подобные слагаемые. Коэффициент  при ak11∗ak22∗...∗akmm, где k1+k2+...+km=n равняется количеству слов, сложенных  из k1 букв a1, k2 букв a2, km букв am, то есть Cn(k1,k2,...,km) ­ количество перестановок с  повторениями состава (k1,k2,...,km). Поскольку,Cn(k1,k2,...,km)=n!k1!∗k2!∗...∗km!, то  теорему доказано. ▲ Бином Ньютона является частичным случаем полиномиальной теоремы для m=2.  Действительно, при условии k1+k2=n выполняется n!k1!∗k2!=n!k1! ∗(n−k1)! откуда Cn(k1,k2)=Ck1n. Пример 1 Доказать, что ∑k1+...+km=nn!k1!∗k2!∗...∗km!=mn. ▼ За полиномиальной теоремой (a1+a2+...+am)n=∑k1+k2+...+km=nn!k1!∗k2!∗...∗km!∗ak11∗ak22∗...∗akmm Пускай a1=a2=...=am=1, тогда mn=∑k1+k2+...+km=nn!k1!∗k2!∗...∗km!∗1k11∗1k22∗...∗1kmm= =∑k1+k2+...+km=nn!k1!∗k2!∗...∗km! ▲ Пример 2 Вычислить (x+y+z)^3 ▼ Полиномиальные коэффициенты не зависят от перестановок своего состава, по этому  достаточно вычислить C3(0,0,3)=3!0!∗0!∗3!=1 C3(0,1,2)=3!0!∗1!∗2!=3 C3(1,1,1)=3!1!∗1!∗1!=6 и использовать полиномиальную теорему (x+y+z)3= =C3(0,0,3)∗(x3+y3+z3)+C3(0,1,2)∗(x∗y2+x2∗y+x∗z2+x2∗z+y∗z2+y2∗z) +C3(1,1,1)∗x∗y∗z= =(x3+y3+z3)+3∗(x∗y2+x2∗y+x∗z2+x2∗z+y∗z2+y2∗z)+6∗x∗y∗z ▲ Пример 3 Найти коэффициент при x8 в разложении полинома (1+2∗x4−3∗x8)9 ▼ За полиномиальной теоремой (1+2∗x4−3∗x8)9= =∑k1+k2+k3=99!k1!∗k2!∗k3!∗1k1∗(2∗x4)k2∗(−3∗x8)k3= =∑k1+k2+k3=99!k1!∗k2!∗k3!∗2k2∗(−3)k3∗x4∗k2+8∗k3 Для того что бы найти коэффициент при x8 разложении  полинома (1+2∗x4−3∗x8)9 необходимо для начала найти все тройки (k1,k2,k3), которые  дают x8. Для этого в целых не отрицательных числах решим систему: {k1+k2+k3=94∗k2+8∗k3=8 У нее есть два решения: (7,2,0) и (8,0,1). Из этого выплывает что коэффициент при x^8  равен 9!7!∗2!∗0!∗22∗(−3)0+9!8!∗0!∗1!∗20∗(−3)1=117 2. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ        2.1. Общие правила комбинаторики     Правило суммы. Пусть объект  способами, не совпадающими со способами выбора объекта  либо  » можно осуществить  и   общих, то указанный выбор можно осуществить   можно выбрать   есть     способами. Если среди способов выбора объектов   Тогда выбор «либо     способами, объект     способами. Пример. Имеется 10 билетов денежно­вещевой лотереи и 15 билетов художественной  лотереи. Сколькими способами можно выбрать один лотерейный билет? Билет денежно­вещевой лотереи можно выбрать 10 способами (все билеты различны),  билет художественной лотереи – 15 способами.  По правилу суммы, выбор одного лотерейного билета можно осуществить 10 + 15 = 25  способами. Пример. Сколькими способами из 28 костей домино можно выбрать кость, на которой  есть 1 или 2? Выбрать кость, содержащую 1, можно 7 способами, а кость, содержащую 2, – тоже 7  способами. Но среди указанных способов выбора есть один общий – это выбор кости 1:2.  Следовательно, общее число способов выбора нужной кости равно 7 + 7 – 1 = 13. Правило произведения. Пусть объект  способами. Тогда выбор «  и  » можно осуществить   можно выбрать   способами, объект   способами.   Пример. Из города  Сколько путей, проходящих через город   в город   идёт 5 дорог, из города   в город   4 дороги.   ведут из города   в город   ? Весь путь из   в   состоит из двух частей: из   в   и из   в  . Из города   в   можно попасть 5 способами, из города   в город   4 способами. Общее   в город    согласно правилу произведения, равно  город   число путей из города 2.2. Соединения   Если из некоторого количества различных меду собой элементов составлять различные  комбинации, то среди них можно выделить три типа комбинаций, носящих общее название – соединения. Рассмотрим эти типы. Определение 2.1. Если в некотором множестве  элементы, оставляя неизменным их количество, то каждая полученная таким образом  комбинация называется перестановкой.  переставлять местами  Общее число перестановок из m элементов обозначается Pm и вычисляется по формуле: Пример. Сколько шестизначных чисел, кратных 5, можно составить из цифр 1, 2, 3, 4, 5, 6 при условии, что в числе цифры не повторяются? Для того чтобы число, составленное из заданных цифр, делилось нацело на 5, необходимо  и достаточно, чтобы цифра 5 стояла на последнем месте. Остальные пять цифр могут  стоять на оставшихся пяти местах в любом порядке. Следовательно, искомое число  шестизначных чисел, кратных 5, равно числу перестановок из 5 элементов, т. е. Определение 2.2. Если составлять из т различных элементов группы по n элементов в  каждой, располагая взятые элементы в различном порядке, то получившиеся при этом  комбинации называются размещениями из т элементов по n. Общее число таких размещений рассчитывается по формуле: Замечание. Перестановки являются частным случаем размещений при  Пример. В седьмом классе изучается 14 предметов. Сколькими способами можно  составить расписание занятий на субботу, если в этот день недели должно быть 5  различных уроков? Различных способов составления расписания, очевидно, столько, сколько существует  пятиэлементных упорядоченных подмножеств учетырнадцатиэлементного множества. Следовательно, число способов равно числу размещений из 14 элементов по 5 элементов,  т. е. равно Пример. Найти   если Применяя формулу для числа перестановок и формулу для числа размещений, перепишем данное уравнение следующим образом: Полученное уравнение равносильно квадратному уравнению корнями которого являются числа  лишено смысла. Корень   При   уравнению удовлетворяет.  и   данное уравнение  Определение 2.3.  Если из т элементов составлять группы по n элементов в каждой, не  обращая внимания на порядок элементов в группе, то получившиеся при этом  комбинации называются сочетаниями из т элементов по n. Общее число сочетаний находится по формуле: Пример. В чемпионате страны по футболу участвуют 18 команд, причём каждые две  команды встречаются между собой 2 раза. Сколько матчей играется в течение сезона? В первом круге состоится столько матчей, сколько существует двухэлементных  подмножеств у множества, содержащего 18 элементов, т. е. их число равно Во втором круге играется столько же матчей, поэтому, согласно правилу суммы, в  течение сезона состоится 153 + 153 = 306 встреч. Пример. Решить неравенство Левая часть данного неравенства имеет смысл тогда и только тогда, когда   целое  число, принадлежащее отрезку   Правая часть неравенства имеет смысл в том и  только в том случае, когда   целое число, принадлежащее отрезку    Следовательно, решениями неравенства могут быть только целые числа из отрезка  Используя формулу числа сочетаний, запишем данное неравенство следующим образом:   Разделив обе части неравенства на   получим откуда   т. е.   Учитывая область допустимых значений данного  неравенства, получим множество его решений:    Одним из вариантов комбинаций являются перестановки с повторяющимися элементами. Если среди т элементов имеется т1 одинаковых элементов одного типа, т2 одинаковых  элементов другого типа и т. д., то при перестановке этих элементов всевозможными  способами получаем комбинации, количество которых определяется по формуле: Пример. Номер автомобиля состоит из трёх букв и трёх цифр. Сколько различных  номеров можно составить, используя 10 цифр и алфавит в 30 букв? Очевидно, что количество всех возможных комбинаций из 10 цифр по 4 равно 10.000. Число всех возможных комбинаций из 30 букв по две равно  учесть возможность того, что буквы могут повторяться, то число повторяющихся  комбинаций равно 30 (одна возможность повтора для каждой буквы). Итого, полное  количество комбинаций по две буквы равно 900. Если к номеру добавляется ещё одна  буква из алфавита в 30 букв, то количество комбинаций увеличивается в 30 раз, т. е.  достигает 27.000 комбинаций. Окончательно, так как каждой буквенной комбинации  можно поставить в соответствие числовую комбинацию, то полное количество  автомобильных номеров равно 270.000.000.  Если    2.3. Бином Ньютона. Полиномиальная формула   Бином Ньютона – это формула, выражающая выражение  формула имеет вид:  в виде многочлена. Эта  где   число сочетаний из n элементов по k. Широко известные формулы сокращённого умножения квадрата суммы и разности, куба  суммы и разности, являются частными случаями бинома Ньютона. Если степень n бинома  Ньютона невысока, коэффициенты многочлена могут быть найдены не расчётом по  формуле количества сочетаний, а с помощью так называемого треугольника Паскаля. Треугольник Паскаля имеет вид: 1 1  2  1 1  3  3  1 1  4  6  4  1 1  5  10  10  5  1 1  6  15  20  15  6  1  1  7  21  35   35  21  7  1 1  8  28  56  70  56  28  8  1 ………………………………….   Формула бинома Ньютона может быть обобщена для произвольного числа слагаемых: ,  где  Пример. В разложении  8, a = 9.  найти члены, содержащие хa, если k = 3, p = 2, n =  По формуле бинома Ньютона имеем: C учётом числовых значений: . . В принципе, можно записать разложение этого выражения в многочлен, определить  коэффициенты либо непосредственно, либо из треугольника Паскаля (степень бинома  сравнительно невелика), однако, делать это не обязательно, так как необходимо найти  только член разложения, содержащий х9. Найдем число i, соответствующее этому члену:    Находим:  Пример. В разложении   найти члены, содержащие xg. т = 9, g = 6. По обобщённой формуле бинома Ньютона получаем: Для нахождения полного разложения необходимо определить все возможные значения ni,  однако, это связано с громадными вычислениями. Поскольку надо найти только члены,  содержащие х6, то n1 = 6, а сумма всех четырёх значений n  равна 9. Значит, сумма n2 +  n3 + n4 = 3. Рассмотрим возможные значения этих величин (см. табл. 2.1).   Таблица 2.1      n2 n3 n4 0 0 3 0 3 0 3 0 0 1 2 0 1 0 2 0 1 2 Искомые члены разложения: Биномиальная и полиномиальная формулы Биномиальная формула (бином Ньютона) Рассмотрим произведение 0 2 1 2 0 1 1 1 1 2 1 0   здесь  вида   скобок, после раскрытия которых получается сумма одночленов  . Выясним, сколько раз встречается многочлен  столько раз, сколькими способами можно выбрать   скобок, из которых берется  , т.е.  Таким образом, после приведения подобных членов получим формулу  при данном  . Он встретится  .  Пример. Полиномиальная теорема Теорема. Доказательство. Чтобы после раскрытия скобок получился одночлен  скобок, из которых берется  из которых берется  членов равенчислу способов, которыми можно осуществить такой выбор.  скобок, из которых берется  , те  . Коэффициент при этом одночлене после приведения подобных  , нужно выбрать те   и т.д. и те     скобок,  Первый шаг последовательности выборов можно осуществить  —  коэффициент равен произведению  и т.д.,  ­й шаг —  , третий —   способами, второй шаг   способами. Искомый  Пример. Раскроем скобки в выражении  . Число 5 можно представить в виде суммы трех целых неотрицательных слагаемых  следующими способами: Заполним следующую табличку. В первом столбце приведены всевозможные разбиения  числа 5 на сумму трех слагаемых, второй столбец – коэффициент, который получится при одночлене, третий – вид одночлена (монома), и в скобках указано количество мономов  данного вида. Для первого разбиения приведены все мономы данного вида. Задачи. 1. Найдите разложение полиномов 1)  2)  3)  , , . 2. Найдите коэффициент при   в разложении полиномов 1)  2)  3)  4)  ; ; ; . 3. Докажите тождества 1)  2)  3)  4)  5)  , , , , .