Число всех подмн-в n -элементного множества
|B(S)| = 2ⁿ
Док-во
Даны А и В, причем число элементов А задано и сущ-т биекция φ: A->B, тогда |B| = |A|
АсS, A-> = (x₁ x₂ … xn), xi= 1, если принадлежит и 0, если иначе. Φ – мн-во всех бинарных посл-тей длины 2. Т.к. отображение φ – биективно{0;1} => = 2ⁿ.
3 Число r -сочетаний из n элементов. Биномиальнаятеорема и следствия из нее. Основны e свойства биномиальных коэффициентов. Треугольник Паскаля.
Сочетания без повторений — комбинаторные соединения из n элементов по m, составленные из этих элементов и отличающиеся друг от друга только составом.:
= n!/r!(n-r)!
Док-во
Каждомуr – сочетанию из n – элементногомн-ва соответствует r! Перестановок элементов этого сочетания. Т.о. = r! => = n!/r!(n-r)!
Основныесв-ва биномиальных коэффициентов
=
2 = +
3 <
Биномиальная теорема
следствия
Док-во
= (x+y) * … * (x+y) (n- раз)
Для того, чтобы найти указ произведнеобход из каждой скобки выбрать по одному слагаемому, перемножить их и сложить всевозможные комбинации. Получ в результате произвед будет равно числу способов выбора из nскобок в точности kскобок, из кот при умножении и берется y. Из всех оставшихся скобок автоматически выбираются x.
Треугольник Паскаля основывается на следующем рекуррентном соотношении:
| 4 Число (r 1,..., rk) -разбиений конечного множества. Другая комбинаторная интерпретация этого числа. Полиномиальная теорема.
P(r₁ … rn) = n! / r₁! … rn!
Док-во
R₁ - элементное подмн-во S₁ можно выбрать из n – элементного мн-ва . Для каждого из таких способов S-S₁ можно выбрать ю Делая такую выбоку для r – подмн-в мы получим: … = n!/r₁!(n-r₁)! * (n-r₁)!/r₂!(n-r₁-r₂)! * … *(n-r₁ - … - )!/ !(n-r₁ -…- )
Другая комбинаторная интерпретация этого числа
Число перестановок n-элементного мн-ва, среди кот имеется в точности эл-тов 1ого тип и тд равно P(r₁ … rn) = n! / r₁! … rn!
Док-во
Сведем к задаче о упорялоч разбиениях. Зафикснек перестановку эл-товданногомн-ва. ПустьS={1 … n} - мн-во номеров позиций, на кот стояли эл-ты мн-ва.Обозначим через - мн-во тех номеров позиций, но кот в нашей перестновке стояли эл-ты i-того типа. Т.о. опрупоряд разбиение (). Между всеми перестановками заданного n- элементного мн-ва и всеми разбиениями мн-ваSимеется биективное соответствие
Полиномиальная теорема
Док-во
() …
Из каждой скобки мы выбираем либо , перемножаем выбранные элементы и складываем все полученные таким образом произведения. Пусть S={1…n} – мн-во номеров скобок. Обозначим –мн-во номеров тех скобок, из которых при получении произведения берется . Мы получили такое разбиение, что каждому слагаемому вида ставится в соответствие ()разбиение мн-ваS. В свою очередь между всеми произведениями вида (с учетом их получения и ()разбиение мн-ваS) уст биективное соответствие. Т.о., после приведения подобных слагаемых, мы получаем, что коэффициентом явл число
| 1 Предмет комбинатор. Логич правила комбинаторики
Комбинато́рика— раздел дискретной математики. Элементы комбинаторики - дискретные объекты, множества (сочетания, перестановки, размещения и пересечения элементов) и отношения на них (например, частичного порядка).
Основные (логические) правила.
В комбинаторном анализе есть два основных логических правила - правило суммы и правило произведения. Рассмотрим более подробно, что из себя представляет каждое из этих правил.
а) Правило суммы: Если дано два конечных множества A и B, - мощность множества , то при или
если некоторый выбор A можно осуществить m способами, а выбор B, отличный от A – n способами, то выбор вида «либо A, либо B» осуществить m+n – способами.
б) Правило произведения: Если A и B – конечные множества и , то .
| | 7 Метод «вкл и искл»(обладающих в точности t св-вами)
n(t) = - + … + +…+ (1)
Док-во
Возьмем элемент a S, который обладает не меньше, чем tсв-вами, тогда в правой части рав-ва (1) он учитывается ноль раз. Пусть элемент а обладает в точности tсв-вами , r=t, тогда в правой части рав-ва (1) элемент а учитывается один раз. Пусть элемент а обладает больше, чем tсв-вами , r>t,тогда в правой части рав-ва (1) он учитывается раз в первом слагаемом, во втором и тд по аналогии: а = + … + . Далее рассмотрим слагаемое = s!/t!(s-t)!*r!/s!(r-s)! = r!/t!(s-t)!(r-s)! = [домножим и разделим на (r-t)!] = r!/t!(r-t)!*(r-t)!/(r-s)!(s-t)! = . Мы получили, что = , т.е. а = + … + = ( + … + ) = т.е. элемент, который обладает более, чем tсв-вами не учитывается в правой части (1), т.е эта формула справедлива для элементов, обладающих в точности tсв-вами
| 14 Число Стирлинга 1ого рода
C(n,k)=C(n-1,k-1)+(n-1)C(n-1,k),
C(n,k)=0, еслиn=0 или k=0, за искл С(0,0)=1
Док-во
Для n =1 это равенство проверяется непосредственно.
Пусть перестановка (n -1)-го порядка распадается на k циклов. Число n можно добавить после любого числа в соответствующий цикл. Все полученные перестановки — различные и содержат k циклов, их количество (n -1)· s (n -1, k). Из любой перестановки (n -1)-го порядка, содержащей k -1 цикл, можно сформировать единственную перестановку n порядка, содержащую k циклов, добавив цикл образованный единственным числом n. Очевидно, что эта конструкция описывает все перестановки n -го порядка, содержащие k циклов. Тем самым равенство доказано.
| 5
Число сочетаний с повторениями
Сочетания с повторениями — комбинаторные соединения из n элементов по m, составленные из этих элементов без учета порядка с возможностью многократного повторения предметов.:
Док-во
Строим k-сочетания с повторениями из элементногомн-ваS={ }.В каждом таком наборе сначала расположим элементы типа , затем типа ,и так далее. Каждому k-сочетанию с повторениями поставим в соответствие последовательность из 0 и 1 длины n+k-1, число единиц в этой последовательности равно k, число нулей n-1. Каждый 0 отделяет наборы различных типов. Каждое k-сочетание с повторениями однозначно определяет указанную последовательность и наоборот. Т.к. количество упорядоченных наборов из 0 и 1 длины n, состоящих из k единиц равно , тотаких последовательностей существует . Значит, =
| 6
Метод «вкл и искл» (не обладающих св-вами)
n(0) = n – + - … - + … +
Док-во
Элемент мн-ваS,кот не обладает ни одним из св-в () в левой части рав-ва учитывается 1 раз, в правой части рав-ва так же один раз, а именно в первом слагаемом. Пусть теперь a S – элемент, который обладает св-вами, тогда 1-r + - + … + +.. +
| |
8
Примен. метода вкл. и искл. (задача о бесп., задача о числе сюръект. отобр.)
Задача о беспорядках
Требуется найти число перестановок множества таких что для всех i. Такие перестановки называются беспорядками.
Пусть — множество всех перестановок и пусть свойство перестановки выражается равенством . Тогда число беспорядков есть . Легко видеть, что — число перестановок, оставляющих на месте элементы , и таким образом сумма содержит одинаковых слагаемых. Формула включений-исключений дает выражение для числа беспорядков:
Это соотношение можно преобразовать к виду
Нетрудно видеть, что выражение в скобках является частичной суммой ряда . Таким образом, с хорошей точностью число беспорядков составляет долю от общего числа перестановок:
Число сюръективных отображений конечного
множества X; |X|= n, на конечное множество Y; |Y | = m, то
есть число функций f:XàY, таких, что f (X) = Y,
равно cогласно принципу включения-исключения:
f(n,m) = + ^n = + ^n
15.
Упорядоченные и неупорядоченные разбиения множеств. Число Стирлинга 2-го рода. Формула и рекуррентное соотношение для числа Стирлинга 2-го рода.
число Стирлинга второго рода представляет собой количество неупорядоченных разбиений n -элементного множества на m частей, в то время какмультиномиальный коэффициент выражает количество упорядоченных разбиений n -элементного множества на m частей фиксированного размера . Количество всех неупорядоченных разбиений n -элементного множества задается числом Белла .
Числом Стирлинга второго рода из n по k, обозначаемым или , называется количество неупорядоченных разбиений n -элементного множества на k непустых подмножеств.
Числа Стирлинга второго рода удовлетворяют рекуррентному соотношению:
, для n ≥ 0,
, для n > 0,
для
| 9
Понятие рекуррентного соотношения. Рекуррентное соотношение k -го порядка дляфункции одной переменной, его общее решение.
Рекуррентно e соотношени e - соотношение между элементами последовательности, в которой следующий элемент выражается через несколько предыдущий.
Рекурентная формула — формула вида , выражающая каждый член последовательности через p предыдущих членов. Например - числа Фибоначчи
Линейным рекуррентным соотношением k - го порядка(k - фиксировано) с постоянными коэффициентами называется рекуррентное соотношение следующего вида:
(3)
- постоянные .
Характеристическим уравнением рекуррентного соотношения (3) является уравнение вида
Теорема 2: Пусть - все попарно различные корни характеристического уравнения рекурретного соотношения (3) - кратность корня . Тогда общее решение рекуррентного соотношения (3) имеет следующий вид:
.
В частности, если , то
12
Общее решение линейного неоднородного рекуррентного соотношения с постоянными коэффициентами
Общее решение неоднородного рекурентного соотношения есть сумма общего решения однородного соотношения и какого-либо решения из неоднородных рекурентных соотношений.
Док-во
Пусть ()-нек решение неоднордного соотнош, а ()-общее решоднороднсоотнош. Необход док-ть, что () = -общее решнеоднорднсоотнош. Мы доказали, что явл решение неоднородн соотнош. Теперь необход показать, что оно явл общим. Для этого необход док-ть, что решения неоднород соотнош сущ-т , что посл-сть ()уд неоднородсоотнош. Для этого запишем
Вычитаем одно из 2ого и получаем:
Т.о. получаем, что () – общее реш однородного соотнош, т.к. сущ-т общее реш неоднород соотнош , то по опр сущ-т такое, что , т.е. вып-тся =>
| 10
Общее решение линейного однородного рекуррентного соотношения с постоянными коэффициентами.
Пусть характеристическое ур-ние рекуррентного соотношения имеет р парно различных корней: крастностей соответственно , тогда посл-сть ()явл общим решением, где = , где - мн-н степени не выше i, завис от n
Док-во
Поскольку явл корнем характеристического ур-ния рекур соотнош, значит каждая посл-ть () явл решение рекурсоотнош. Докажем теор для случая када кратность корней равна 1. Тогда рав-во можно переписать виде: , p=k. Следвательнолин комбинация()так же явл решением рекурсоотнош. Др словами, посл-сть () с мн-ном – решение рекур соотнош
Необход д-ть, что эти решения будут общими,т.е. необход, чтобы сущ-ли , такие, что . Рассмотрим
при n=0: ,
при n=1:
…
при n=k-1: =
Получ система ур-ний из kур-ний с неизвестными , относ кот нужно выяснить имеет ли реш данная система. Опр данной системы будет явл
=
Т.о. мы получили, что ранг матрицы данной системы равен рангу рассмотр матрицы, значит даннай система совместима, а это означ, что сущ-т решение
13
Разбиение подстановки на циклы. Число подстановок n -элементного множества, имеющих предписанных циклический тип.
Циклом длины lназ. такая подстановка а конечного множества Y={y1,..., у l ], что ш
Конечный цикл обозначается (y1, y2,..., yl). Бесконечным циклом наз. такая П. счетного множества
что для любого целого i s(yi)= yi+1 Обозначение бесконечного цикла таково:
Цикл длины 2 есть транспозиция. Группа Sn содержит (п- 1)! циклов длины п. Для любой подстановки g из S(X).существует такое разбиение множества X на непересекающиеся подмножества, что на каждом из них g действует как цикл. Конечные подмножества этого разбиения имеют вид
где g l (x}=x, а бесконечные -
| 11
Числа Фибоначчи. Вывод формулы n-го числа Фибоначчи решением линейного
однородного рекуррентного соотношения 2-го порядка.
Линейным однородным рекуррентным соотношением второго порядка с постоянными коэффициентами называется рекуррентное соотношение вида:
(2)
- нейкие коэффициенты, причем отлично от нуля. Уравнение вида
- характеристическое уравнение рекуррентного соотношения (2).
Теорема 1: Если характеристическое уравнение рекуррентного соотношения (2) имеет два различных корня , то общее решение рекуррентного соотношения (2) имеет вид
Если рекуррентное соотношение имеет два равных корня , то общее решение рекуррентного соотношения (2) имеет следующий вид
последовательность чисел Фибоначчи задается линейным рекуррентным соотношением:
14 Число Стирлинга 1ого рода
Числа Стирлинга первого рода (без знака) — количество перестановок порядка n с k циклами.
Числами Стирлинга первого рода (со знаком) s(n, k) называются коэффициенты многочлена:
где — символ Похгаммера (убывающий факториал):
Как видно из определения, числа имеют чередующийся знак. Их абсолютные значения задают количество перестановок множества, состоящего из n элементов с k циклами.
Числа Стирлинга первого рода задаются рекуррентным соотношением:
, для n ≥ 0,
, для n > 0,
для
Док-во
Для n =1 это равенство проверяется непосредственно. Пусть перестановка (n -1)-го порядка распадается на k циклов. Число n можно добавить после любого числа в соответствующий цикл. Все полученные перестановки различны и содержат k циклов, их количество (n -1)· s (n -1, k). Из любой перестановки (n -1)-го порядка, содержащей k -1 цикл, можно сформировать единственную перестановку n порядка, содержащую k циклов, добавив цикл образованный единственным числом n. Очевидно, что эта конструкция описывает все перестановки n -го порядка, содержащие k циклов. Тем самым равенство доказано.
| |
28 Полиномиальная нормальная форма. Полином Жегалкина. Теорема о единственности представления булевой функции посредством полинома Жегалкина
Под полиномом булевой функции понимаем сложение по модулю два конечного множества элементарных конъюнкций. Степенью полинома является наибольший ранг элементарной конъюнкции, входящей в этот полином.
Полином, содержащий все переменные без знака отрицания, называется полиномом Жегалкина.
Для каждой булевой функции существует единственный полином Жегалкина, реализующий эту функцию.
={0;1}, -двоичное представление числа k, 7
Теор о ед-сти представ бул ф-циипоср-ом п.Жегалкина
Для любой булевой ф-циисущ-т в точности один полином Жегалкина.
Док-во
f=f(), a(f)=(). Каждый полином Жегалкина однозначно определяется вектором (). Векторов () будет сущ-ть в точности , а это число всех булевых функций от n переменных, т.е каждой функции соответствует свой полином Жегалкина
| 29
Замкнутые классы булевых ф-ций
Замкнутый класс в теории булевых функций — такое множество функций алгебры логики, замыкание которого относительно операции суперпозиции совпадает с ним самим: . Другими словами, любая функция, которую можно выразить формулой с использованием функций множества , снова входит в это же множество.
1. Класс - сохрconst 0 – явлзамкнутым
Док-во
Пусть ф-цииg=g() и =f() . Пусть h-суперпозиция. Рассмотрим h=h(0, … 0) = g() = g(0, … 0) = 0
2. Класс - сохрconst 1 – явлзамкнутым
Док-воаналогичное
3. Класс –самодвойственная ф-ция – явл замкнутым
Док-во
Пусть ф-цииg=g() и =f() . Пусть h-суперпозиция. Рассмотрим h() = g() = g() = () = ()
4. Класс –монотонная ф-ция – явл замкнутым
Док-во
= ()и = () {0,1}. Пусть ф-цииg=g() и =f() . Пусть h-суперпозиция. Скажем, что . h() = g() g() = h()
5. Класс –линейная ф-ция – явл замкнутым
Док-во
Т.к. суперпозиция полинома Жегалкина степени не выше 1 так же явл полиномом степени не выше 1.
| 30 Полнота системы булевых функций. Теорема Поста (без доказательства).
Множество функций алгебры логики называется полной системой, если замыкание этого множества совпадает с множеством всех функций. (В частности, для двузначной логики .) Другими словами, должна быть возможность любую функцию алгебры логики выразить формулой с использованием функций множества .
Теорема Поста
Система булевых функций F является полной тогда и только тогда, когда она не содержится ни в одном из классов , т.е. когда в ней имеется хотя бы одна функция, не сохраняющая 0, хотя бы одна функция, не сохраняющая 1, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция
| 27
Алгоритм Квайна нахождения минимальной ДНФ булевой функции.
(теорема Квайна). Если в СДНФ в начале произвести все операции неполного склеивания, а затем все операции поглощения, то в результате получится сокращенная ДНФ.
Покажем, что, применяя операцию неполного склеивания, получим все простые импликанты функции. Введем операцию развертывания, которая обратна операции склеивания: это есть умножение каждого произведения на выражение вида .
Пусть – простая импликанта некоторой трех переменных. Тогда:
получатся после многократного применения этой операции дизъюнкции конституент единицы исходной функции, т.е. ее СДНФ.
| |
16
Число Белла. Рекуррентное соотношение для числа Белла.
числом Белла называется число всех неупорядоченных разбиений n -элементного множества, при этом по определению полагают .
Числа Белла можно задать в рекуррентном виде:
.
Число Белла можно вычислить как сумму чисел Стирлинга второго рода:
20
Теорема Рамсея.
Пусть , и — натуральные числа, причем . Тогда существует число , обладающее следующим свойством: если все -элементные подмножества -элементного множества произвольным образом разбиты на два непересекающихся семейства и , то либо существует -элементное подмножество множества , все -элементные подмножества которого содержатся в , либо существует -элементное подмножество, все -элементные подмножества которого содержатся в .
| 17
Упорядоченные и неупорядоченные разбиения чисел. Рекуррентные соотношения для количества неупорядоченных разбиений натурального числа на фиксированное число слагаемых.
Разбие́ние числа́ n — это представление n в виде суммы положительных целых чисел, называемых частями. При этом порядок следования частей не учитывается (в отличие откомпозиций), то есть разбиения, отличающиеся только порядком частей, считаются равными. В канонической записи разбиения части перечисляются в невозрастающем порядке.
Количество разбиений числа n на слагаемые, используя числа не превышающие k:
Количество разбиений натурального числа n на k слагаемых:
21
Булевы функции. Способы их задания. Число бул. Ф-ий от n переменных.
Логической (булевой) функцией (или просто функцией) n переменных y = f(x 1, x 2, …, xn) называется такая функция, у которой все переменные и сама функция могут принимать только два значения: 0 и 1.
Кол-во бул.ф-ий 2^(2^ n)
1. Табличный
| 18
Система различных представителей. Теорема Холла (без доказательства).
Система различных представителей для семейтсва конечных множеств S = {A1, A2,..,Ai,…,Am} есть система попарно различных элементов {a1, a2,…, ai,…, am}, для которых ai ∈Ai [i=1,2…m].
Теорема Холла:
Пусть задано мн-во S, задан набор (необязательно различных) подмн-в из ST=(). Тогда для Т сущ-т система различных представителей такая, что и подмн-ва { } [m] вып-тся условие: | | k
22
Док-во
1. Необходимость очевидна. Пусть для (1) сущ-т система общих представителей, мн-во сод-т kэл-товмн-ва С. Учитывая вкл эл-тов долно быть больше, чем k?!
2. Достаточность. S’={ }. Рассмотрим набор Тподмн-вамн-ваS’. T=(), где ={ }. Если взять i=1, то получается, что … при i=m: . РокажемЮч то для Т сущ-т система различных представителей (теор Холла) подмн-ва { } [m] вып-тся условие: | | k. Преположим, что это не выполняется, тогда должно сущ-тьnи такое подмн-во { }, что | k, т.е. н-во ={ }?! Покажем, что мн-во c а не сод-т , значит для набора Т сущ-т система различных представителей. Выберем в c аналогично и для c . Получим С={ … }, т.е. систему различных представителей
23
Число всех подмн-в n -элементного множества
|B(S)| = 2ⁿ
Док-во
Даны А и В, причем число элементов А задано и сущ-т биекция φ: A->B, тогда |B| = |A|
АсS, A-> = (x₁ x₂ … xn), xi= 1, если принадлежит и 0, если иначе. Φ – мн-во всех бинарных посл-тей длины 2. Т.к. отображение φ – биективно{0;1} => = 2ⁿ.
| 3 Число r -сочетаний из n элементов. Биномиальнаятеорема и следствия из нее. Основны e свойства биномиальных коэффициентов. Треугольник Паскаля.
Сочетания без повторений — комбинаторные соединения из n элементов по m, составленные из этих элементов и отличающиеся друг от друга только составом.:
= n!/r!(n-r)!
Док-во
Каждомуr – сочетанию из n – элементногомн-ва соответствует r! Перестановок элементов этого сочетания. Т.о. = r! => = n!/r!(n-r)!
Основныесв-ва биномиальных коэффициентов
=
2 = +
3 <
Биномиальная теорема
|
|
|