КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Биноминальные коэффициентыЛекция 11 Тема: Полиномиальная формула. Треугольник Паскаля. Рекуррентные соотношения. План: 1. Треугольник Паскаля 2. Бином Ньютона 3. Свойства биномиальных коэффициентов 4. Рекуррентные соотношения. 5. Основные способы решения рекуррентных соотношений
Сnk (число сочетаний) - это число способов выбрать k различных (т.е. без повторений) предметов из n различных (0<= k <= n), без учета порядка выбора. Они могут быть вычислены по следующим формулам:
Треугольник Паскаля и Бином Ньютона:
В предыдущих примерах мы вычисляли числа Cnk непосредственно по формуле, делая много умножений и делений. Оказывается, есть метод вычислять сразу много разных Cnk, используя только сложение. Особенно важно это при программной реализации, поскольку компьютер складывает числа гораздо быстрее, чем умножает и тем более делит. Он основан на доказанном выше свойстве: Cn+1k+1=Cnk+Cnk+1. Давайте построим из чисел два бесконечных треугольника. В первом из них (см. рис. внизу слева) будем ставить единицы в самом верху и по краям каждом следующей строки, а каждое из остальных чисел будет равно сумме двух стоящих над ним слева и справа (этот треугольник называется треугольником Паскаля). Во втором (см. рис. внизу справа) будем последовательно выписывать значения Cnk, отводя по одной строке для каждого значения n и располагая в ней Cnk по возрастанию k. На самом деле эти треугольники одинаковы. Равенство первых нескольких строчек, можно заметить, а дальше надо уже доказывать.
Утверждение. Если строчки треугольника Паскаля и позиции в них нумеровать, начиная с нуля, то на k-м месте в n-й строке будет стоять значение Cnk (основное свойство треугольника Паскаля). Доказательство: Индукция по n (см. лекцию "Индукция", если вы еще не знакомы с этим методом). База: n =0 - действительно, C00 =1 - как раз то, что стоит на верхушке треугольника Паскаля. Переход: от n к n+1. Пусть в n-й строчке все числа уже равны значениям Cnk из n по соответствующим k. Рассмотрим n+1 -ю строчку. На ее краях (нулевое и n+1 -е места) стоят две единицы - и значения Cn+10 и Cn+1n+1 как раз равны 1. Далее, при всех k от 1 до n число, стоящее на k -м месте в n+1-й строке, равно сумме чисел, стоящих в n-й строке на k-1 -м и k -м местах соответственно (т.е. как раз двух стоящих над ним - по принципу построения треугольника Паскаля). По предположению индукции, они равны Cnk-1 и Cnk, а их сумма тогда будет Cnk-1+Cnk, что как раз равно Cn+1k, ч.т.д. Для справки мы приводим здесь первые 11 строчек (с нулевой по 10-ю) треугольника Паскаля - их можно посчитать и вручную. На компьютере, с помощью простой программы, можно вычислить значительно больше, и более быстрого алгоритма, чем треугольник Паскаля, пока не существует.
Такие, казалось бы, чисто комбинаторные вещи, как числа Cnk и треугольник Паскаля, неожиданно встречаются и в алгебре. Выпишем известные формулы сокращенного умножения:
Коэффициенты в этих формулах (и это лучше видно, когда выписаны еще нулевая и первая степень) - это числа из треугольника Паскаля, то есть Cnk. На самом деле, такая закономерность будет продолжаться и дальше, и называется она бином Ньютона. Точнее:
(a+b)n=an+Cn1an-1b+Cn2an-2b2+...+Cnn-1a1bn-1+bn.
Можно доказать эту формулу по индукции, как и основное свойство треугольника Паскаля. Приведем более простое объяснение:
(a+b)n=(a+b)(a+b)...(a+b) (n скобок). Раскрывая скобки, получаем в отдельных слагаемых произведения n букв, каждая из которых - a или b, т.е. an-kbk при каком-то k от 0 до n. Докажем, что для каждого такого k число таких слагаемых - ровно Cnk, откуда, приведя подобные, и получаем формулу бинома. Но это правда: an-kbk получается путем взятия a из k скобок и b из n-k оставшихся; разные такие слагаемые получаются путем разного выбора этих самых k скобок, а k скобок из n можно выбрать как раз Cnk способами, ч.т.д. Именно из-за бинома Ньютона числа Cnk часто называют биномиальными коэффициентами.
Дата добавления: 2014-01-07; Просмотров: 940; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |