Дискретная Математика. Учебное пособие Допущено научнометодическим советом по математике вузов СевероЗапада в качестве учебного пособия для студентов вузов, обучающихся по специальностям 220200
 Скачать 6.37 Mb.
|
|
Пример 1. Найти число различных слов (бессмысленных), которое можно получить, переставляя буквы слова «математика». Разные буквы слова математика представляют собой множества k A A A ,..., , 2 1 , на которые можно разбить исходное слово и различные объединения которых будут давать новые бессмысленные слова. Здесь м м A т т A a a a A k , , , , , , , 6 3 2 1 , , , 6 5 4 к A и A e A Отсюда 1 , 2 , 2 , 3 6 5 4 3 2 1 r r r r r r Исходное множество 10 , , , , , , , , , , n а к и т а м е т а м S n Тогда по формуле (2.3.4) 151200 2 1 2 1 3 2 1 10 9 8 7 6 5 4 3 2 1 ! 1 ! 1 ! 1 ! 2 ! 2 ! 3 ! 10 N Подсчитаем, наконец, число r n, - сочетаний с повторениями из множества n S . Пусть элементы множества n S занумерованы числами ,..., 2 , 1 n Так как множество n S конечно или счетно, то эта операция всегда возможна. Тогда вместо r n, - сочетаний множества n S можно рассматривать r n, - сочетания из эквивалентного ему множества n S ,..., 2 , 1 в силу взаимно однозначного соответствия. Всякая r n, - выборка из S может быть записана в виде r n n n ,..., , 2 1 , где r n n n 2 1 , причем равенство возможно в силу того, что рассматриваются выборки с повторениями. r - выборке r n n n ,..., , 2 1 поставим в соответствие r - множество 1 ,..., 2 , 1 , 3 2 1 r n n n n r , в котором все элементы, очевидно, различны. Соответствие между r n n n ,..., , 2 1 и 1 ,..., 2 , 1 , 3 2 1 r n n n n r опять взаимно однозначное, причем r - множества 1 ,..., 2 , 1 , 3 2 1 r n n n n r являются r - сочетаниями без повторений из 1 r n - множества 1 ,..., 2 , 1 r S . По формуле (2.3.3) число r r n , 1 - сочетаний без повторения равно r r n C 1 . Тогда ! 1 1 ! 1 ! ! 1 ˆ 1 r r n n n n r r n C C r r n r n (2.3.5) 2.4. Бином Ньютона и полиномиальная теорема а) Бином Ньютона. Исторически название «бином Ньютона» несправедливо, ибо формулу n b a знали еще среднеазиатские математики, начиная с Омара Хайяма (около 1100 г.); в Европе до Ньютона ее знал Паскаль . Заслуга Ньютона в том, что он обобщил эту формулу для нецелого показателя n . Итак, n k n n n l n l l n n n k n k n k k n n b a C b a C b a C b a C b a C b a 0 0 1 1 1 0 0 (2.4.1) Формула (2.4.1) легко доказывается методом математической индукции. Действительно, при : 1 0 1 1 1 1 0 0 1 1 b a b a C b a C b a n Далее, предположив, что формула верна для 1 n , получаем Исаак Ньютон (1643 - 1727) - английский физик, астроном и математик. Гийас ад-Дин Абу-л-Фатх Омар ибн Ибрахим Хайям (около 1048 - после 1122) - иранский математик, астроном и поэт. Блез Паскаль (1623 - 1662) - французский математик. 23 1 1 1 0 1 1 1 1 0 1 1 1 1 k n k n k k n k n k n k k n n n n n b a C b a C b a b b a a b a b a b a Про ведем замену индекса суммирования 1 , 1 k j j k Тогда 1 0 1 1 1 n k k n k k n b a C n j j n j j n b a C 1 1 1 . Отсюда 1 0 1 1 1 1 n k k n k k n n k k n k k n n b a C b a C b a Выровняем пределы изменения индексов суммирования в обеих суммах. Для этого введем дополнительно , 0 , 0 1 1 1 n n n C C тогда n k k n k k n n k k n k k n n k k n k k n n k k n k k n b a C b a C b a C b a C 0 1 1 0 1 0 1 1 1 1 1 и Отсюда n k n k k n k k n k n k n k n k n k k n k n n b a C C k n k n k n k n k n k n C C b a C C b a 0 0 1 1 1 1 1 1 ! ! ! ! 1 ! ! 1 ! 1 1 ! 1 ! 1 Для n нецелого формула имеет вид ! 1 α 2 α 1 α α ! 3 2 α 1 α α ! 2 1 α α α 1 1 3 2 α k x k k x x x x при 1 x Биномиальное разложение служит основой для многих комбинаторных формул. Например, 1) 1 b a Получим n k n k n C 0 2 Это число равно числу всех возможных неупорядоченных подмножеств множества n S , состоящего из n элементов. Действительно, так как k n C число k - элементных подмножеств ( k n, - сочетаний) множества n S , то сумма в левой части есть число всех подмножеств. 2) 1 , 1 b a Отсюда n k k k n C 0 0 1 Из этого равенства вытекает, что суммы биномиальных коэффициентов, стоящих на четных и на нечетных местах, равны между собой, и каждая равна 2 1 n б) Полиномиальная теорема. Эта теорема является обобщением формулы бинома на случай k слагаемых. , 0 ,..., 0 , 0 2 1 2 1 2 1 2 1 2 1 2 1 ! ! ! ! n r r r r r r r k r r k n k k k k a a a r r r n a a a , (2.4.2) где суммирование проводится по всем решениям уравнения n r r r k 2 1 в целых неотрицательных числах, т. е. выражение n k a a a 2 1 равно сумме всех возможных слагаемых вида k r k r r k a a a r r r n ! ! ! ! 2 1 2 1 2 1 , где 2 1 n r r r k Пример 1. Вычислим 3 z y x Раскрывая скобки последовательно, производя умножение многочлена на многочлен и приводя подобные члены, получим 6 3 3 3 3 3 3 2 2 2 2 2 2 3 3 3 3 xyz y z x z z y x y z x y x z y x z y x Всего в выражении десять членов. Этот же результат легко получается по полиномиальной формуле (2.4.2) при 3 , 3 k n Система условий суммирования здесь имеет вид 3 , 0 , 0 , 0 3 2 1 3 2 1 r r r r r r Различных 24 числовых коэффициентов тоже три: , 1 ! 0 ! 0 ! 3 ! 3 , 3 ! 0 ! 1 ! 2 ! 3 6 ! 1 ! 1 ! 1 ! 3 Для более удобного написания конечного результата лучше составить таблицу всех возможных комбинаций индексов 1 r , 2 r и 3 r . 1 r 2 r 3 r 3 0 0 0 3 0 0 0 3 2 1 0 2 0 1 1 2 0 0 2 1 1 0 2 0 1 2 1 1 1 Тогда xyz yz xz z y xy z x y x z y x z y x 6 3 1 2 2 2 2 2 2 3 3 3 3 , что то же самое, что было получено раньше. 2.5. Практическое занятие № 3. Правила суммы и произведения. Перестановки и сочетания. Свойства биномиальных коэффициентов 2.5.1. Сколько трехзначных чисел можно составить из цифр 1, 2, 3, 4, 5, если каждую из этих цифр можно использовать не более одного раза? 2.5.2. Сколько имеется пятизначных чисел, которые делятся на 5? 2.5.3. На одной из боковых сторон треугольника взято n точек, на другой m - точек. Каждая из вершин при основании треугольника соединена прямыми с точками, взятыми на противоположной стороне. а) Сколько точек пересечения этих прямых образуется внутри треугольника? б) На сколько частей делят треугольник эти прямые? 2.5.4. Сколько есть двузначных чисел, у которых обе цифры четные? 2.5.5. Пассажир оставил вещи в автоматической камере хранения, а когда пришел получать вещи, выяснилось, что он забыл номер. Он только помнит, что в номере были числа 23 и 37. Чтобы открыть камеру нужно правильно набрать пятизначный номер. Какое наибольшее количество номеров нужно перебрать, чтобы открыть камеру? 2.5.6. Из колоды, содержащей 52 карты, вынули 10 карт. В скольких случаях среди этих карт окажется: а) хотя бы один туз; б) ровно один туз; в) не менее двух тузов г) ровно два туза? 2.5.7. Дано n точек, никакие три из которых не лежат на одной прямой. Сколько прямых можно провести, соединяя точки попарно? 2.5.8. В соревнованиях по гимнастике две команды имели одинаковое число участников. В итоге общая сумма баллов, полученных всеми участниками, равна 156. Сколько было участников, если каждый из них получил оценки только 8 или 9 баллов? 2.5.9. Расстояние от A до B - 999 км. Вдоль дороги стоят километровые столбы, на которых расстояние от A до B записаны так: 25 0 999 , 1 998 , 2 997 ,…, 999 0 . Сколько среди этих столбов таких, на которых есть только две различные цифры? 2.5.10. В некотором царстве каждые два человека отличаются набором зубов. Какова может быть наибольшая численность населения царства (максимальное количество зубов у человека – 32). 2.5.11. В роте имеется три офицера и сорок солдат. Сколькими способами может быть выделен наряд, состоящий из одного офицера и трех солдат? 2.5.12. На рояле 88 клавиш. Сколько существует последовательностей из шести попарно различных звуков? (В последовательности звуки идут один за другим). Сколько существует аккордов из шести звуков? (Аккорд получается, если любые 6 клавиш нажаты одновременно). 2.5.13. Сколько членов получится после раскрытия всех скобок в выражении 1 1 1 1 1 1 1 g f e d c b a ? 2.5.14. Сколько существует чисел от 0 до n 10 , в которые не входят две подряд идущие друг за другом одинаковые цифры? 2.5.15. Сколькими способами можно выбрать 6 карт из колоды, содержащей 52 карты, так, чтобы среди них были карты каждой масти? 2.5.16. Какова вероятность, купив один билет, угадать в спортлото (из 49): а) k номеров ( 6 ,..., 2 , 1 k ); б) хотя бы k номеров? 2.5.17. Сколькими способами можно посадить за круглый стол n мужчин и n женщин так, чтобы никакие два лица одного пола не сидели рядом? 2.5.18. Сколькими способами можно разложить в два кармана девять монет различного достоинства? 2.5.19. Сколько различных делителей имеет число а) 2310; б) 10!? 2.5.20. У англичан принято давать детям несколько имен. Сколькими способами можно назвать ребенка, если ему дадут не более трех имен, а общее число имен равно 300? 2.5.21. На перекрестке A автомобилист разбил стекло левой фары (см. рис. 2.1), и те- C B перь ему надо кратчайшим путем попасть в ремонтную мастерскую B , не попав при этом в пункт M . Скольки- ми способами он может выбрать маршрут? M E D F A Рис. 2.1. 2.5.22. Международная комиссия состоит из 9 человек. Материалы комиссии хранятся в сейфе. Сколько замков должен иметь сейф, сколько ключей для них нужно изготовить и как их разделить между членами комиссии, чтобы доступ к сейфу был возможен тогда и 26 только тогда, когда соберутся не менее 6 членов комиссии. 2.5.23. Определить сколько рациональных членов содержится в разложении: а) 20 3 3 2 ; б) 100 4 3 2 6 2.5.24. Найти коэффициент при k t в разложении: а) 17 , 2 15 7 4 k t t ; б) 10 , 2 2 20 3 k t t 2.5.25. Какое число больше 50 50 100 99 или 50 101 ? 2.5.26. Пусть n и m - целые положительные числа. Доказать а) n k n k n n kC 1 1 2 ; б) n k n k n n n C k k 2 2 2 1 1 ; в) n k n k n n C k 0 2 1 1 2 2.5.27. Доказать, что для любого n m ,..., 2 , 1 , 0 справедливо тождество n k k r m k m n r n C C C 0 2.5.28. Доказать, что 2 0 2 2 2 1 3 2 n i n i n i n C 2.5.29. Доказать тождества: а) n i n i n n n C C 1 1 1 2 1 1 2 ; б) n i n i n n n C C 1 2 1 2 2.5.30. Доказать, что 1 , 1 2 1 1 2 1 1 n n C C n i i n i n |