Литература 22 3 основные операции со множествами 4 Основные операции со множествами Определение
 Скачать 154.25 Kb.
|
|
C 0 ; (2) |C 1 | = C k −1 n −1 , так как любое множество из C 1 получается из некоторого под- множества Y ′ ⊆ X \ {a} мощности k − 1 присоединением элемента a. Тогда по правилу суммы имеем: C k n = C k −1 n −1 + C k n −1 Определение. Пусть n ∈ N ∪ {0}. Число способов образования произведений из n + 1 упорядоченных сомножителей относительно неассоциативного умножения называется числом Каталана и обозначается q n . Пример. Пусть n = 2. Тогда существует ровно два способа образовать произ- ведения элементов a 0 , a 1 , a 2 : (a 0 · a 1 ) · a 2 и a 0 · (a 1 · a 2 ). Следовательно q 2 = 2. Замечание. Если a 0 , a 1 , . . . , a n — сомножители, то q n равно числу способов рас- ставить скобки так, чтобы на каждом шаге вычислялось произведение двух эле- ментов. Теорема 2.2 (О рекуррентном соотношении для числа Каталана). 1. q 0 = 1; 2. q n = n −1 ∑ i=0 q i · q n −i−1 . Доказательство. 1. q 0 = 1 следует из определения числа Каталана. 2. Разобьем всевозможные расстановки скобок на n классов в зависимости от по- ложения двух пар внешних скобок. Если первая пара скобок содержит i + 1 мно- жителей, то после расстановки двух пар внешних скобок, получится произведение (a 0 , a 1 , . . . , a i ) · (a i+1 , . . . , a n ), i = 0, . . . , n − 1. Внутри первой пары скобок существует ровно q i способов расставить скобки, в внутри второй пары — ровно q n −i−1 способов. Тогда общее число способов расставить скобки в этом случае по правилу произве- дения равно q i · q n −i−1 . Итоговое рекуррентное выражение получается применением правила суммы. Определение. Пусть X — множество мощности n, и пусть k > 0. Число неупорядоченных разбиений множества X на k подмножеств называется числом Стирлинга второго рода и обозначается S k n . Положим S 0 0 = 1. 2. ОСНОВНЫЕ КОМБИНАТОРНЫЕ ЧИСЛА И ИХ РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ 9 Пример. Рассмотрим X = {1, 2, 3} и k = 2. Существует ровно три различных разбиения множества X на два подмножества: {{1}, {2, 3}}, {{2}, {1, 3}}, {{3}, {1, 2}}. Следовательно S 2 3 = 3. Теорема 2.3 (О рекуррентном соотношении для числа Стирлинга второго рода). 1. S 0 0 = 1, S 1 0 = 0; 2. S k n = S k −1 n −1 + k · S k n −1 . Доказательство. 1. Заметим, что S k n = 0 при k > n, так как не существует разбиений множества из n элементов на k > n непустых подмножеств. В частности S 1 0 = 0. 2. Пусть X — множество мощности n > 0. Зафиксируем некоторый элемент a ∈ X. Чтобы получить разбиение множества X на k подмножеств, можно разбить множе- ство X \ {a} на k подмножеств и поместить элемент a ∈ X в любой из них k · S k n −1 способами или образовать отдельное одноэлементное подмножество разбиения {a} и разбить X \ {a} на k − 1 подмножество S k −1 n −1 способами. Отсюда по правилу суммы S k n = S k −1 n −1 + k · S k n −1 Следствие 2.1 (О числах S 2 n ). S 2 n = 2 n −1 − 1 при n > 2. Доказательство. Отметим, что по рекуррентному соотношению для числа Стир- линга второго рода для k = 2 имеем: S 2 n = S 1 n −1 + 2 · S 2 n −1 . Также отметим, что S 1 n = 1 при n > 1, так как существует только одно разбиение множества из n элементов на одно подмножество. Докажем исходное утверждение индукцией по числу элементов n в множестве. База индукции: пусть n = 2. Тогда S 2 2 = S 1 1 + 2 · S 2 1 = 1 = 2 2 −1 − 1. Предположение индукции: пусть утверждение верно при любом k < n. Шаг индукции: S 2 n = S 1 n −1 + 2 · S 2 n −1 = 1 + 2 · (2 n −2 − 1) = 2 n −1 − 1. Определение. Пусть n > 0. Число всех неупорядоченных разбиений множе- ства мощности n называется числом Белла и обозначается B n . Т.о. B n = n ∑ k=0 S k n и B 0 = 1. Теорема 2.4 (О рекуррентном соотношении для числа Белла). Пусть n > 1. Тогда B n = n −1 ∑ k=0 C k n −1 · B n −k−1 . Доказательство. Пусть X — множество мощности n > 1. Зафиксируем неко- торый элемент a ∈ X. Пусть Y — элемент разбиения множества X, содержащий элемент a, и пусть |Y \ {a}| = k. Тогда 0 6 k 6 n − 1. Множество X \ Y можно разбить B n −k−1 способами. При этом число способов выбрать подмножество Y в множестве X равно C k n −1 , так как один элемент a заведомо 3. СВОЙСТВА КОМБИНАТОРНЫХ ЧИСЕЛ 10 лежит в множестве Y . Следовательно число способов разбить множество X так, чтобы элемент a принадлежал подмножеству мощности k + 1 равно C k n −1 · B n −k−1 Теперь утверждение теоремы следует из правила суммы. 3. Свойства комбинаторных чисел Определение. Число упорядоченных подмножеств мощности k в множестве из n элементов называется числом размещений из n по k и обозначается A k n . Теорема 3.1 (О числе размещений). A k n = n! (n − k)! = n(n − 1) . . . (n − k + 1). Доказательство. Справедливость леммы следует из правила произведения. Пусть (x 1 , x 2 , . . . , x k ) — упорядоченная последовательность. Её построение осуществ- ляется за k шагов: 1-ым шагом выбираем элемент x 1 различными n способами. Вто- рой элемент x 2 выбираем n − 1 способами, и так далее. Последний элемент x k можно выбрать n − k + 1 различными способами. Теорема 3.2 (О числе биекций). Пусть X — множество мощности n. Тогда число различных биекций f : X → X равно n!. Доказательство. Пусть x 1 , x 2 , . . . , x n — элементы множества X. Каждая биек- ция f : X → X задается соответствием: x 1 x 2 . . . x n ↕ ↕ . . . ↕ f (x 1 ) f (x 2 ) . . . f (x n ) , в котором все элементы f (x 1 ), . . . , f (x n ) различны. Тогда каждая биекция одно- значно определяется упорядоченной последовательностью (f (x 1 ), f (x 2 ), . . . , f (x n )). Всего таких различных последовательностей ровно A n n = n! штук. Замечание. Задание биекции на множестве X мощности n эквивалентно упо- рядочиванию элементов множества X. Тогда число всевозможных упорядоченных множеств мощности n равно n!. Теорема 3.3 (О числе сочетаний). C k n = n! k! · (n − k)! . Доказательство. По определению C k n равно числу подмножеств мощности k в множестве из n элементов. Каждому из этих подмножеств соответствует k! упорядо- ченных подмножеств. Следовательно , по правилу произведения число упорядочен- ных подмножеств мощности k в множестве из n элементов равно C k n · k!. С другой стороны эта величина равна A k n = n! (n −k)! . Отсюда получаем, что C k n = n! k! · (n − k)! . 3. СВОЙСТВА КОМБИНАТОРНЫХ ЧИСЕЛ 11 Теорема 3.4 (Биномиальная формула). (1 + t) n = n ∑ k=0 C k n · t k . Доказательство. Докажем индукцией по числу n. База индукции: пусть n = 1. Тогда (1 + t) 1 = C 0 1 + t · C 1 1 Предположений индукции: пусть утверждение теоремы верно для любого k < n. Шаг индукции: (1 + t) n = (1 + t) n −1 · (1 + t) = (1 + C 1 n −1 t + C 2 n −1 t 2 + . . . + C n −1 n −1 t n −1 ) · (1 + t) = = (1 + C 1 n −1 t + C 2 n −1 t 2 + . . . + C n −1 n −1 t n −1 )+ + (t + C 1 n −1 t 2 + C 2 n −1 t 2 3 + . . . + C n −1 n −1 t n ) = = 1 + t(C 1 n −1 + C 0 n −1 ) + t 2 (C 2 n −1 + C 1 n −1 ) + . . . + t n C n −1 n −1 Используя рекуррентное соотношение для числа сочетаний C k n −1 + C k −1 n −1 = C k n и равенство C n −1 n −1 = 1 = C n n , получаем требуемое в условии теоремы соотношение. Теорема 3.5 (Свойства числа сочетаний). Имеют место следующие соотношения: (1) C k n = C n −k n ; (2) n ∑ k=0 C k n = 2 n ; (3) n ∑ k=0 ( −1) k C k n = 0; (4) (свёртка Вандермонда) C k m+n = k ∑ s=0 C s m C k −s n , m > k, n > k. Доказательство. 1. Справедливость этого равенства следует из явной форму- лы для значения числа сочетаний C k n 2. Справедливость этого равенства следует из биномиальной формулы. В самом деле: 2 n = (1 + 1) n = n ∑ k=0 C k n · 1 k 3. Справедливость этого равенства также следует из биномиальной формулы ана- логично предыдущему случаю. В самом деле: 0 = (1 − 1) n = n ∑ k=0 C k n · (−1) k 4. Для доказательства этого равенства вычислим значение (1 + t) n+m двумя раз- ными способами. С одной стороны, по биномиальной формуле (1 + t) n+m = n+m ∑ k=0 C k n+m t k . 3. СВОЙСТВА КОМБИНАТОРНЫХ ЧИСЕЛ 12 С другой стороны: (1 + t) n+m = (1 + t) n · (1 + t) m = n ∑ l=0 C l n t l · m ∑ s=0 C s m t s = = (1 + C 1 n t + C 2 n t 2 + . . . + C n n t n ) · (1 + C 1 m t + C 2 m t 2 + . . . + C m m t m ) Коэффициент при слагаемом t k после раскрытия скобок равен сумме таких про- изведений вида C i n · C j m , что i + j = k. Следовательно коэффициент при t k равен k ∑ s=0 C s n · C k −s m . Сравнивая полученную величину с коэффициентом при t k в биноми- альной формуле, получаем требуемое равенство. Определение. Пусть X — множество мощности n. Пусть ν : X → N ∪ {0} и ∑ x ∈X ν(x) = k. Пара (X, ν) называется мультимножеством мощности k над множе- ством X. Значение ν(x) называется кратностью вхождения элемента x в муль- тимножество (X, ν). Пример. Пусть X = {a 1 , a 2 , a 3 }. Мультимножеством мощности 3 является, например, набор элементов {a 1 , a 1 , a 1 }, при этом ν(a 1 ) = 3, ν(a 2 ) = 0 и ν(a 3 ) = 0. Примером мультимножества мощности 6 служит набор элементов {a 1 , a 2 , a 2 , a 3 , a 3 , a 3 }, при этом ν(a 1 ) = 1, ν(a 2 ) = 2 и ν(a 3 ) = 3. Замечание. Можно рассматривать упорядоченные мультимножества, кото- рые характеризуются не только кратностью вхождения элементов множества X, но и порядком, в котором эти элементы образуют множество. Примерами различных упорядоченных мультимножеств мощности 5 над множеством {0, 1} являются наборы {0, 0, 1, 1, 1} и {0, 1, 0, 1, 1}. Эти наборы совпадают, как мультимножества, но различаются, как упорядочен- ные мультимножества. Определение. Пусть X — множество мощности n. Через C k n будем обозна- чать число различных мультимножеств мощности k над множеством X. Теорема 3.6 (О числе мультимножеств). C k n = C k n+k −1 Доказательство. Пусть X = {x 1 , x 2 , . . . , x n }. Набор из таких n чисел k 1 = ν(x 1 ), k 2 = ν(x 2 ), . . . , k n = ν(x n ), что n ∑ i=1 k i = k, однозначно задаёт мультимножество мощности k. Следовательно число C k n равно числу различных неотрицательных решений уравнения k 1 + k 2 + . . . + k n = k. |