|
|
Основные принципы комбинаторикиКафедра математики, ТиМОМ Валицкас А.И. КОНСПЕКТ ЛЕКЦИЙ ПО ДИСЦИПЛИНЕ “ЭЛЕМЕНТЫ КОМБИНАТОРНОГО АНАЛИЗА”
Тобольск – 2012 С О Д Е Р Ж А Н И Е
ГЛАВА I. АЗЫ КОМБИНАТОРИКИ Основные принципы комбинаторики Комбинаторика занимается изучением объектов, сопутствующих конечным множествам. Основные из этих объектов: подмножества, разбиения, перестановки, сочетания, сочетания с повторениями. С комбинаторными объектами связаны две основные задачи: задача перечисления объектов и задача нахождения количества этих объектов. Прежде чем переходить к рассмотрению основных комбинаторных объектов, сформулируем часто используемые четыре основных принципа комбинаторики. Принцип сложения: если проводится испытание с x исходами, и независимо испытание с другими y исходами, то всего получается x + y исходов. Другими словами, если объект А можно выбрать x способами, а объект В – y способами, то для выбора одного из объектов А или В существует x + y возможностей. Пример:В одном ящике лежит 18 белых шаров, а в другом ящике – 20 чёрных. Сколькими способами можно выбрать 1 шар из двух ящиков ? Ясно, что 38-ю способами.
Ясно, что принципы умножения и сложения обобщаются и на случай произвольного количества испытаний с независимыми исходами. Принцип дополнения: если испытание заканчиваетсяx исходами, а первый исход встречается в y случаях, то для остальных исходов (2-го, … …, х-го) будет x–y возможностей. Этот принцип будет в дальнейшем обобщен (см. принцип включения-исключения). Несмотря на кажущуюся тривиальность эти принципы позволяют получить почти все нетривиальные комбинаторные результаты и решать задачи. Примеры: 1.Монету подбрасывают 10 раз, записывая результаты (орёл – “о” или решка – “р”), получая набор из десяти символов. Сколько всего существует различных возможных наборов ? В скольких случаях решка выпадает не менее двух раз ? Каждое из десяти испытаний приводит к двум независимым результатам: орлу или решке. По принципу умножения общее количество наборов (результатов десяти испытаний) равно 210 = 1024. Для нахождения количества наборов с не менее двумя решками удобнее найти дополнительное количество наборов с менее чем двумя решками. Ясно, что существует единственный набор без решек: все 10 орлов. Кроме того, существует 10 различных наборов с одной решкой. Таким образом, всего будет 11 наборов с менее чем двумя решками. А значит искомое количество наборов с не менее двумя решками равно 1024 – 11 = 1013. 2. В одном ящике лежит 18 белых шаров, а в другом ящике – 20 чёрных. Сколькими способами можно последовательно выбрать 2 шара: вначале любой, а потом – белый ? Хотя один шар выбирается 38-ю способами, но выбор второго шара существенно зависит от сделанного выбора первого. Поэтому нужно разбирать несколько случаев: 1) первый шар белый. Тогда после вытаскивания первого шара в первом ящике осталось 17 белых шаров, а во втором – 20 чёрных. Значит, выбор второго шара может осуществиться 17-ю способами, а последовательный выбор двух шаров – 18×17 способами. 2) первый шар чёрный. Его можно вытащить 20-ю способами. После этого в первом ящике осталось 18 белых шаров, а во втором – 19 чёрных. Значит, выбор второго шара может осуществиться 18-ю способами, а последовательный выбор двух шаров – 20×18 способами. Общее количество способов: 18×17 + 20×18 = 18×37. Замечание:Здесь не применим сразу принцип умножения, поскольку выбор второго шара зависит от выбора первого. Принцип взаимно однозначного соответствия: два конечных множества А = {a1 , … , an} и B = {b1 , … , bm} содержат одинаковое число элементов тогда и только тогда, когда существует взаимно однозначная (биективная) функция f : A ® B. Здесь нужно вспомнить, что функция f : A ® B называется взаимно однозначной (или биективной), если выполнены три условия: 1) f(a) определено для каждого a Î A, 2) f инъективна, т.е. различные элементы переводит в различные (" x, y Î A f(x) = f(y) ® x = y), 3) f сюръективна, т.е. отображает А на всё множество B (" b Î B $ a Î A f(a) = b). Пример: Сколько существует упорядоченных пар (i; j), где 1 £ Сопоставим каждой паре (i ; j) число f(i, j) = n·(i – 1) + j. Ввиду ограничений на i, j верны оценки: 1 = n·(1 – 1) + 1 £ f(i, j) £ n·(n – 1) + n = n2 . Таким образом построено отображение f : A ® {1, 2, … , n2}. Это отображение биективно: 1) f всюду определено на A по построению. 2) f инъективно: если f(i, j) = f(k, l), то n·(i – 1) + j = n·(k – 1) + l, т.е. n·(i – k) = l – j, n | (l – j), что возможно только в случае l = j, т.к. 1 £ 3) f сюръективно. Действительно, любое число m Î {1, 2, … , n2} можно разделить с остатком на n, записав m = n·q + r, где 0 £ r £ n–1. Если r ¹ 0, то f(q+1, r) = n·q+r = m, т.е. m является образом пары (q + 1; r). Если r = 0, то f(q, n) = n·(q–1) + n = n·q = m, и m – образ пары (q; n). Следовательно, во множестве А столько пар, сколько чисел во множестве {1, 2, … , n2}, т.е. n2. Конечно, это можно доказать и проще, но в приведённом рассуждении работает полезная нумерация пар. Для n = 3, например, получаются следующие номера пар: f(1, 1) = 1, f(1, 2) = 2, f(1, 3) = 3, f(2, 1) = 4, f(2, 2) = 5, f(2, 3) = 6, f(3, 1) = 7, f(3, 2) = 8, f(3, 3) = 9. Эту нумерацию можно использовать в разнообразных нетривиальных задачах.
Не нашли, что искали? Воспользуйтесь поиском по сайту: ©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.
|
Принцип умножения: если проводится испытание с x исходами, после которого независимо от исходов первого испытания проводится испытание с y исходами, то общее количество возможных исходов после двух испытаний будет x×y. Этот принцип можно сформулировать наглядно: если из города А в город B ведут x дорог, а из города B в город C ведут y дорог, то из города A в город C можно проехать x×y способами.
£ n ?
£ n. Далее, при l = j получается и i = k, т.е. равенство f(i, j) = f(k, l) возможно лишь в случае i = k, l = j.