Читать онлайн «Элементы комбинаторики: Пособие для студентов заочного отделения»

НИЖЕГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. Н. И. ЛОБАЧЕВСКОГО Факультет вычислительной математики и кибернетики Кафедра математической логики и высшей алгебры ЭЛЕМЕНТЫ КОМБИНАТОРИКИ (Пособие для студентов заочного отделения) Составители: В. Е. Алексеев, В. В. Лозин 1998  2 Комбинаторика (комбинаторный анализ) – раздел дискретной математики, в котором изучаются объекты, составленные из элементов конечных множеств. Одним из основных видов комбинаторных задач являются перечислительные задачи. В этих задачах речь идет о выборе определенного количества элементов из некоторого множества с соблюдением тех или иных условий и требуется подсчитать число способов, которыми можно осуществить такой выбор. Напомним некоторые обозначения из теории множеств. 2 A – множество всех подмножеств множества A. A – число элементов (мощность) конечного множества A. A1 × A2 ×K× An – прямое (декартово) произведение множеств A1 , A2 ,K , An . Элементами декартова произведения являются последовательности вида ( x1 , x2 ,K, xn ) , где x1 ∈ A1 , x2 ∈ A2 ,K , x n ∈ An . При A1 = A2 =K = An = A получается декартова степень A n множества A. Если элементы множества A считать буквами алфавита, то элементы декартовой степени можно рассматривать как слова, они в этом случае записываются в виде x1 x 2 K x n . Буквой E будем обозначать двухэлементное множество {0,1} . Символом отмечается конец доказательства. 1. Правила равенства, суммы и произведения Очень многие комбинаторные задачи решаются применением трех простых правил, названных в заголовке. Пусть A и B - конечные множества, f - функция, определенная на A со значениями в B. Напомним, что f называется биекцией или взаимно однозначным отображением, если выполняются условия 1) любые два различных элемента из A отображаются в различные элементы множества B (функция, удовлетворяющая этому условию, называется инъекцией); 2) для любого y∈B существует такой x ∈ A ,что f ( x ) = y (такая функция называется сюръекцией). Если существует биекция из A в B , то говорят также, что между A и B имеется взаимно однозначное соответствие. Правило равенства. Если между конечными множествами A и B есть взаимно однозначное соответствие, то A = B . Правило суммы. Если A и B – конечные множества и A I B = ∅ , то AU B = A + B . Правило произведения. Для любых конечных множеств A и B имеет место равенство A × B = A ⋅ B . Первые два правила очевидны, третье следует из того, что при B = b каждый элемент множества A образует b пар с различными элементами множества B, поэтому, если A = a , то всего будет ab пар. Правила суммы и произведения обобщаются на случай любого числа слагаемых или сомножителей. Для правила суммы обобщение очевидно: мощность объединения любого числа попарно непересекающихся множеств равна сумме их мощностей.