2-е занятие k-подмножества С помощью правил суммы и произведения можно решать различные задачи комбинаторики. Но это не всегда удобно, так же, как далеко. - презентация

1 2-е занятие k-подмножества С помощью правил суммы и произведения можно решать различные задачи комбинаторики. Но это не всегда удобно, так же, как далеко не всегда удобно сводить решение любой геометрической задачи к аксиомам. Наряду с аксиомами мы используем в геометрии теоремы, что позволяет сократить решение задачи. Точно так же в комбинаторике есть несколько простейших, «стандартных» задач, к которым часто удается свести решение других задач. Эти задачи формулируются на языке теории множеств. Впрочем, мы будем пользоваться лишь простейшими понятия­ми теоремы множеств,

2 в качестве примера возьмем множество из четырех элементов и будем изображать его подмножества и слова, составленные из элементов этого множества 1.Пусть множество N состоит из четырех элементов: коня, слона, ферзя и ладьи. K C Ф Л 2. В N имеется всего 2 4 подмножеств:С 4 0 =1 О-подмножество (пустое). С 4 1 =4 1-подмножества, С 4 2 =6 2-подмножеств, С 4 3 4=4 3-подмножества, С 4 4 =1 4-подмножество (все множество N). K,C,Ф,Л КС,КФ,КЛ,СФ,СЛ,ФЛ KСФ,KСЛ,KФЛ,CФЛ К,С,Ф,Л 3. Существует 4 2 =16 2-слов, составленных иэ элементов множества N. КК, КС, КФ,КЛ, СК,СС,СФ,СЛ, ФК,ФС,ФФ,ФЛ, ЛК,ЛС,ЛФ,ЛЛ

3 Существует А 4 2 =12 2-слов без повторений, составленных из элементов множеств N Существует Р4 = 4! = 24 перестановки элементов множества N

4 Решим следующую задачу. 5 студентов сдают зачет по плаванию. Зачет сдан, если студент проплывает 100 метров (время любое). Если же студента приходится вылавливать, то зачет не сдан. Сколькими способами может окончиться заплыв? Возможны различные случаи. Может случиться, что все студенты окажутся хорошими пловцами, а может случиться, что всех пятерых придется спасать. Общее число исходов можно сосчитать так. Расположим всех студентов в каком-то порядке, скажем но алфавиту: Андреев, Борисов, Володин, Григорьев, Дмитриев. Для каждого из них есть две возможности - либо он сдаст зачет, либо нет. В первом случае поставим в соответствие этому студенту цифру 1, а во втором цифру 0. Тогда исход заплыва выразится последовательностью длины 5 из нулей и единиц. Например, последователь­ность 0, 1, 1, 0, 1 означает, что достаточно хорошо плавают только Борисов, Володин и Дмитриев. А если зачет сдаст только Григорьев, то отчет об исходе соревнований бу­дет иметь такой вид: 0, 0, 0, 1, 0. Последовательность 0, 0, 0, 0, 0 означает, что ни один студент не достиг финиша.

5 Таким образом, задача о числе всех исходов заплыва свелась к следующей: сколько последовательностей длины 5 можно составить из цифр 0 и 1 ? Ответ на эту задачу дается правилом произведения; поскольку на каждом месте последовательности у нас выбор из двух возможностей, то общее число исходов равно 2х2х2х2х2 = 32. Итак, имеется 32 возмож­ных исхода заплыва. В разобранной задаче нам надо было узнать, сколько подмно­ жеств можно составить из множества N: {Андреев, Борисов, Володин, Григорьев, Дмитриев}. При этом допускалось и пустое подмножество, а также подмножество, совпадающее со всем множеством N. Ответ оказался равным 32 = 2 5. Точно так же доказывается, что если множество N содержит п элементов, то оно имеет 2 n подмно­жеств. Этот же результат можно доказать, воспользовавшись математической индукцией.

6 В олимпийских играх поступают так: в финал выходят двое лучших. Выясним, сколько исходов могут иметь соревнования в этом случае. Математически задача формулируется так: сколькими способами можно выбрать 2 элемента из множества, содержащего 5 элементов? Легко проверить, что это можно сделать 10 способами (выпишите сами все эти способы). Но такой метод «прямого перебора» годится лишь при малом числе участников. Хотелось бы иметь формулу, позволяющую сразу давать ответ на вопрос. Итак, нам надо решить следующую задачу: Сколько k-подмножеств содержится в множестве N из n элементов? Здесь мы для краткости говорим «k-подмножество» вместо «подмножество, содержащее k элементов». Выбор подмножества из данного множества N можно наглядно представить себе следующим образом. Элементы множества N сложим в мешок, а затем запустим в этот мешок руку и вытащим подмножество. Разумеется, все k элементов подмножества вытаскиваются сразу и никакого разумного порядка для них установить нельзя.

7 Обозначим число k - подмножеств в множестве из n элементов через С n k (это число называют числом сочетаний из n элементов по k) Числа С n k (их называют биномиальными коэффициентами) обладают целым рядом любопытных свойств. О многих из них было рассказано в статье Д.Б.Фукса и М.Б.Фукса «Арифметика биномиальных коэффициентов». В этой статье было доказано, что и с помощью метода математической индукции получена формула для Оба утверждения были выведены из равенства, но их можно доказать и комбинаторными рассуждениями.

8 3. k-слова. Снова возьмем в руки мешок с элементами множества N, но на этот раз будем вытаскивать элементы не сразу, а по очереди. Сначала вынем один элемент, обозначим его а 1 запишем и положим обратно в мешок. Потом вытащим второй элемент (может случиться, что нам снова попадется тот же самый элемент а 1 ), запишем его и т. д. После k выборов у нас получится запись вида (а 1,…,a k ), где a 1..., a k какие-то элементы из множества N. Такую запись мы назовем словом длины k или k-словом (иначе ее называют кортежем), составленным из элементов множества N. Два k-слова считаются совпадающими, если у них одинако­ вые первые элементы, одинаковые вторые элементы, одинаковые k-e элементы. С k-словами мы часто встречаемся на практике. Например, десятичные записи чисел - это «слова», составленные из 10 цифр, обычные слова - это «слова», составленные из русских букв, фразы - это «слова», составленные из русских слов. Решим следующую задачу.

9 Дано множество N, состоящее из п элементов. Сколько k-слов можно составить из элементов этого множества? Поскольку первый элемент можно выбрать n способами, второй тоже n способами,..., k-й тоже n способами, то /г-слово можно выбрать n k способами. Окончательно: из n элементов можно составить nк слов длины k. Многие комбинаторные задачи решаются по этому правилу. Найдем, например, сколькими способами можно разделить k различных предметов между n людьми. Для этого расположим элементы в каком-то порядке и над каждым предметом укажем, кому он предназначается. Например, запись показывает, что первому участнику раздела достанутся 1-й, 2-й, 6-й, 10-й предметы, второму - 4-й, 5-й, 7-й, а третьему - 3-й, 8-й, 9-й предметы. Мы видим, что каждый способ раздела задается k-словом (где k число предметов) из n элементов (номеров участников раздела). Значит, число способов раздела равно n к

10 4. k-слова без повторений. Опять возьмем в руки мешок, в который сложены элементы множества N, и начнем вытаскивать из него один за другим элементы этого множества. Но на этот раз не будем возвращать эти элементы в мешок, а выложим их в ряд. После k выборов у нас снова появится k-слово ( а 1,..., а n ), но на этот раз среди элементов а 1,..., а n нет повторяющихся (такие k-слова называются размещениями без повторений). По-другому можно сказать, что k-слова без повторений - это упорядоченные k- подмножества множества N. Число k-слов без повторений из и элементов обозначают А n k. Из правила произведения сразу вытекает, что В самом деле, первый элемент можно выбрать n способами, второй – только n-1 способами, ведь взять уже выбранный элемент нельзя. Третий элемент можно выбрать n-2 способами, …, k-й (n-k+1) способами. Значит, общее число способов действительно выражается этой формулой. Например, если из 10 членов комиссии надо назначить председателя, его заместителя и секретаря, то это можно сделать 10 х 9 х 8=720 способами.

11 5. Перестановки. Если из мешка вытаскиваются и выкладываются в ряд один за другим все элементы множества N (и ни один элемент не возвращается обратно), то в конце концов все элементы множества N окажутся расположенными в некотором порядке. В этом случае говорят о перестановках без повторений из n элементов. Таким образом, перестановка из n элементов это k-слово без повторений из n элементов. Полагая в формуле (3) k = n, получаем, что число перестановок из n элементов равно n! Его обозначают символом Р n. Итак, Рn = n!

12 6. Перестановки с повторениями. Мы уже знаем, что из п «букв» можно составить п к слов длины k. Некоторые из них отличаются друг от друга своим составом, а другие - только порядком элементов. Соберем все слова, имеющие один и тот же состав, а именно такие, в которые входят k 1 раз первая буква, k 2 раз вторая буква,..., k n раз n-я буква (мы считаем, что «буквы» в «алфавите» расположены в каком-то порядке). Ясно, что k = k 1 + k 2 + … + k n. Число «слов» в этом подмножестве обозначим через Р (k 1,…, k n ). Мы докажем сейчас, что Для этого заметим, что буквы, входящие в данное слово, можно переставлять друг с другом k! способами. Но не все из этих способов изменяют слово. Например, слово баллада не изменяется при перестановке второй и пятой или третьей и четвертой букв (в первом случае переставляются между собой две буквы а, а во втором - две буквы л). Подсчитаем число перестановок букв, не изменяющих слово состава (k 1,…, k n ). Легко видеть, что число таких перестановок равно (k 1 ! k 2 !…, k n ! ). (например, для слова баллада число таких перестановок равно 3! 2! - мы можем переставлять друг с другом 3! способами буквы а и 2! способами буквы л; буквы б и д входят лишь один раз). Поэтому, чтобы сосчитать число перестановок с повторениями, надо k! разделить на k 1 ! k 2 !…, k n ! Формула доказана.

13 Найдем, например, сколько различных слов получается при перестановке букв слова метаматематика. В это слово входят 3 буквы м, 2 буквы е, 3 буквы т, 4 буквы а, 1 буква и и 1 буква к, а всего 14 букв. Значит, число перестановок букв этого слова равно С помощью формулы для перестановок с повторениями можно получить новое доказательство формулы (2). Мы уже знаем, что каждое подмножество множества N можно зашифровать с помощью нулей и единиц. Если множество N содержит п элементов, а подмножество - k элементов, то получим k единиц и n-k нулей. Значит, в множестве из n элементов есть столько же k-подмножеств, сколько перестановок можно сделать из k единиц и n-k нулей. Таким образом,

14 задачи 1.Пусть р 1..., р к - различные простые числа. Сколько делителей имеет число где а 1,..., а к -некоторые натуральные числа (включая делители 1 и q)? 2. Сколькими способами можно переставить между собой буквы слова перешеек так, чтобы четыре буквы е не шли подряд? 3. Сколькими способами можно переставить буквы в слове камелия так, чтобы не менялся порядок гласных букв? 4.Сколькими способами можно переставить буквы слова огород так, чтобы три буквы о не стояли рядом? 5.Найдите сумму всех трехзначных чисел, которые можно записать с помощью цифр 1, 2, 3, 4 (любую из цифр можно использовать несколько раз). 6.Найдите сумму четырехзначных чисел, которые получаются при всевозможных перестановках цифр 1, 2, 3, Решите ту же задачу для цифр 1, 2, 2, 5.

15 Включения и исключения. Сколько существует целых положительных чисел, меньших 100, которые делятся на 2, но не делятся на 3 Для наглядности ситуацию можно изо­бразить двумя пересекающимися кругами В первом круге - множество чисел, которые делятся на 3, во втором - множество чисел, которые делятся на 2, а их пересечение (общая часть) - множество чисел, которые делятся на 6.. Нам нужны числа, которые делятся на 2, но не делятся на 3. Числа, которые делятся на 2, но не делятся на 3 - это числа, ко­ торые делятся на 2, но не делятся на 6. На рисунках 2а) и 2б) мы заштриховали нужное множество чисел. Очевидно, их количество равно = 33 (из 49 чисел, делящихся на 2, 16 делятся на 6)

16 Сколько существует целых положительных чисел, меньших 100, которые делятся на 3, но не делятся на 2 Решение задачи аналогично предыдущему решению только в этом случае нам нужно другое заштрихованное множество

17 Сколько существует целых положительных чисел, меньших 100, которые делятся на 3, или на 2 Решение задачи В этом случае мы также заштрихуем нужное нам множество. Это - объединение двух кругов (см пред. рис)- Если сложить количество чисел, которые делятся на 3, с количеством чисел, которые делятся на 2, то мы при этом два раза - посчитаем числа, которые делятся на 6 (см пред рис.). Таким образом, от полученной суммы нам еще надо отнять количество чисел, ко­торые делятся на 6. Итак, ответ: = 66.

18 Сколько существует целых положительных чисел, меньших 100, которые не делятся ни на 3, ни на 2 Изобразим ситуацию в виде диаграммы (см.рис.). Квадрат - это множество всех целых положительных чисел, меньших 100, а круги - это множества чисел, делящихся на 2 и на 3. Нужное нам количество чисел заштриховано на рис.6. Количество таких чисел будет равно количеству чисел, находящихся в дополнении к объединению двух кругов. Сколько чисел в объединении двух кругов, мы уже подсчитали в предыдущей задаче. Ответ = 33.

19 Обозначим через N количество всех чисел, меньших 100, через N 2, N 3, N 2*..3 - соответственно количества чисел, которые делятся на 2, делятся на 3, делятся на 2*3, а через N / - количество чисел, которые не попадают ни в N 2, ни в N 3. Тогда из наших рассуждений мы получим формулу N / = N - N 2 - N 3 + N 2*3

20 Сколько целых положительных чисел, меньших 100,которые не делятся ни на 2, ни на 3, ни на 5? Решение задачи 1-4. Заметим, во первых, то если число делится и на 2, и на 5, то оно делится на 10; если оно делится и на 3, и на 5, то оно делится на 15, а если еще и на 2, то оно делится на 30. Изобразим ситуацию в виде диаграммы, где внутри квадрата - множество чисел, меньших 100, а в кружках - соответственно множества чисел, которые делятся на 2, на 3, на 5, Пусть N2 - количество чисел, которые делятся на 2, N3 - количество чисел, которые делятся на 3, N5 - количество чисел, которые делятся на 5. N2*.3 - делящиеся и на 2, и на 3, N3*5 -делящиеся и на 3, и на5. Наконец, N2*3*5 - количество чисел, которые делятся и на 2, и на 3, и на 5, а N / - количество чисел, которые не делятся ни на 2, ни на 3, ни на 5

21 Оказывается, верна следующая формула: N / = N – N 2 – N 3 – N 5 + N 2*3 + N 2*5 + N 3*5 – N 2*3*5 (*) Все числа, которые стоят в правой части равенства, легко посчитать: N = 99. N 2 = 49 N 3 = 33, N 5 = 19 N 2*3 =N 6 =16, N 3*5 = N 15 = 6, N 2*3*5 = 3. По формуле ( * ) мы получаем нужное нам число N / = 26. Осталось доказать формулу ( * ). Мы должны посчитать, сколько чисел содержится в квадрате, но не попадает ни в один из кругов. Если мы вычтем из N сумму N 2 + N 3 + N 5, то числа, попавшие ровно в два из трех кругов, мы вычтем два раза, а числа, попавшие во все три круга - даже три раза. Теперь к разности N – N 2 – N 3 – N 5 добавим сумму N 2*3 + N 3*5 + N 2*5 Тогда все числа, попадающие в один или два круга, мы учли правильно и только числа, попадающие во все три круга - неправильно: их количество мы трижды вычли и вновь трижды добавили. Придется из суммы N – N 2 – N 3 – N 5 + N 2*3 + N 3*5 вычесть еще N 2*3*5. Теперь все числа, входящие в объединение трех кругов, мы учли по разу и пришли к формуле (*).

22 задачи Задача Сколько существует целых положительных чисел, меньших 1000, которые не делятся ни на 2, ни на 3, ни на 5? Задача Сколько существует целых положительных чисел, меньших 1000, которые не делятся ни на 3, ни на 5, ни на 7, ни на 11? Задача Объединение множества A и B состоит из 25. элементов, пересечение - из 10 элементов. Сколько элементов в А, если в В : а) 15 элементов; 'б) 21 элемент; в) 10 элементов? Задача В школьной химической олимпиаде участвовали 21 человек, в физической - 26 человек, в математической - 29 человек. 14 школьников принимали участие и в химической, и в математической, 15 учащихся - и в физической, и в математической, 8 - во всех трех олимпиадах. Сколько школьников участвовали хотя бы в одной из трех олимпиад? Найти все возможные ответы. Задача У меня трое друзей. За месяц с каждым из них я обедал 9 раз, с каждыми двумя из них - 4 раза, со всеми тремя - 1 раз, без каждого из них - 15 раз. а)Сколько всего раз я обедал? б)Сколько раз я обедал один?