Дискретная Математика. Учебное пособие Допущено научнометодическим советом по математике вузов СевероЗапада в качестве учебного пособия для студентов вузов, обучающихся по специальностям 220200
 Скачать 6.37 Mb.
|
|
Пример 1. В комнате несколько человек, знающих хотя бы один из трех языков. Шестеро знают английский, шестеро - немецкий, семеро - французский. Четверо знают английский и немецкий, трое - немецкий и французский, двое - французский и английский. Один человек знает все три языка. Сколько человек в комнате? Сколько из них знают только английский язык? Задачу можно решить традиционным способом «вычерпывания» множеств без применения формулу включений и исключений. Перепишем условие задачи более компактно в виде таблицы А Н Ф АН НФ ФА АНФ 6 6 7 4 3 2 1 Пусть из комнаты ушел человек, знающий все три языка, тогда получим А Н Ф АН НФ ФА АНФ 5 5 6 3 2 1 0 Пусть теперь ушли три человека (из оставшихся), знающие одновременно английский и немецкий языки; число людей, знающих другие пары языков, не изменится. А Н Ф АН НФ ФА АНФ 2 2 6 0 2 1 0 Пусть уйдут двое, знающие немецкий и французский. А Н Ф АН НФ ФА АНФ 2 0 4 0 0 1 0 Наконец, уходит человек, знающий французский и английский языки. Окончательно получим А Н Ф АН НФ ФА АНФ 1 0 3 0 0 0 0 Итак, в комнате остался один человек, знающий только английский язык, и трое, знающих только французский язык. Кроме того, вышло семь человек, значит, сначала в комнате было одиннадцать человек. Решим теперь эту же задачу методом включений и исключений. Пусть свойство A p - знать английский язык, аналогично H p и Ф p - свойства, характеризующие знание немецкого и французского языков. По условию задачи общее число людей составляют все, знающие хотя бы один язык; не знающих хотя бы один язык в задаче нет. По формуле (2.14.2) имеем 11 1 9 19 1 2 3 4 7 6 6 , , , , , Ф H A Ф H Ф A H A Ф H A p p p n p p n p p n p p n p n p n p n n 43 Число людей, знающих только английский язык, это Ф H A p p p n , , . По формуле (2.14.6) 1 1 2 4 6 , , , , , , Ф H A Ф A H A A Ф H A p p p n p p n p p n p n p p p n Так же легко может быть найдет ответ и на другие подобные вопросы. 2.15. Учет весов элементов в формуле включения и исключения Дальнейшие усложнения метода связаны с введением весов элементов. Как и прежде, будем считать, что веса это числовые характеристики элементов рассматриваемых множеств. Итак, пусть задано n - множество n S и каждому элементу n i S s n i ,..., 2 , 1 , приписан вес i s ω из k - множества свойств k p p p ,..., , 2 1 Тогда , свойством обладает не э элемен если , 0 , свойством обладает э элемен если , 1 j i j i i j p s p s s p а S s i i j j i s s p p ω ω - сумма весов элементов со свойством j p . Произведем r - выборку свойств r i i i p p p ,..., , 2 1 и обозначим сумму весов элементов, обладающих всеми r выбранными свойствами, через r i i i p p p ,..., , ω 2 1 , т. е. r i i i p p p ,..., , ω 2 1 это сумма весов элементов множества n S , которые обладают каждым из свойств k p p p ,..., , 2 1 . Сумму, распространенную на все возможные r - выборки свойств, обозначим k i i i i i i r r r p p p 1 2 1 2 1 ω ,..., , ω Здесь суммирование распространяется на все сочетания r i i i ,..., , 2 1 длины r из k свойств, количество сочетаний равно r k C . Таким образом, в r ω суммируются веса только тех элементов, которые имеют как минимум r свойств. Пусть элемент n i S s обладает t свойствами и r t , тогда его вес i s ω в r ω войдет r t C раз. Например, 1 1 ω ω ω ω 1 ω 2 1 i k i p p p p содержит k C k 1 членов, а 2 1 2 1 , 1 3 1 2 1 , ω , ω , ω , ω 2 ω i i k k i i p p p p p p p p содержит 2 1 2 k k C k членов и так далее. Через 0 ω обозначим сумму весов всех элементов множества n S . Данное определение 0 ω корректно, так как сумма 0 ω должно включать элементы, обладающие нуль свойствами и более. Действительно, любой из элементов множества n S удовлетворяет этим условиям. Положим r k ω - сумма весов элементов, обладающих равно r свойствами из k имеющихся, тогда 0 ω k - сумма весов элементов, которые не имеют ни одного из указанных свойств. При таких обозначениях теорема включений и исключений с учетом весов будет формулироваться следующим образом. Теорема 2.5. Сумма весов элементов, обладающих точно r свойствами из k свойств k p p p ,..., , 2 1 равна k r i r i r i r k i r i r i r k r k r r r r r k r r k r r r k i C i r C k C r C r C r C r k r C r C r C r C r ω 1 ω 1 ω 1 2 ω 1 ω ω ω 1 2 ω 1 ω ω ω 0 2 2 1 1 0 2 2 1 1 0 (2.15.1) Доказательство. Покажем, что вклад веса i s ω произвольного элемента n i S s в правую и левую часть формулы (2.15.1) одинаковый. Пусть n i S s обладает точно t свойствами. Тогда а) если r t , то s ω не входит в r k ω и не входит в i r ω , т. е. равенство (2.15.1) примет вид 0=0; б) если r t , то s ω входит один раз в r k ω и один раз в i r ω ; 44 в) если r t , то в r k ω s ω не входит и левая часть формулы (2.15.1) в этом случае равна нулю. В i r ω вес s ω входит i r t C раз, t i r . Правая часть формулы (2.15.1) для веса s ω одного элемента n i S s примет вид t C r C r C r t t r t r r r r ω 1 1 ω ω 1 r t i i r t r i r i t t r t t r t r t r r r t r r C C s C s C C s C C s C 0 1 1 1 ω ω 1 ω ω Но i r t r i r C C i r t r t C C i r t i r r t r t r t i r t i r t i r i r ! ! ! ! ! ! ! ! ! ! ! ! , тогда r t i i r t r i r i C C s 0 1 ω 0 1 1 ω 1 ω 1 ω 0 0 r t r t r t i r t i i r t i r t i r t r t i C s C C s C C s . Таким образом, и в этом случае формула (2.15.1) верна. Если все элементы n i S s n i ,..., 2 , 1 , имеют единичный вес, т. е. 1 ω i p , то k n k ω и сумма весов равна числу слагаемых в сумме r n r ω , тогда формула (2.15.1) превращается в k r i r i r i r k r k r r r r k i n C k n C r n C r n C r n 1 1 1 1 (2.15.2) Следующая теорема является, по сути, следствием теоремы 2.5. Теорема 2.6. Если даны n - множество n S , каждый элемент которого имеет вес, и k - множества свойств, то сумма 0 ω k весов элементов, не удовлетворяющих ни одному из заданных свойств, определяется по формуле k m k i i i i i i m k k k k p p p k 0 1 2 1 2 1 ,..., , 1 ω 1 2 ω 1 ω 0 ω 0 ω (2.15.3) Итак, сумма весов множества из n элементов, не удовлетворяющих ни одному из k свойств, равна сумме весов всех элементов множества 0 ω минус сумма весов элементов, обладающих хотя бы одним свойством, плюс сумма весов элементов, имеющих не менее двух свойств и так далее. Если все элементы n i S s n i ,..., 2 , 1 , имеют единичный вес, то k n k ω и сумма весов равна числу слагаемых в сумме. В этом случае n 0 ω , 0 ω k равно числу элементов множества n S , не удовлетворяющих ни одному из указанных k свойств. Тогда формула (2.15.3) переходит в формулу k m k i i i i i i m k k k i k j i k l j i l j i j i i k k k p p p n p p p n p p p n p p n p n n p p p n 0 1 2 1 1 1 1 2 1 2 1 2 1 ,..., , 1 ,..., , 1 , , , ,..., , (2.15.4) Метод включения и исключения применяется везде, где речь идет о разделении дискретных множеств, производимых в зависимости от наличия (или отсутствия) у элементов определенных свойств. К числу задач, решаемых с помощью этого метода, относятся, например, задачи о встречах или беспорядках, разновидности задач теории чисел и ее приложений, где применяются специальные функции Эйлера и Мебиуса Пример 1. Задача о беспорядках или задача о встречах. Пусть имеется конечное упорядоченное множество чисел ,..., 2 , 1 n Для них могут быть образованы перестановки n a a a ,..., , 2 1 . Число всех перестановок, очевидно, ! n . Среди этих перестановок имеются такие, где ни один из элементов не сохранил своего первоначального места: Август Фердинанд Мебиус (1790 - 1868) - немецкий математик. 45 ,..., 2 , 1 , n i i a i Такие перестановки называются беспорядками. Найдем число беспорядков. Множество n элементов рассматривается по отношению к множеству свойств элементов оставаться на своих местах ,..., 2 , 1 , : n i i a p i i Очевидно, что если k элементов закрепляются на своих местах, то число k N соответствующих перестановок равно ! k n Число способов, которыми можно выбрать k закрепленных элементов из общего количества n элементов равно k n C Число беспорядков, где ни один элемент не сохранил своего первоначального места, тогда находится по формуле, аналогичной формуле (2.15.3) ! ! 1 1 ! 1 1 ! 3 1 ! 2 1 1 1 ! ! ! 1 2 1 1 ! 2 ! 2 1 ! 1 ! ! 1 ! 1 ! 2 ! 1 ! 0 2 1 e n n k n k n k k n n n n n n n n n n n n C k n C n C n C n N n k k n n n k n k n n (2.15.5) Здесь выражение ... обозначает целую часть заданного числа, а e - основание натуральных логарифмов. Пример 2. Задача о числе перестановок, в которых остаются на своих местах k элементов. В этой задаче из n элементов k должно быть неподвижных. Число способов, которыми можно выбрать эти k неподвижных элементов равно k n C Оставшиеся k n элементов могут образовывать беспорядки, их число подсчитаем по формуле (2.15.5). Тогда по правилу произведения ! 1 1 ! 3 1 ! 2 1 ! ! ! 1 1 ! 3 1 ! 2 1 1 1 ! k n k n k n k n C k N k n k n k n (2.15.6) 2.16. Функция Эйлера Функцией Эйлера называется функция n , определенная на множестве N , значения которой равны числу k натуральных может быть и составных целых чисел, взаимно простых с n и не превосходящих n , то есть 1 , , 0 n k n k Для 1 n полагают 1 1 . Знаком b a, обозначается наибольший общий делитель натуральных чисел a и b . Взаимно простыми называются числа, наибольший общий делитель которых равен единице. Например, натуральные числа 5 и 7 взаимно просты, так как 1 7 , 5 Таким образом, взаимно простые числа друг на друга нацело не делятся. Функция Эйлера аналитически выражается следующим образом k i k j i k k j i i q q q n q q n q n n n 1 1 2 1 , 1 (2.16.1) где k - есть число простых делителей i q числа ,..., 2 , 1 , k i n Чаще функция Эйлера приводится в несколько другом виде , 1 1 1 1 1 1 1 1 2 1 2 1 2 1 1 k k k k i i q q q n q q q n q n n (2.16.2) Формулы (2.16.1) и (2.16.2) получим позже, а сейчас посчитаем значения n для 10 ,..., 2 , 1 n Разложим числа с 1 до 10 на простые делители. 1 1 1 1 1 3 2 6 46 1 2 2 1 7 7 1 3 3 3 2 8 2 2 4 2 3 9 1 5 5 1 1 5 2 10 1) 1 1 по определению. 2) 1 2 , 1 , 1 2 1 1 2 2 . Это число 1. 3) 1 3 , 2 , 1 3 , 1 , 2 3 1 1 3 3 . Два числа не превосходят 3 и взаимно просты с числом 3; это числа 1 и 2. 4) 1 4 , 3 , 1 4 , 1 , 2 2 1 1 4 4 . Это числа 1 и 3. 5) 1 5 , 4 , 1 5 , 3 , 1 2,5 , 1 5 , 1 , 4 5 1 1 5 5 Четыре числа удовлетворяют условию существования функции Эйлера. Это числа 1, 2, 3 и 4. 6) 1 6 , 5 , 1 6 , 1 , 2 3 1 1 2 1 1 6 6 . Это числа 1 и 5. 7) , 1 7 , 5 , 1 7 , 4 , 1 7 , 3 , 1 2,7 , 1 7 , 1 , 6 7 1 1 7 7 1 7 , 6 . Значение функции Эйлера в этом случае равно шести, так как шесть чисел удовлетворяют условию существования функции Эйлера. Это числа 1, 2, 3, 4, 5 и 6. 8) 1 8 , 7 , 1 8 , 5 , 1 3,8 , 1 8 , 1 , 4 2 1 1 8 8 . Значение функции Эйлера равно четырем. Это числа 1, 3, 5 и 7. 9) , 1 9 , 7 , 1 9 , 5 , 1 9 , 4 , 1 2,9 , 1 9 , 1 , 6 3 1 1 9 9 1 9 , 8 . Это числа 1, 2, 4, 5, 7 и 8. 10) 1 10 , 9 , 1 10 , 7 , 1 10 , 3 , 1 10 , 1 , 4 5 1 1 2 1 1 10 10 . Это числа 1, 3, 7 и 9. Таким образом, функция Эйлера для первых десяти значений аргумента может быть задана следующей таблицей. n 1 2 3 4 5 6 7 8 9 10 n 1 1 2 2 4 2 6 4 6 4 Выведем теперь формулы, представляющие функцию Эйлера. Для этого решим сначала такую вспомогательную задачу. Пусть k a a a ,..., , 2 1 - взаимно простые натуральные числа, то есть n j i a a j i а , , 1 , - некоторое натуральное число. Найдем число натуральных чисел, не превышающих n и не делящихся ни на одно из чисел k a a a ,..., , 2 1 Пусть i A - множество натуральных чисел, не превышающих n и делящихся на i a Тогда количество чисел, делящихся по крайней мере на одно из чисел k a a a ,..., , 2 1 равно 2 1 k A A A n 47 Очевидно i i a n A n , где опять x - наибольшая целая часть x , не превосходящая x . Множество k i i i A A A 2 1 - это множество тех чисел, которые делятся на k i i i a a a 2 1 , то есть k k i i i i i i a a a n A A A n 2 1 2 1 , поскольку числа k i i i a a a 2 1 взаимно простые. По формуле (2.14.2) получим k i k i i k k i i i k A A A n A A n A n A A A n 1 2 1 2 1 1 1 1 2 1 1 2 1 1 Тогда количество чисел, не превышающих n и делящихся, по крайней мере, на одно из чисел k a a a ,..., , 2 1 равно k i k i i k k i i i k a a a n a a n a n A A A n 1 2 1 2 1 1 1 1 2 1 1 2 1 1 Количество чисел, не превышающих n и не делящихся ни на одно из чисел k a a a ,..., , 2 1 равно k i k i i k k i i i k a a a n a a n a n n A A A n n 1 2 1 2 1 1 1 1 2 1 2 1 1 Эта формула аналогична формуле (2.14.3) и представляет собой по сути формулу включений и исключений. Ее можно было сразу написать, если ввести 1 1 i i p a n - свойство числа n делиться на 1 i a Тогда 1 i a n - количество чисел не превосходящих n и обладающих свойством 1 i p Пусть теперь n - натуральное число, разложение которого на простые множители имеет вид k k q q q n 2 1 2 1 , где k q q q ..., , 2 1 - простые числа. Если n - число натуральных целых чисел, взаимно простых с n , то по только что полученной формуле имеем k i i k i k i i k k k i i i q n q q q n q q q n q q n q n n n 1 1 1 2 1 2 1 1 1 1 1 1 1 1 1 1 1 2 1 2 1 1 Преобразования сумм в произведения очень громоздки и связаны с разложением многочлена на множители. Например, для 2 k соответствующие преобразования будут иметь вид 1 1 1 1 1 1 1 1 1 1 1 2 1 2 2 1 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 1 2 2 1 2 1 q q n q q q q n q q q q n q q q q q q n q q q q q q n q q n q n q n n Перечислим в заключение без доказательства свойства функции Эйлера. 1. Если 1 , b a , то b a b a . Например, 1 7 , 3 , 21 7 3 2 1 12 7 6 3 2 21 7 1 1 3 1 1 21 1 1 21 i i q 12 6 2 7 3 21 48 2. q q q q q 1 1 α 1 α α α Возьмем 3 2 , 8 n n , 2 3 2 2 4 8 4 2 1 1 2 3 3. k i i k i k i i i i q n q q q n i 1 1 1 α α 1 1 1 1 1 4. n q d d k i i n d k i q d i i i 1 α \ 1 \ α , где d - различные делители числа n . Например, если 1 1 5 2 10 n , то 10 \ 2 1 α 10 5 2 d i i i q d . Выражение 10 \ d d означает, что суммирование ведется по сем делителям числа 10, т. е. 10 \ 10 5 2 1 d d 10 4 4 1 1 5. n x n mod 1 , где 0 n и 1 , n x . Например, 7 , 3 n x , 6 7 3 3 7 mod 1 1 7 104 729 или 10 , 3 n x , 10 mod 1 1 10 8 81 3 3 4 10 Пример 1. Найти число способов разложения n шаров по m ящикам так, чтобы m r r 0 ящиков остались пустыми. Рассмотрим простейший пример. Пусть 1 , 5 , 3 r n m Из рисунка сразу ясно, что 1-й ящик 2-й ящик 3-й ящик порядок, т. е. номер шаров важен, сле- довательно, речь идет о n - переста- 1234 5 новках. В данном опыте выбирается 1235 пуст 4 ящик. Это выборка с повторениями, 1245 3 так как ящики могут повторяться, нап- ример, первый шар положен в первый Рис. 2.4. ящик, второй шар положен в первый ящик и так далее. На основе такого простого примера ясно, что речь идет о выборке m ящиков n раз ( n шаров) с повторениями (см. рис.2.4). Таким образом, число способов, которыми можно разместить n шаров по m ящикам равно n m Пусть m i p i ,.., 2 , 1 свойство, состоящее в том, что при данной раскладке ящик с номером i остался пустым. Тогда количество раскладок, обладающих свойствами m i i i p p p r i i i r 1 ,..., , 2 1 2 1 при одном способе выбора r пустых ящиков равно n i i i r m p p p n r ,..., , 2 1 , а общее количество раскладок, распространенное на все возможные способы выбора пустых ящиков, будет равно m i i i n r m i i i r r r m C p p p n 1 2 1 2 1 ,..., , Применим теперь формулу включений и исключений типа (2.15.2), получим m r k n k m r k r k m r k r k r k m r m l m k l r k l r k k m C C k C r n , , 0 , , 1 1 r m l r m l n l r m r m l l r m r m l r m r l r n l r m r l r l l r m C C l r m l r m C C l r m l r m C C l r m C C 0 0 1 ! ! ! ! , ! ! ! ! 1 n r m l l r m l r m l r m C C 0 1 49 2.17. Функция Мебиуса Функция Мебиуса n μ определяется для всех N n и равна , если , 1 , 1 α и если 0, , 1 если 1, μ 2 1 α α 2 α 1 2 1 k k i k q q q n q q q n n n k (2.17.1) где k k q q q n α α 2 α 1 2 1 - разложение аргумента на простые сомножители, такое же как для функции Эйлера (см. подразд. 2.16). Функция Мебиуса для первых десяти значений аргумента задается следующей таблицей. n 1 2 3 4 5 6 7 8 9 10 n μ 1 -1 -1 0 -1 1 -1 0 0 1 Рассмотрим некоторые свойства функции n μ и ее связь с функцией Эйлера. 1) n d n n d \ , 1 если , 1 , 1 если , 0 μ (2.17.2) причем суммирование идет по всем делителям d числа n . Итак, если 1 n , то n d d \ 1 1 μ μ . Если же 1 α α 2 α 1 2 1 k k q q q n , тогда n d k i i i k d n d C d d \ 1 0 μ , \ 1 μ μ 0 1 1 k , так как все делители d , для которых 0 μ d , имеют по формуле (2.17.1) вид r i i i q q q 2 1 , т. е. r i i i r q q q 1 μ 2 1 . Количество таких делителей r i i i q q q 2 1 , выбираемых из k q q q 2 1 равно r k C 2) Если n d d g n f \ , то n d d n f d n g \ μ , (2.17.3) где n f и n g определены на множестве N . Формула (2.17.3) называется формулой обращения Мебиуса. 3) n d d d n n \ μ . (2.17.4) Формула (2.17.4) устанавливает связь между функциями Эйлера и Мебиуса. Если k k q q q n α α 2 α 1 2 1 , то k i i n d q d d 1 \ 1 1 μ 2.18. Практическое занятие № 5. Формула включений и исключений 2.18.1. Из урны, содержащей m различных шаров, одновременно извлекают m s s 1 шаров, записывают их номера, а затем шары возвращаются обратно в урну. Можно составить d s m C различных наборов, получающихся в результате d извлечений. Найти число наборов, в которых а) встречаются все шары; б) ровно m r r 0 шаров не встречается. 2.18.2. Вычислить / / 2 1 k k S , где суммирование проводится по всем натуральным / k , не кратным 2, 3 и 5. 50 2.18.3. Четыре человека сдают свои шляпы в гардероб. В предположении, что шляпы возвращаются наугад, найти вероятность того, что в точности k человек получат свои шляпы назад. Рассмотреть все значения 4 0 k k 2.18.4. При обследовании читательских вкусов оказалось, что 60% студентов читают журнал A , 50% - журнал B , 50% - журнал C , 30% - журналы A и B , 20% - журналы B и C , 40% - журналы A и C , 10% - журналы A , B и C . Сколько процентов студентов: а) не читает ни одного журнала; б) читает в точности два журнала; в) читает не менее двух журналов. 2.18.5. Найти число целых положительных чисел, не превосходящих 100 и не делящихся ни на одно из чисел 3, 5 и 7. 50 2.18.6. Показать, что если m n 30 , то количество целых положительных чисел, не превосходящих n и не делящихся ни на одно из чисел 6, 10, 15, равно m 22 . 2.18.7. В классе 35 учащихся. Из них 20 посещают математический кружок, 11 - физический, 10 учащихся не посещают ни одного из этих кружков. Сколько учеников посещают и математический и физический кружок? Сколько учащихся посещают только математический кружок? 2.18.8. Сколькими способами можно расположить за круглым столом n супружеских пар так, чтобы мужчины и женщины чередовались и никакие двое супругов не сидели рядом? 2.18.9. В букинистическом магазине лежат 6 экземпляров романа И.С. Тургенева «Рудин», 3 экземпляра его же романа «Дворянское гнездо» и 4 экземпляра романа «Отцы и дети». Кроме того, есть 5 томов, содержащих романы «Рудин» и «Дворянское гнездо», и 7 томов, содержащих романы «Дворянское гнездо» и «Отцы и дети». Сколькими способами можно сделать покупку, содержащую не менее чем по одному экземпляру каждого из этих романов? 2.18.10. Вычислить: а) 100 ; б) 1000 ; в) p , где p - простое число. |