Презентация на тему "Теория конечных множеств (комбинаторика)"

Презентация: Теория конечных множеств (комбинаторика)
1 из 40
Ваша оценка презентации
Оцените презентацию по шкале от 1 до 5 баллов
  • 1
  • 2
  • 3
  • 4
  • 5
0.0
0 оценок

Комментарии

Нет комментариев для данной презентации

Помогите другим пользователям — будьте первым, кто поделится своим мнением об этой презентации.


Добавить свой комментарий

Аннотация к презентации

Презентация на тему "Теория конечных множеств (комбинаторика)" по математике. Состоит из 40 слайдов. Размер файла 0.3 Мб. Каталог презентаций в формате powerpoint. Можно бесплатно скачать материал к себе на компьютер или смотреть его онлайн.

  • Формат
    pptx (powerpoint)
  • Количество слайдов
    40
  • Слова
    математика
  • Конспект
    Отсутствует

Содержание

  • Презентация: Теория конечных множеств (комбинаторика)
    Слайд 1

    ТЕОРИЯ КОНЕЧНЫХ МНОЖЕСТВ (КОМБИНАТОРИКА)

    §1. Принципы сложения и умножения Комбинаторика занимается подсчетом количеств разных комбинаций, которые можно получить различными способами из тех или иных конечных множеств.

  • Слайд 2

    Если конечное множество 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).

  • Слайд 3

    Доказательство: При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). Следствие доказано.

  • Слайд 4

    Иногда принцип сложения можновстретить в таком виде: если объект x можно получитьm способами, а объектyможно получить l способами, причем множества этих способов не пересекаются, то объект x или объект yможно получить m + lспособами. Таким образом, необходимо помнить, что в комбинаторике союз “или”ассоциирован с операцией сложения.

  • Слайд 5

    Теорема 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},

  • Слайд 6

    Гдемножество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.

  • Слайд 7

    В комбинаторном изложении принцип умножения часто формулируют так: если объект xможно сконструировать m способами, объект y можно сконструировать l способами, то объект(x,y)или (x иy) можно сконструировать m · l способами. То есть союз “и” в комбинаторики ассоциирован с операцией умножения.

  • Слайд 8

    Теорема 4. Если множестваA1, A2,…,Akконечны, то n(A1 A2 ,…,Ak )=n(A1) · n(A2)·,…, ·n(Ak ).

  • Слайд 9

    Задача . Пусть 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).

  • Слайд 10

    Задача . Из цифрA={0,1,2,3,5,6,7} составить все четырех­значные числа, не содержащие повторяющихся цифр и делящиеся на 3.

    Решение. Воспользуемся признаком делимости на три: число делится на три в том и только в том случае, когда сумма цифр этого числа делится на три. Поэтому надо перебрать всевозможные четверки цифр, сумма которых делится на три. Перечислим такие четверки:

  • Слайд 11

    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.

  • Слайд 12

    Аналогично 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

  • Слайд 13

    §2. Размещения и перестановки

    Определение 1. Пусть дано конечное множествоA, n(A)=nи 1 ≤ k ≤ n.k-размещением множестваAназывается любой упорядоченный набор длины k(), где все координаты - попарно различные элементы множества A. Число всехk-размещенийn-элементного множества обозначается через .

  • Слайд 14

    Пример. Пусть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). Таким образом

  • Слайд 15

    Теорема 2. Пустьn  N, 1≤k≤ n. Тогда.

    Доказательство. Применим индукциюпоk. Докажем равенство при k=1. 1-размещения это наборысостоящие из одногоэлемента,взятого изn-элементного множества. Очевидно, что их будет столько же, сколько элементов, в n-элементном множестве,то есть .

  • Слайд 16

    C другой стороны , то есть

  • Слайд 17

    Допустим, равенство выполняется дляk

  • Слайд 18
  • Слайд 19

    Пример. В первенстве страны участвуют 12 команд. Сколькими способами они смогут занять призовые места.

    Решение. Поскольку является существенным тот факт, какая команда займет первое место, какая – второе, какая - третье, то задача сводится к вопросу: сколькими способами можно выбрать трёхэлементный упорядоченный набор из 12-элементного множества.Таких способов будетспособов.

  • Слайд 20

    Замечание 3. Приk>nневозможно построитьk-размещение, поэтому при k>n. Замечание 4. Приk=0под 0-размещением мы будем понимать пустое множество. Так как пустое множество единственно, то чтосогласуется с формулой, так как приk=0имеем

  • Слайд 21

    Определение 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-элементного множества обозначается

  • Слайд 22

    Теорема 6.

    Доказательство. Применим индукцию поk. Приk=1число1-размещений равно числу элементов множестваA, то есть Сдругой стороны,n1=n. Базис индукции доказан. Допустим, формула верна приk=l, то есть

  • Слайд 23

    Докажем утверждение приk= l +1. Из каждого упорядоченногоl-элементного набора можнополучить n упорядоченных наборов длиныl+1, приписывая любой элементAсправа, тоесть (l +1)-размещений с повторениями вn раз больше,чем l-размещений с повторениями, тоесть Теорема доказана.

  • Слайд 24

    Пример. Номер машины состоит из двух букв русского алфавита (32 буквы) и из четырёх цифр. Сколько всего существует номеров?

    Решение.Пару буквмы можем выбрать способами, четвёрку цифр можновыбрать способами. Значит, всегомашинных номеров можносоставить по принципу произведения

  • Слайд 25

    Определение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.

  • Слайд 26

    Теорема 8.Pn=n!

    Доказательство. Каждую перестановкуn-элементного множества можно рассматривать какn-размещение этого множества. Поэтому

  • Слайд 27

    Задача. Сколькими способами на шахматной доске можно расставить 8 ладей таким образом, что бы они не били друг друга.

    Решение. Первую вертикаль можно заполнить лишь одной ладьёй, чтобы не нарушалось условие задачи. Причём количество способов заполнить эту вертикаль равно восьми. На вторую вертикаль можно поставить тоже только одну ладью, причём уже семью способами, и т.д. вплоть до восьмой вертикали, которую можно заполнить одним способами. По принципу произведения всего способов расстановки ладей так, чтобы они не били друг друга, будет 8·7·6·…·2·1=8!

  • Слайд 28

    §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}. Таким образом,.

  • Слайд 29

    Теорема 2.приkn.

    Доказательство. Из одногоk-сочетания можно получитьk!k-размещенийn-элементного множества, потому чтоk элементов можно упорядочитьk! способами. Поскольку каждоеk-размещение есть не что иное, как упорядоченноеk-сочетание, то всегоk-размещений будет С другой стороныk-размещений имеется. Получили равенство или ,

  • Слайд 30

    и отсюда получаем искомую формулу:

  • Слайд 31

    Теорема 3 (простейшие свойства сочетаний). 1)       2)       3)       4)       5)      , (m1);

  • Слайд 32

    Теорема 4 (бином Ньютона).

  • Слайд 33

    Доказательство. Второе равенство представляет собой не что иное, как разные записи одной и той же суммы. Слева стоит эта сумма в “развернутом” виде, а справа эта же сумма, записанная с помощью знака суммирования. Поэтому доказываем первое равенство. Рассмотрим выражение:

  • Слайд 34

    Раскрыв скобки, получим сумму В первой сумме количество слагаемых равно количеству элементов множества то есть . Во второй сумме количество слагаемых равно количеству двухэлементных подмножеств n-элементного множества S, то есть равно .

  • Слайд 35

    Число слагаемых в k-ой сумме равно количеству k-элементных подмножеств n-элементного множества S , то есть равно Поэтому, если положить в A то получим Теорема доказана

  • Слайд 36

    Следствие 5. Следствие 6. Следствие 7. (a+b)n =

  • Слайд 37

    Замечание.В силу большой важности бинома Ньютонадля самых разных разделов математики, числа называются биноминальнымкоэффициентами.

    Следствие 9.

  • Слайд 38

    Определение 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-элементного множества обозначается . Приведенный пример показывает, что

  • Слайд 39

    Лемма . Число всех упорядоченных нулей и единиц последовательностей из нулей и единиц длины n, в которых присутствует l нулей, равно (или, что одно и то же).

  • Слайд 40

    Теорема 12..

    Пример. В магазине продаются пирожные 4 сортов. Сколькими способами можно купить 8 пирожных? Решение. Находим число 8-сочетаний с повторениями 4-х элементного множества:

Посмотреть все слайды

Сообщить об ошибке