Дискретная математика (стр. 7 )

S определяется при n=2 r’== - 6 (x10 и x10), и значит S=0, так как r’ отрицательное. N=N - S=14 – 9 =5. И действительно, это цифры 95, 86, 77, 68, 59.

Беспорядком считается ситуация, когда каждый из предметов находится не на своём месте. Имеется n мест и n предметов. При n = 1 число беспорядков равно нулю: Бесп(1) = 0. При n = 2 число беспорядков равно единице, когда два предмета меняются своими местами: Бесп(2) = 1. Беспорядки – это подмножество всех перестановок множества из n предметов. Имеется n свойств, которыми подстановки могут и обладать и не обладать: первый предмет на своём первом месте, второй предмет на своём втором месте, … , n-й предмет на своём n-м месте.

Применим формулу включений и исключений. Sj = C(n-j)! = n!/j!, так как существует C способов набрать j предметов, чтобы установить их на свои места, и (n-j)! способов расставить в подстановке остальные (n-j) предметов. N = n!, S1 = n!/1!, S2 = n!/2!, … Sn = n!/n! = 1. N0 = Бесп(n) = N – S1 + S2- … +(-1) Sn = = n! .

Имеется множество A мощности n: A = {a, a, … , a}. Сколько существует троек подмножеств (X, Y, Z) множества A, где XA, YA, ZA и XY=, XZ= и ZY=. Для каждого элемента a из множества A существует три свойства (три возможности): aX, aY и aZ. Имеется 8 типов этой принадлежности для каждого элемента множества A: aXYZ, aXYZ, aXYZ, aXYZ, aXYZ, aXYZ, aXYZ, aXYZ.

Из этих восьми типов принадлежности четыре (первый, второй, третий и пятый) пустые, так как являются пересечениями с XY, или с XZ, или с ZY, которые пусты по условию, и, значит, ни один элемент множества A попасть в них не может. Каждый из элементов множества A может попасть или в XYZ, или в XYZ, или в XYZ, или в XYZ. Так как в множестве A имеется n элементов, и для каждого из них существует 4 возможности, то существует ровно 4 троек подмножеств (X, Y, Z) множества A с вышеуказанными условиями.

Например, A={1,2}и существует 16 троек подмножеств с указанными выше условиями: (, , ), (, , {1}), (, {1}, ), ({1}, , ), (, , {2}), (, {2}, ), ({2}, , ), (, , A), (, A, ), (A, , ), ({1}, {2 }, ), ({2}, {1 }, ), ({1}, , {2}), ({2}, , {1}), (, {1}, {2}), (, {2}, {1}).

Сколько существует наборов из трёх подмножеств A (X, Y, Z) таких, что ZX= и XYZ=A. Здесь X=A/X, для Y и Z аналогично. Здесь нет таких элементов A, что aXYZ и aXYZ, так как ZX=. Кроме того, не существует таких элементов A, что aXYZ, так как XYZ=A. Каждое aA, значит каждое aA или a( XYZ) или aXYZ. Существует 5 троек подмножеств множества A (X, Y, Z) с заданными условиями.

Первая лемма Капланского: из n объектов (точек) на прямой выбираются k. Число f(n, k) таких наборов, что никакие два из выбранных k объектов не являются соседними равно C при k(n+1)/2. Пусть на прямой имеется 7 объектов (n = 7): A, B, C, D, E, F и G.

Наборы из трёх объектов (k = 3), не содержащие соседних объектов: ACE, ACF, ACG, ADF, ADG, AEG, BDF, BDG, BEG и CEG.

Доказательство индукцией по n: f(n,1) = С = n, так как существует ровно n возможностей выбрать один объект из n объектов. Это первый шаг индукции.

Пусть k>1. Разбиваем множество рассматриваемых наборов на два подмножества: Первое подмножество содержит первый объект, а второе – не содержит его. Для нашего примера с семью объектами (n = 7 и k = 3) первое подмножество – это ACE, ACF, ACG, ADF, ADG, AEG, а второе – это BDF, BDG, BEG и CEG.

Так как наборы с первым объектом не содержат второй объект (соседний с первым), то число наборов в первом подмножестве равно f(n-2,k-1). Здесь от n объектов отнимаем первый и второй, а от k объектов – первый, так как он уже есть в наборах первого подмножества.

Число наборов во втором подмножестве равно f(n-1,k). Рекурсивная формула для f(n, k) = f(n-2,k-1) + f(n-1,k). Теперь сделаем индуктивное предположение, что формула f(n, k) = C выполняется для числа объектов, меньшего n. Тогда по индуктивному предположению f(n-2,k-1) = C = C и f(n-1,k) = C. Получим из этого, что формула выполняется и для n объектов.

f(n-2,k-1) + f(n-1,k) = C + C = ((n-k)!/(k!(n-2k)!)) + ((n-k)!/((k-1)!(n-2k+1)!)) = ((n-k)!/((k-1)!(n-2k)!))*(1/k + 1/(n-2k+1)) = ((n-k)!/((k-1)!(n-2k)!))*((n-k+1)/(k(n-2k+1))) =(n-k+1)!/(k!(n-2k+1)!) = C. Лемма доказана. Это доказательство самого Капланского.

Существует и другое доказательство. Действительно: n2k+1, минимальное значение n, при котором существует ровно одно решение, это n=2k-1 (k выбранных и (k-1) не выбранных между ними). Если n>2k-1, то значит имеется t ”лишних” (t=n - 2k+1) объектов, для которых существует (k+1) позиция. Первая позиция - перед первым выбранным объектом, вторая – между первым и вторым выбранными объектами, … , последняя – после последнего выбранного объекта. x из этих t точек будет в первой позиции, x - во второй и т. д. Получили: x+x+ … +x=t и число решений равно C= C= C= C.

Теперь пусть между выбранными объектами на прямой может быть не менее m не выбранных (m>0). Минимальное значение n, при котором существует ровно одно решение, это n= k +(k-1) m (k выбранных и (k-1)*m не выбранных между ними). Если n< k +(k-1) m, то решений не существует. Если n> k +(k-1) m, то значит имеется t ”лишних” (t=n – k -(k-1) m) объектов, для которых существует (k+1) позиция. Число решений равно C= C= C= C= C = fm(n, k). Здесь k(n+m)/(m+1). Например, f2(n, k) = C.

Вторая лемма Капланского: из n объектов (точек) на окружности выбираются k. Число g (n, k) таких наборов, что никакие два из выбранных k объектов не являются последовательными (соседними) равно (n C)/(n-k) при k n/2. Например, для n = 7 и k = 3 g(7,3) = (7C)/4 = 7. Это наборы ACE, ACF, ADF, BDF, BDG, BEG и CEG. Заметим, что в этих семи наборах каждый из семи объектов присутствует ровно три раза, чего не было для объектов на прямой. Там концевые объекты (A и G) встречались больше внутренних.

Доказательство: Как и раньше, разбиваем множество наборов на два подмножества: с первым объектом и без него. В обоих случаях получаем прямые с объектами, к которым применяем первую лемму Капланского. С первым объектом имеется f(n-3,k-1) наборов, а без него - f(n-1,k) наборов. g(n, k) = f(n-1,k) + f(n-3,k-1) = C + C = ((n-k)!/(k!(n-2k)!)) + ((n-k-1)!/((k-1)!(n-2k)!)) = ((n-k-1)!/((k-1)!(n-2k)!)) (((n-k)/k)+1) = ((n-k-1)!/((k-1)!(n-2k)!)) (n/k) = ((n-k-1)!/(k!(n-2k)!)) n = ((n-k)!/(k)!(n-2k)!)) (n/(n-k)) = (n C)/(n-k).

Вторая лемма Капланского для случая, когда между выбранными объектами находится не менее m не выбранных (m > 0), тоже сводится к его первой лемме. Множество наборов разбивается теперь на (m + 1) подмножеств: первое – с первым объектом, второе - без первого объекта, но со вторым, третье – без первого и второго, но с третьим объектом, … , m-е подмножество - без первых (m-1) объектов, но с m-м объектом, (m+1)–е подмножество – без первых m объектов.

Для m = 1 рассматривались только первое и последнее подмножества. Подмножество только без первого объекта для m > 1 не может быть представлено как прямая с объектами. Ограничение на k: теперь kn/(m+1). gm(n, k) = fm(n-2m-1,k-1) + fm(n-2m-1,k-1) + fm(n-2m-1,k-1) + … + fm(n-2m-1,k-1) + fm(n-m, k) = mfm(n-2m-1,k-1) + fm(n-m, k). Например, пусть n = 7, k = 2 и m = 2. Это наборы: AD, AE, BE, BF, CF, CG и DG. Получили 7 наборов и каждый объект встречается в них 2 раза.

g2(n, k) = 2f2(n-2m-1,k-1) + f2(n-m, k) = 2f2(n-5,k-1) + f2(n-m, k). g2(7,2)= 2 fm(n-2m-1,k-1) f2(2,1) + f2(5,2)= 2C+ C= 22+3 = 7. gm(n, k) можно получить и другим способом. Если нам известно, сколько имеется наборов с первым объектом (а это fm(n-2m-1,k-1)), то из симметричности задачи (круг) столько же существует наборов с любым другим объектом (а всего их n). Отсюда в наборах имеется nfm(n-2m-1,k-1) объектов. Так как в каждом наборе присутствует k объектов, то общее число наборов (оно же gm(n, k)) равно nfm(n-2m-1,k-1)/k.

Докажем, что nfm(n-2m-1,k-1)/k = mfm(n-2m-1,k-1) + fm(n-m, k). fm(n-2m-1,k-1) = C= C. fm(n-m, k) = C= C. gm(n, k) = mC + C = m((n-km-1)!/((k-1)!(n-k-km)!)) + ((n-km)!/(k!(n-k-km)!)) = C(m+((n-km)/k)) = C(n/k) = nfm(n-2m-1,k-1)/k.

Задача Люка: сколько существует способов рассадить за круглым столом n супружеских пар, мужчины и женщины через одного, так, чтобы каждые муж и жена не сидели рядом друг с другом? При решении задачи Люка используются вторая лемма Капланского и формула включений и исключений.

Все решения задачи Люка являются подмножеством множества беспорядков. Беспорядки, как и другие подстановки, могут быть заданы и квадратной матрицей размера nn. Строки матрицы – это места, а столбцы – это предметы. Для беспорядков не занятой в матрице будет главная диагональ, так как каждый предмет не на своём месте. Например, на трёх предметах можно сделать только два беспорядка:

Здесь правая матрица соответствует подстановке - предмет 1 находится на месте предмета 3 (3!), предмет 2 – на месте предмета 1 (1!), а предмет 3 – на месте предмета 2 (2!). Левая матрица соответствует подстановке . В матрицах беспорядков главная диагональ заполнена запрещающими знаками X, положение предмета указано единицей, а его отсутствие – 0. Как в любой подстановке, в каждой строке матрицы и в каждом столбце имеется ровно одна единица.

Рассмотрим теперь задачу Люка для трёх семейных пар (n = 3). Предметы – это мужья, а места – это жёны. Рассадим сначала жён:

Место по правую руку от жены считаем «родным» для каждого мужа. Получили, что предмет 1 не может находиться ни на месте 1!, ни на месте 2!, предмет 2 не может находиться ни на месте 2!, ни на месте 3!, предмет 3 не может находиться ни на месте 3!, ни на месте 1!. На трёх предметах существует только одно решение задачи Люка:

Это же решение может быть задано матрицей:

Теперь запрещёнными являются не только главная диагональ, но ещё и n других позиций в матрице.

Для решения задачи Люка рассадим сначала n жён, что можно сделать 2*n! способами. Теперь каждый муж может занять любое место, кроме мест справа и слева от своей жены, и число размещений мужей не зависит от размещения жён. Задача сводится к задаче о размещении мужей.

Надо пересчитать подстановки такие, что элемент j < n не может стоять на местах j и (j+1), а элемент n - на местах n и 1. Обозначим через Pj свойство j-й элемент на месте j, а через P`j свойство j-й элемент на месте (j+1) при j<n и P`n свойство n-й элемент на месте 1.

Рассмотрим эти 2n свойств в следующем порядке: P1, P`1, P2, P`2, … , Pn, P`n. Надо найти подстановки, не удовлетворяющие ни одному из этих свойств. Фиксируем k не противоречивых свойств (k<n+1), то есть ни одно место не может быть занято более чем одним предметом. Тогда число подстановок, удовлетворяющих этим k свойствам равно (n – k)!, так как для оставшихся (n-k) предметов существует именно (n-k)! возможностей разместиться.

Число наборов из k не противоречивых свойств (не соседних) по второй лемме Капланского равно 2nC/(2n-k) при k<n+1 и по формуле включений и исключений решение задачи Люка имеет вид: N – S1 + S2 - … + (-1)Sn = n! – (2nC/(2n-1))*(n-1)! + (2nC/(2n-2))*(n-2)! - … + (-1)(2nC/(2n-n))*0! при n>2. Для n = 3 число решений равно 3! - (6C/5)*2! + (6C/4)*1! - (6C/3)*0! = 6 – 12 + 9 – 2 = 1.