В.А. Носов - Комбинаторика и теория графов, страница 3

имеем  подмножеств и по предположению индукции выполнено k  n − 1( n − 1)!= k  ( k !)( n − k − 1)!Таким образом, общее число k-подмножеств (по правилу суммы) равно n − 1+ k + 1 n − 1( n − 1)!( n − 1)!( n − 1)!1 1+=+ == k  ( k − 1)!( n − k)! k !( n − k − 1)! ( k − 1)!( n − k − 1)!  n − k k  nn!= k !( n − k )!  k т.е. формула (*) справедлива и для n + k.4. Число всех подмножеств n-множества. Пусть А - множество из n элементов иB(A) - булеан множества А. Нас интересует число B( A) .

Рассмотрим множество {0,1} иустановим биективное соответствие между множеством B(A) и множеством всех отображений F: A → {0,1}.Для произвольного подмножества A1 ⊆ A определим FA1 : A → {0,1}, полагая 1, е с ли a ∈ A1FA1 (a) = 0, е с ли a ∈ A1Ясно, что если A1 ≠ A2, то FA1 ≠ FA2 и любому отображению F: A → {0,1}соответствуетA1 ⊆ A , где A1 = {a a ∈ A и F(a) = 1}. Значит, нужное биективное соответствие установлено и, согласно предыдущему, имеется 2n отображений F: A → {0,1}. Отсюда,B( A) = 2 n .Следствие. Справедливо тождество11nn  n∑ k =0   = 2 k5. Мультимножества. В ряде случаев приходится рассматривать объекты, в которых элементы множества повторяются.

Известный пример - корни алгебраическогоуравнения. Определим мультимножество над множеством А как пару (A,r) множества Аи отображения r: A → N0 = {0, 1, … }, задающего кратность элементов из множества А.Мощностью мультимножества (A,r) называется число ∑a ∈A r(a) .1. Число мультимножеств мощности m над n-множеством.Пусть А = {a1, … , an}. Тогда число мультимножеств мощности m равно числу отображений r: A → N0 с условиемr(a1) + r(a2) + … + r(an) = mКаждому такому отображению r поставим в соответствие набор из элементов 0, 1 видаr = (0 r (a1 ) 10 r (a 2 ) 1 ⋅⋅ ⋅ 10 r (a n ) ) ,где 0 r ( a i ) означает 0, повторенный r(ai) раз. Набор r имеет длину m + n - 1и содержит mнулей и n - 1 единиц.

Ясно, что разным отображениям r1 : A → N0, r2 : A → N0 соответствуют разные наборы r1, r2 . Далее, произвольный набор из элементов 0, 1 длины m + n -1,содержащий n - 1единиц определяет отображение r: A → N0 с условием ∑a ∈A r(a) = m,если положить r(a1) равным числу нулей до первой единицы слева, r(a2) равным числунулей между первой и второй единицами слева и т.д. Следовательно, число интересующих отображений r: A → N0 равно числу наборов из 0, 1 длины m+ n -1, содержащих n 1 единиц.

Поскольку каждый такой набор однозначно определяется множеством номеров координат, принимающих значение единица, то интересующее нас число равно числу (n-1)-подмножеств (m+n-1)-множества, которое, согласно предыдущему, равно m + n − 1 n −1 Если нас интересует число невырожденных мультимножеств (A,r) мощности m над nмножеством А, т.е. таких, у которых r(a) > 0 для всех a ∈ A, то оно равно m − 1 n − 1Предоставляется этот факт доказать самостоятельно.Следствие.

Число одночленов x1α1 x 2α 2 ⋅⋅⋅ x αn n полной степени m из кольца многочленов K[x1, … , xn] равно12 m + n − 1 n −1 2. Число перестановок мультимножеств мощности m. Пусть дано мультимножество (A,r), где А = {a1, … , an} и r: A → N0 , причем ∑a ∈A r(a) = m. Перестановкой мультимножества (A,r) будем называть отображение F: {1, … , m} → A, такое, чтоF −1 (a) = r(a), ∀a ∈ A.Ясно, что любая перестановка F мультимножества однозначно определяется выборомr(ai) элементов из {1, … , m}, переходящих в ai . Это можно сделать числом способом,равным m   m − r(a1 )  m − r(a1 ) − ⋅ ⋅ ⋅ − r(a n −1 )m! ⋅⋅⋅ =r(a n ) r(a1 )  r(a 2 )   r(a1 ) !⋅ ⋅ ⋅r(a n ) !6. Свойства биномиальных коэффициентов и связанные с ними тождества.В комбинаторных расчетах биномиальные коэффициенты играют важную роль.Для оперирования с ними полезны следующие формулы. n k n  n − k n k n − 1 n − 1 +  - свойство сложения k  k − 1 n kn  n − 1 - свойство понижения индексовk  k − 11.

  = - свойство симметрии2.   = 3.   = n   m m  k  n  n − k  - свойство замены индексов k  m − k4.     =   Данные формулы проверяются непосредственной выкладкой. r 0 r + 1 r + n  r + n + 1+…+ =  1  n   n 5.   + ♦ Докажем индукцией по n. При n = 1 тождество верно. Пусть оно верно при n.Тогда для n + 1 имеем r  r + 1 r + n  r + n + 1  r + n + 1  r + n + 1  r + n + 2 + +…+ + + = ♦=  0  1  n   n +1   n   n +1   n +1  0 m 1 m n m n + 1 m + 16.

  +   + … +   = ♦ Запишем последовательность равенств13 n   n   n + 1 +   = m + 1  m  m + 1 n − 1  n − 1  n +  = m + 1  m   m + 1… 0   0  1  +   = m + 1  m  m + 1Теперь складываем данные равенства, получаем нужное тождество. ♦n  n max   =   n 0≤ k ≤ n  k     2 7.♦ Рассматриваем отношение n  k n  k − 1=n − k +1knnзамечаем, что оно больше 1 при k ≤   и меньше 1 при k >   .

♦228. Пусть p - простое число. Тогда p kа)   ≡ 0(mod p) при 1 ≤ k ≤ p - 1 p − 1k ≡ ( −1) (mod p) при 0 ≤ k ≤ p - 1 k б)  pp!целое, числа k! и (p - k)! взаимно просты с p, поэтому они сокра k k !( p − k)!♦ Число   =щаются с (p - 1)!. Отсюда следует а). p − 1( p − 1)!. Ясно, что справедливы соотношения= k  k !( p − 1 − k )!Рассмотрим теперь p −1 p − 2p− k≡≡ ⋅⋅⋅≡≡ − 1(mod p) , откуда следует б) при k ≥ 1. При k = 0 утверждениеk12б) очевидно. ♦9.

Пусть x - некоторое переменное из множества действительных чисел, n - натуральное число. Тогда справедливо14 n(1 + x)n = ∑nk =0   xk kПолагая x = 1 и, x = -1, получаем тождества9а. nn∑nk =0   = 2 k9б.k  n∑nk =0 ( −1)   = 0 kРассматривая очевидное тождество(1 + x)n(1 + x)m = (1 + x)n+m (n, m - натуральные числа)и подсчитывая справа и слева коэффициент при xk , 0 ≤ k ≤ n+m получим тождествоВандермонда: n  m   n + m10. ∑ik=0    = i   k − i  k Используя тождества 4, 9а, 9б легко доказываются тождества n  n  n  n − 1 n  n − p n11а.

    +    +L+   = 2p  0  p  1  p − 1 p  0  p n  n  n  n − 1 n  n − p11б.     −    + L + ( −1) p    =0 0  p  1  p − 1 p  0 12.( −1)∑ni =1ii −111 n  = 1 + +L+2n i♦ Рассмотрим тождество n(1 - x)n = ∑ni =0 ( −1) i   x i iПеренесем влево член при i = 0 и разделим обе части равенства на x.-(1 − x) n − 1 n= ∑in=1 ( −1) i   x i −1 i(1 − x) − 1Это равносильно тождеству n i- [1 + (1 - x) + (1 - x)2 + … + (1 - x)n-1] = ∑in=1 ( −1) i   x i −1проинтегрируем обе части по x и получим(1 - x) +(1 − x) 2(1 − x) n( −1) i  n i+L++ C = ∑in=1 xi  i2nПолагая x = 0, находим постоянную интегрирования С:15C = - [1 +11+L+ ]2nТеперь полагаем x = 1 и получаем нужное тождество.

♦16Упражнения.Доказать тождества ni =0  i n2 2n n1. ∑   =  1  n1(2 n +1 − 1) =k++nk11k =0n2. ∑n3. ∑ ( −1) kk =01  n1 =k + 1  k n + 1n n  n  nnπ24. 1 -   +   −   +L = 2 cos4 2  4  6n n  n  n  nnπ25.   −   +   −   +L = 2 sin4 1  3  5  717§ 3. Бинарные отношения.1. Определения.Пусть дано декартово произведение множеств A1 ×L× A n . ПодмножествоR⊆ A1 ×L× A n называется n-местным отношением на множествах A1, … An. Говорят, чтоэлементы a1, … an находятся в отношении R, если (a1, … an) ∈ R.Наиболее изучены и часто используются в приложениях двухместные или бинарныеотношения.

Иногда бинарные отношения R на A1 × A 2 называют соответствиями из A1 вA2. Для бинарных отношений наряду с записью (a1,a2) ∈ R пишут также a1Ra2 . ЕслиAi = A, ∀ i ∈ 1, n , то говорят, что задано n-местное отношение на множестве А. Далеебудут рассматриваться только бинарные отношения.Если R ⊆ A1 × A 2 - бинарное отношение, то можно определить проекции пр1Rи пр2R как подмножества A1 и A2 соответственно:nр1R = {a1 (a 1 , a 2 ) ∈ R для некоторого a2 ∈ A2 }nр2R = {a2 (a 1 , a 2 ) ∈ R для некоторого a1 ∈ A1 }Если nр1R = A1 , то говорят, что отношение R всюду определено.

Если nр2R = A2, то говорят, что отношение R сюръективно. Для задания бинарных отношения можно использовать любые способы задания множеств. Наиболее употребительные способы заданиябинарного отношения R на конечном множестве А - матричный и графический. Пустьn-множество А состоит из элементов a1, a2, … an. Тогда для бинарного отношения R на Аопределим матрицу DR = (rij), i, j ∈ 1, n , гдеrij =1, если aiRaj0, в противном случае.Матрица DR однозначно определяет бинарноеотношение R. При графическом задании отношения R строится граф с множеством вершин a1, … an на плоскости, причем от вершины ai к вершине aj проводится ориентированная дуга в том и только в том случае, если aiRaj . Построенный таким образом графоднозначно характеризует отношение R.Легко видеть, что отображения являются частным случаем бинарных отношений.