Содержание
-
ТЕОРИЯ КОНЕЧНЫХ МНОЖЕСТВ (КОМБИНАТОРИКА)
§1. Принципы сложения и умножения Комбинаторика занимается подсчетом количеств разных комбинаций, которые можно получить различными способами из тех или иных конечных множеств.
-
Если конечное множество A состоит из m элементов, то мы будем писать: |A| = m или n(A) = m. Теорема 1 (принцип сложения). ПустьA B = . Тогдаn(A B) = n(A) + n(B). Следствие 2. ПустьA1, A2….Al– система попарно непересекающихся конечных множеств. Тогдаn(A1A2 …Al) = n(A1)+n(A2)+…+n(Al).
-
Доказательство: Приl=2 ссылаемся на теорему 1: n(A1A2) = n(A1) + n(A2). Допустим, что утверждение верно при l = k, n(A1A2 …Ak) = n(A1) + n(A2) +…+ n(Ak). Докажем утверждение при l = k+1. В этом случае n(A1A2 …Ak Ak+1) = n((A1 A2 …Ak) Ak+1) = n(A1A2 …Ak) + n(Ak+1). Здесь мы воспользовались базисом индукции и, применяя индуктивное предположение, получим: n(A1 A2 … Ak) + n(Ak+1) = n(A1) +…+ n(Ak) + n(Ak+1). Следствие доказано.
-
Иногда принцип сложения можновстретить в таком виде: если объект x можно получитьm способами, а объектyможно получить l способами, причем множества этих способов не пересекаются, то объект x или объект yможно получить m + lспособами. Таким образом, необходимо помнить, что в комбинаторике союз “или”ассоциирован с операцией сложения.
-
Теорема 3 (принцип умножения). Если множество A состоит из m элементов, а множество B состоит из lэлементов, то n(A B) =ml. Доказательство:При l=1 множествоB состоит из 1 элемента:B={b1}. Поэтому мн-во A B={(ai, b1)|i =1, 2,…,m}состоит изm элементов, n(A B)=m · 1=m · l. Базис индукции проверен. Приl = k, если n(A) = m, n(B) = k, то n(A B) = m · k. Приl = k + 1. Пусть B = {b1, b2 ,…,bk ,bk+1} или B=B‘{bk+1},
-
ГдемножествоB'={b1, b2 ,…,bk}состоитиз k элементов. По индуктивному предположению n(A B') = n(A) · n(B') = m · k. С другой стороны B=B‘{bk+1}, поэтому (A B) =A B' A … {bk+1}, причем A B'A {bk+1} =, так как B'{bk+1} =. По теореме 1 n(A B) = n(A B' A {bk+1}) = n(A B') + n(A {bk+1})=m · k + m · 1 = m(k + 1) = m · l.
-
В комбинаторном изложении принцип умножения часто формулируют так: если объект xможно сконструировать m способами, объект y можно сконструировать l способами, то объект(x,y)или (x иy) можно сконструировать m · l способами. То есть союз “и” в комбинаторики ассоциирован с операцией умножения.
-
Теорема 4. Если множестваA1, A2,…,Akконечны, то n(A1 A2 ,…,Ak )=n(A1) · n(A2)·,…, ·n(Ak ).
-
Задача . Пусть A и B конечные мн-ва, B A. Сколько элементов содержит множества A\B.
Решение. Докажем, что в случае, когда B A, n(A\B) = n(A) – n(B). В самом деле, запишем очевидноетеоретико-множественное равенство (A\B)B = A, причем (A\B) B =. Применим к множествам A\B и B принцип сложения. n((A\B)B)=n(A\B) + n(B) илиn(A)=n(A\B)+n(B) Отсюда получаем требуемое равенство n(A\B) = n(A) – n(B).
-
Задача . Из цифрA={0,1,2,3,5,6,7} составить все четырехзначные числа, не содержащие повторяющихся цифр и делящиеся на 3.
Решение. Воспользуемся признаком делимости на три: число делится на три в том и только в том случае, когда сумма цифр этого числа делится на три. Поэтому надо перебрать всевозможные четверки цифр, сумма которых делится на три. Перечислим такие четверки:
-
A1 = {0, 1, 2, 3}, A2 = {0, 1, 2, 6}, A3 = {0, 1, 3, 5}, A4 = {0, 1, 5, 6}, A5 = {0, 2, 3, 7}, A6 = {0, 3, 5, 7}, A7 = {0, 5, 6, 7}, A8 = {1, 2, 3, 6}, A9 = {1, 3, 5, 6}, A10 = {1, 2, 5, 7}, A11 = {2, 2, 6, 7}, A12 = {3, 5, 6, 7}. Обозначим через B множество всех искомых чисел, а через Bi (i = 1, 2,…, 12) множества чисел, полученные из цифр множества Ai соответственно. Так как приij Bi Bj = , то по принципу сложения n(B) =. По принципу произведения n(B1)=3·3·2·1=18.
-
Аналогично n(B2)=n(B3)=n(B4)=n(B5)=n(B6)=n(B7)=18 Попринципу произведенияn(B8)=4·3·2·1=24. Аналогично, n(B9)=n(B10)=n(B11)=n(B12)=24. Наконец, n(B)=18·7+24·5=246
-
§2. Размещения и перестановки
Определение 1. Пусть дано конечное множествоA, n(A)=nи 1 ≤ k ≤ n.k-размещением множестваAназывается любой упорядоченный набор длины k(), где все координаты - попарно различные элементы множества A. Число всехk-размещенийn-элементного множества обозначается через .
-
Пример. ПустьA=a,b,c,d. Выпишем все 2-размещения этого четырёхэлементного множества: (a;b), (b;a), (a;c), (c;a), (a;d), (d;a), (b;c), (c;b), (b;d), (d;b), (c;d), (d;c). Таким образом
-
Теорема 2. Пустьn N, 1≤k≤ n. Тогда.
Доказательство. Применим индукциюпоk. Докажем равенство при k=1. 1-размещения это наборысостоящие из одногоэлемента,взятого изn-элементного множества. Очевидно, что их будет столько же, сколько элементов, в n-элементном множестве,то есть .
-
C другой стороны , то есть
-
Допустим, равенство выполняется дляk
-
-
Пример. В первенстве страны участвуют 12 команд. Сколькими способами они смогут занять призовые места.
Решение. Поскольку является существенным тот факт, какая команда займет первое место, какая – второе, какая - третье, то задача сводится к вопросу: сколькими способами можно выбрать трёхэлементный упорядоченный набор из 12-элементного множества.Таких способов будетспособов.
-
Замечание 3. Приk>nневозможно построитьk-размещение, поэтому при k>n. Замечание 4. Приk=0под 0-размещением мы будем понимать пустое множество. Так как пустое множество единственно, то чтосогласуется с формулой, так как приk=0имеем
-
Определение 5. Пусть конечное множество Aсостоит изnэлементов.k -размещением с повторениями множества Aназывается упорядоченный набор длины k, элементы которого берутся из A. Элементы вk-размещении с повторениями не обязаны быть различными. Пример. ПустьA={1,2,3}.Выпишем все 2-размещения с повторениями множества A: (1;1),(1;2),(1;3),(2;1),(2;2),(2;3), (3;1),(3;2),(3;3). Числоk-размещений с повторениями n-элементного множества обозначается
-
Теорема 6.
Доказательство. Применим индукцию поk. Приk=1число1-размещений равно числу элементов множестваA, то есть Сдругой стороны,n1=n. Базис индукции доказан. Допустим, формула верна приk=l, то есть
-
Докажем утверждение приk= l +1. Из каждого упорядоченногоl-элементного набора можнополучить n упорядоченных наборов длиныl+1, приписывая любой элементAсправа, тоесть (l +1)-размещений с повторениями вn раз больше,чем l-размещений с повторениями, тоесть Теорема доказана.
-
Пример. Номер машины состоит из двух букв русского алфавита (32 буквы) и из четырёх цифр. Сколько всего существует номеров?
Решение.Пару буквмы можем выбрать способами, четвёрку цифр можновыбрать способами. Значит, всегомашинных номеров можносоставить по принципу произведения
-
Определение7. Перестановкойn-элементного множества называется упорядоченный набор длины n, составленный из этих элементов, причём каждый элемент входит в набор ровно один раз. Число перестановокn-элементного множества обозначается символомPn. Пример. Выпишем все перестановки 3-х элементного множестваA={a;b;c}:(a;b;c),(a;c;b),(b;a;c),(b;c;a),(c;a;b),(c;b;a). Таким образом, P3=6.
-
Теорема 8.Pn=n!
Доказательство. Каждую перестановкуn-элементного множества можно рассматривать какn-размещение этого множества. Поэтому
-
Задача. Сколькими способами на шахматной доске можно расставить 8 ладей таким образом, что бы они не били друг друга.
Решение. Первую вертикаль можно заполнить лишь одной ладьёй, чтобы не нарушалось условие задачи. Причём количество способов заполнить эту вертикаль равно восьми. На вторую вертикаль можно поставить тоже только одну ладью, причём уже семью способами, и т.д. вплоть до восьмой вертикали, которую можно заполнить одним способами. По принципу произведения всего способов расстановки ладей так, чтобы они не били друг друга, будет 8·7·6·…·2·1=8!
-
§3.Сочетания. Свойства сочетаний.Бином Ньютона
Определение 1. Пусть дано n-элементное множество. Любоеk-элементное подмножества множестваAназываетсяk-сочетаниемn-элементногомножества. Числоk-сочетанийn-элементногомножества обозначается . Пример. Выпишем все 2-сочетания4-элементного множестваA={a,b,c,d}:{a;b},{a;c},{a;d},{b,c},{b,d},{c,d}. Таким образом,.
-
Теорема 2.приkn.
Доказательство. Из одногоk-сочетания можно получитьk!k-размещенийn-элементного множества, потому чтоk элементов можно упорядочитьk! способами. Поскольку каждоеk-размещение есть не что иное, как упорядоченноеk-сочетание, то всегоk-размещений будет С другой стороныk-размещений имеется. Получили равенство или ,
-
и отсюда получаем искомую формулу:
-
Теорема 3 (простейшие свойства сочетаний). 1) 2) 3) 4) 5) , (m1);
-
Теорема 4 (бином Ньютона).
-
Доказательство. Второе равенство представляет собой не что иное, как разные записи одной и той же суммы. Слева стоит эта сумма в “развернутом” виде, а справа эта же сумма, записанная с помощью знака суммирования. Поэтому доказываем первое равенство. Рассмотрим выражение:
-
Раскрыв скобки, получим сумму В первой сумме количество слагаемых равно количеству элементов множества то есть . Во второй сумме количество слагаемых равно количеству двухэлементных подмножеств n-элементного множества S, то есть равно .
-
Число слагаемых в k-ой сумме равно количеству k-элементных подмножеств n-элементного множества S , то есть равно Поэтому, если положить в A то получим Теорема доказана
-
Следствие 5. Следствие 6. Следствие 7. (a+b)n =
-
Замечание.В силу большой важности бинома Ньютонадля самых разных разделов математики, числа называются биноминальнымкоэффициентами.
Следствие 9.
-
Определение 10. Пусть А = {a1, a2, …, an} -n–элементное множество. k-сочетанием с повторениями множества А называется неупорядоченный набор [a1,a2,…,ak], где все элементы принадлежат множеству А, причем допустимо повторение этих элементов. Пример. Пусть А = {a, b, c}. Выпишем все 2-сочетания с повторениями множества А: [a, a], [a, b], [a, c], [b, b], [b, c], [c,c]. Число k–сочетаний с повторениями n-элементного множества обозначается . Приведенный пример показывает, что
-
Лемма . Число всех упорядоченных нулей и единиц последовательностей из нулей и единиц длины n, в которых присутствует l нулей, равно (или, что одно и то же).
-
Теорема 12..
Пример. В магазине продаются пирожные 4 сортов. Сколькими способами можно купить 8 пирожных? Решение. Находим число 8-сочетаний с повторениями 4-х элементного множества:
Нет комментариев для данной презентации
Помогите другим пользователям — будьте первым, кто поделится своим мнением об этой презентации.