Контрольные вопросы
| скачать Раздаточный материал № 2 по теме "Элементы комбинаторики и бином Ньютона" Содержание §1. Элементы комбинаторики . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 §2. Треугольник Паскаля . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 §3. Бином Ньютона . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 Контрольные вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 Ответы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 Литература. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56§1. Элементы комбинаторики Пусть  , тогда произведение всех последовательных натуральных чисел от единицы до “n”  обозначим через n! (читается как эн-факториал). Итак, имеем по определению(1.1)  Например,  ,  .Рассмотрим конечное множество, содержащее n=5 элементов  . Из этого множества будем создавать подмножества двумя принципиально разными способами. В первом случае, реализуем обычный способ получения подмножеств, в котором порядок следования (перечисления) элементов роли не играет. Такими подмножествами будут наборы элементов, отличающиеся друг от друга или самими элементами или их числом: {а,b},{а,с}, {d}, (b,с,d,е), {а,b,с,d}, {а,b,с}, {е,d, b}, ... и т.д. Создаваемые подмножества (наборы элементов), в которых порядок следования элементов роли не играет, будем называть сочетаниями (комбинациями - отсюда и название комбинаторика). Обозначать сочетания будем так:  – число сочетаний из "n" элементов по "m" элементов. Выше приведённые наборы элементов (подмножества) суть: . В качестве несобственных подмножеств {а,b,с,d,е} и  будут фигурировать, очевидно,  соответственно.Теперь рассмотрим наборы элементов из того же множества {а,b,с,d,е}, учитывая порядок следования элементов в наборах элементов: {а,b}, {b,а}, (а,b,с), {b,с,а}, {с,а,b}, {а,b,с,d}, {d,с,b,а},... и т.д. Наборы элементов, в которых порядок следования (перечисления) элементов имеет определяющее значение, будем называть размещениями и обозначать так:  – число размещений из "n" элементов по "m" элементов. Выше приведённые наборы элементов суть:  .Получим формулу, по которой можно будет определить число . Очевидно, что = п ; расположим эти размещения в столбик:  .Рассмотрим  . Очевидно, что к каждому ранее выписанному в столбик размещению можно приписать в строке n-1 размещений, тогда всех будет n(n-1). Для определения  достаточно ко всем размещениям приписать n-2 размещений, тогда получим  или  , откуда нетрудно усмотреть общее правило для определения  :  где  .Если m=n, то имеем различные размещения в самом исходном множестве. В случае трёхэлементного множества {а,b,с} имеем: {с,а,b}, {b,с,а}, {с,b,а}, (b,а,с) и {а,с,b}, то есть  =6, включая и исходное множество. Размещения в исходном множестве называются перестановками и обозначаются так: Pп – число перестановок из "n" элементов. Таким образом, перестановки Pп являются частным случаем размещений при n=m. В формуле (1.2) при n=m имеем:  , то есть(1.3) Pп = п! Пример. Решить уравнение  Решение. ОДЗ:    , (х+1)(х+2)=132, х2+3х–130=0, х1,2=10, –13;отрицательное значение не удовлетворяет ОДЗ; стало быть, х=10. Формулу для определения числа размещений приведём к другому виду, умножив и разделив правую часть соотношения (1.2) на одно и тоже выражение, отличное от нуля:   , то есть: При выводе формулы предполагалось, что n  0, то есть множество размещений имеет хотя бы один элемент. Если п = 0, то это означает, что рассматривается пустое множество; а так как пустое множество имеет только одно подмножество (само себя), то  . Если условится, что 0!=1, то формула (1.4) будет давать верный результат и в случае п = 0. В самом деле,  . Пример. Упростить  Решение. ОДЗ:     Из определений сочетаний, размещений и перестановок следует, что  В самом деле, если во всех сочетаниях  сделать перестановки Pт, то получим все размещения . Исходя из соотношения (1.5), получаем Пример. Вычислить  Решение.  Отметим одно из свойств числа сочетаний  В самом деле, расписав по формуле (1.6) левую и правую части рассматриваемого соотношения, получим:   что доказывает справедливость свойства (1.7). Пример. Вычислить  .Решение.  .Обозначения  образованы от первых букв французских слов combinasion (сочетание), arrangement (размещение, приведение в порядок) и permutation (перестановка).§2. Треугольник Паскаля В известных формулах сокращённого умножения: (а+b)2=а2+2аb+b2, (а+b)3=а3+3а2b+Заb2+b3 численные коэффициенты в правых частях рассматриваемых соотношений представим в виде следующей таблицы чисел: (а + b)2 121 n=2 (а + b)3 1331 n=3 Слева от приведённой таблицы коэффициентов записаны биномы (суммы двух слагаемых) с соответствующими показателями степени, которые ещё раз приведены справа от таблицы коэффициентов. Назовём эти коэффициенты биноминальными. Дополним эту таблицу для показателей степени биномов, равных 1 и 0. Имеем:  m=0 m=1 m=2 m=3 Такая таблица биноминальных коэффициентов называется треугольником Паскаля. Числа, содержащиеся в этой таблице, будем ещё называть элементами. Начальную строку таблицы будем считать "нулевой" в соответствии со значением показателя степени бинома, определяющего эту строку. При этом следующая строка считается первой, последующая - второй и т.д. в соответствии с показателями степеней бинома, определяющего эти строки таблицы биноминальных коэффициентов. Отметим первое свойство треугольника Паскаля. Свойство I. Число элементов в любой строке треугольника Паскаля равно n+1, то есть на единицу больше показателя степени бинома, разложение которого даёт эту строку. Для удобства будем полагать начальный элемент любой строки "нулевым", тогда последний элемент в этой строке будет соответствовать показателю степени бинома, дающего в разложении эту строку. Нулевые, первые, вторые и все последующие элементы в каждой строке таблицы образуют в ней как бы диагонали, нумерация которых суть: m = 0,1,2,.. и т.д. В приведённом выше треугольнике Паскаля эти диагонали пронумерованы внизу и отделены друг от друга прямыми линиями. Теперь нетрудно уяснить правило, по которому можно продолжать построение треугольника Паскаля для  . Обозначим любой элемент таблицы через , где нижний индекс соответствует номеру строки, а верхний – номеру диагонали. Тогда любой элемент таблицы, кроме крайних в строках, при  определяется по формуле  , то есть имеемСвойство II: Любой элемент треугольника Паскаля, кроме крайних в строках, при определяется суммой двух чисел, расположенных в предшествующей строке, причём одно из них находится на той же диагонали, а второе – на предшествующей диагонали.Используя правило построения треугольника Паскаля (свойство II), продолжим составление таблицы биноминальных коэффициентов: 1 n = 0 1 1 n = 1 1 2 1 n=2 1 3 3 1 n=3 1 4 6 4 1 n=4 1 5 10 10 5 1 n = 5 1 6 15 20 15 6 1 n = 6 1 7 21 35 35 21 7 1 n = 7 1 8 28 56 70 56 28 8 1 n = 8 ^ Написать разложение бинома (а+b)n , где n=5. Решение. Используя пятую строку треугольника Паскаля, имеем   .Элементы любой строки треугольника Паскаля суть числа сочетаний членов разложения бинома с показателем степени "n" после приведения подобных членов, причем сумма показателей степени при "а" и "b" в любом члене разложения постоянна и равна показателю степени бинома «n». После такого отождествления биноминальных коэффициентов (элементов треугольника Паскаля) с числами сочетаний нетрудно и аналитически доказать справедливость свойства II:  . Свойство III. Крайние элементы в любой строке одинаковы и равны единице, то есть  .В самом деле,   .Свойство IV. Первые и предпоследние элементы в любой строке одинаковы и равны соответствующему показателю степени бинома, равному «n», то есть  . В самом деле,   .Свойство V. Вообще, равноудаленные от концов строки элементы одинаковы, то есть:  В самом деле, поскольку биноминальные коэффициенты в треугольнике Паскаля суть числа сочетаний, то свойства III, IV и V согласуются и вытекают из свойства сочетаний, представленного формулой (1.7) и доказанного ранее. Свойство VI. Из треугольника Паскаля усматриваем, что величины биномиальных коэффициентов от краев строки к ее середине возрастают, причем в чётной строке имеем один наибольший член разложения, а в нечетной строке – два. Свойство VII. Любой член разложения может быть получен произведением предшествующего члена на коэффициент, равный  , то есть имеет место формула  . В самом деле,   .Представим два свойства биноминальных коэффициентов, которые будут доказаны в следующем параграфе. Свойство VIII. Сумма биноминальных коэффициентов в любой строке треугольника Паскаля равна 2n, где n – показатель степени соответствующего бинома, то есть  Это свойство для трехэлементного множества было рассмотрено ранее, причём было указано на его ценность вообще в теории множеств. Свойство IX. В любой строке треугольника Паскаля сумма биноминальных коэффициентов, стоящих на нечётных местах, равна сумме биноминальных коэффициентов, стоящих на чётных местах, то есть  (данное обозначение включает и нуль во множество натуральных чисел).Отождествление биноминальных коэффициентов в треугольнике Паскаля с соответствующими числами сочетаний позволяют записать формулы сокращённого умножения в виде:   Возникает вопрос: будут ли иметь место аналогичные формулы для более высоких натуральных степеней бинома? Рассмотрим бином (a+b)4 :       Так как  (как начальные элементы строк),  (как последние элементы строк),    , то получим выражение для бинома четвёртой стёпени, аналогичное ранее рассмотренным, а именно  Приведённые выкладки наводят на мысль: не будет ли формула  справедлива для любого натурального "n". В следующем параграфе убедимся в этом с помощью метода математической индукции.§3. Бином Ньютона Теорема: для произвольных чисел "a" и "b"  и произвольного натурального числа "n" ( ) справедлива формула  где  — число сочетаний из "n" элементов по "k" элементов.Для n=1 соотношение (3.1) приобретает вид:  , так как  ; стало быть, для п=1 формула (3.1) верна. Допустим, что формула (3.1) верна для п = т, то есть (3.2)  Докажем справедливость формулы (3.1) для n=m+1. Итак, имеем  Выделим из первой суммы слагаемое, соответствующее k = 0 (то есть "нулевое слагаемое"), а из второй суммы выделим слагаемое, соответствующее k = т (то есть "последнее" слагаемое). Имеем  . Во второй сумме сделаем сдвижку нумерации слагаемых на одну позицию влево; при этом вместо "k" пишем k-1, а вместо m-1 пишем "m". Получаем      Учитываем, что  , а  ; далее,  (правило построения треугольника Паскаля, свойство II). Имеем   Компактная сумма получилась в результате вовлечения в сумму предшествующего ("нулевого") и последующего ("последнего") слагаемых. Если теперь учесть, что т +1=п , то получим формулу (3.1)  Таким образом, из допущения, что формула (3.1) верна для п=т (соотношение (3.2)), следует, что она верна для п =m+1 , и, так как эта формула верна и при п = 1, то на основании принципа математической индукции ее справедливость установлена для всех натуральных значений п. Соотношение (3.1) называется формулой Ньютона разложения натуральной степени бинома. Докажем с помощью формулы бинома Ньютона то положение, что сумма всех возможных подмножеств во множестве с числом элементов, равным "n", определяется числом, равным 2" (свойство VIII). Положив в формуле (3.1) а = b = 1, получим  , что требовалось доказать.Если в формуле (3.1) положить, что а=1, а b=-1, то получим   ; при этом выражение  можно представить как разность двух сумм с четными и нечетными значениями «m»:    ; из равенства сумм следует, что сумма биномиальных коэффициентов, стоящих на четных местах, равна сумме биномиальных коэффициентов, стоящих на нечетных местах (свойство IX).^ . Найти средний член разложения бинома  Решение. так как показатель степени бинома является четным числом, то в разложении этого бинома будет один наибольший член; стало быть, надо найти пятый член (  ). Имеем   Ответ:  .^ 1). Можно ли определить понятие множества? 2). Какие множества называются несобственными? 3). Важен ли порядок следования элементов во множестве при их перечислении? 4). Какие множества называются упорядоченными? 5). Какова сумма всех возможных подмножеств во множестве с конечным числом элементов в нем? 6). Что называется факториалом? 7). Чем отличаются сочетания от размещений? 8). Почему перестановки являются частными случаями размещений? 9). Выражение 0! имеет ли смысл? 10). Как определяется число перестановок? 11). Как определяется число размещений? 12). Как определяется число сочетаний? 13). Как связаны между собой размещения, сочетания и перестановки? 14). Почему в строках треугольника Паскаля n+1 элемент? 15). Зачем в треугольнике Паскаля вводятся понятия нулевой строки и нулевого элемента в строке (нулевая диагональ)? 16). Как строится треугольник Паскаля? 17). Как отождествляются элементы треугольника Паскаля (биномиальные коэффициенты) с числами сочетаний? 18). Каковы по величине равноудаленные от краев строки элементы треугольника Паскаля? 19). Каковы величины нулевого и первого элементов строки в треугольнике Паскаля? Почему? 20). Какова сумма показателей степеней в любом члене разложения бинома? 21). Сколько наибольших по величине элементов в строке треугольника Паскаля? 22). Доказать, что сумма коэффициентов, стоящих на четных местах, равна сумме коэффициентов, стоящих на нечетных местах. 23). В чем состоит принцип математической индукции? Упражнения1). Упростить или вычислить: a).  б).  в).  г).  д).  2). Решить уравнения: а).  б).  в).  г).  д).  е).  ж).  з).  и).  к).  л).  .3). Решить неравенства: а).  б).  в).  .4). Доказать, что  5). Во сколько раз число перестановок из девяти элементов больше, чем число перестановок из семи элементов? 6). К числу перестановок из десяти элементов добавили число перестановок из одиннадцати элементов. Во сколько раз увеличилось данное число? 7). Расписание одного дня содержит 5 уроков. Определить количество таких расписаний при выборе из 11 предметов. 8). Сколькими способами можно выбрать трех дежурных из группы в 20 человек? 9). Число элементов относится к числу размещений из них по три как 1:210. Определить число элементов. 10). Число размещений из "m" элементов по 2 относится к числу размещений из "m" по 4 как 1:12. Определить число элементов. 11). Комиссия состоит из председателя, его заместителя и еще пяти человек. Сколькими способами члены комиссии могут распределить между собой обязанности? 12). Число сочетаний из "m" элементов по три в пять раз меньше числа сочетаний из "m+2" элементов по четыре. Определить "m". 13). Из группы в 15 человек составляется комиссия из председателя и четырех членов. Сколькими способами это можно сделать? 14). Во взводе 5 сержантов и 50 солдат. Сколькими способами можно составить наряд из одного сержанта и трех солдат? 15). Сколькими способами можно группу из 15 человек разделить на две группы так, чтобы в одной группе было 4 человека, а в другой – 11? 16). Сколькими способами можно образовать дозор из трех солдат и одного офицера при наличии 80 солдат и трех офицеров? 17). Найти число диагоналей выпуклого 10-угольника. 18). Разложить бином (х + 1)7. 19). Вычислить  20). Найти седьмой член разложения  21). Найти член разложения  , не зависящий от а.22). Найти член разложения  , содержащий х8.23). Найти члены разложения, являющиеся целыми числами.   24). Сколько членов разложения  являются целыми числами?Ответы 1). а).  ; б).  в). 8; г). (m + 1)m; д). 15; 2). а). 6; б). 6; в). 10; г). 11; д). 10; е). 8; ж). 4; з). (3, 14); и). 3; к). 27; л). 2; 3). а). {8; 9; 10}; б). {0; 1; 2}; в).  5). 72; 6). 12; 7). 55440; 8). 1140; 9). 16; 10). 6; 11). 42; 12). {14; 3}; 13). 15015; 14). 98000; 15). 1365; 16). 246480; 17). 35; 18). х7 +7х6 +21х5 +35х4 +35х3 +21х2 +7х + 1; 19).  20) ; 21). 5005; 22).  ; 23). а). 60; б). 625; 24). 32.Литература 1. Пособие по математике для поступающих в вузы. Под редакцией Г.Н. Яковлева. – М.: “Наука”. – 1988. 2. Л.К. Головко, З.В. Демьяненко, А.Е. Журавель, В.Г. Стеценко. Математика. Сборник задач: Пособие для подготовительных отделений. – Киев: – 1988. 3. Справочник по элементарной математике ( для поступающих в вузы). Под редакцией П.Ф. Фильчакова. – Киев: “Наукова думка”. – 1972. 4. Виленкин Н.Я. Популярная комбинаторика. – М.: “Наука” – 1975. 5. Ежов И.И., Скороход А.В., Ядренко М.М. Элементы комбинаторики. – М.: “Наука” – 1975. 6. Кофман А. Введение в прикладную комбинаторику. – М.: “Наука”. – 1975. 7. В.Д. Морозова. Введение в анализ. – М.: Изд-во МГТУ. – 1996. 8. С.К. Соболев. Пособие по математике для поступающих в ВУЗ. Часть I. – М.: Изд-во МГТУ. – 1996.
|
плохо
1 