Презентация на тему "Основы комбинаторики"

Презентация: Основы комбинаторики
Включить эффекты
1 из 54
Ваша оценка презентации
Оцените презентацию по шкале от 1 до 5 баллов
  • 1
  • 2
  • 3
  • 4
  • 5
2.0
1 оценка

Комментарии

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

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


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

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

Смотреть презентацию онлайн с анимацией на тему "Основы комбинаторики" по математике. Презентация состоит из 54 слайдов. Материал добавлен в 2017 году. Средняя оценка: 2.0 балла из 5.. Возможность скчачать презентацию powerpoint бесплатно и без регистрации. Размер файла 0.33 Мб.

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

Содержание

  • Презентация: Основы комбинаторики
    Слайд 1

    § 1. Примеры комбинаторных задач и общие принципы комбинаторики

  • Слайд 2

    Правило произведения Пусть объект а1можно выбрать n1, различными способами, после каждого выбора объекта а1объект а2можно выбрать n2различными способами,..., после каждого выбора объектов а1, а2,..., аp-1 объект аpможно выбрать nрразличными способами. Тогда количество способов, которыми можно выбрать а1, а2, ..., аpравно n1n2...np.

  • Слайд 3

    Составление слова из восьми букв можно представить как заполнение буквамиклеток следующей таблицы: 1 2 3 4 5 6 7 8 На первое место можно поставить любую из восьми букв, на второе - любую из семи оставшихся и т.д. вплоть до заполнения единственным способом клетки № 8 последней оставшейся буквой. Число способов заполнения таблицы будет равно 8·7·6·5·4·3·2·1=8! Напомним, что символом п! (читается «эн факториал») обозначается произведение всех натуральных чисел от 1 до п: n!=1·2·...·(n-1)·n. Ответ:n!= 1 • 2 • ...• (n -1) • п.

  • Слайд 4

    Пример 2. Сколько четырехбуквенных «слов» можно составить из карточек «в», «е», «ч», «н», «о», «с», «т», «ь»? Пусть ак- к -я буква слова (к =1,2,3,4). Тогда n1= 8,n2= 7, n3=6, nА= 5 и по правилу произведения сразу получаем ответ: 8·7·6·5 = 1680. Ответ: 1680.

  • Слайд 5

    Пример 3. Сколькими способами можно поставить на шахматную доску белую и черную ладью так, чтобы они не били друг друга?

  • Слайд 6

    Выбор объекта а1 - поля для белой ладьи - может быть сделан n1 = 64 способами. Независимо от выбора этого поля белая ладья бьет 15 полей, поэтому для черной ладьи остается 64-15 =49 полей: n2= 49. Ответ: число расстановок ладей равно 64 · 49 = 3136.

  • Слайд 7

    Пример 5. Сколь различных слов можно получить, переставляя буквы слова «комбинаторика»?

  • Слайд 8

    В слове «комбинаторика» 13 букв. Если бы все они были различны, то, переставляя их, можно было бы получить 13! слов. Но в нашем слове буквы к, о, и, а встречаются по два раза. Обозначим их к1,к2,о1,о2,и1,и2,а1,а2. Ясно, что слова, отличающиеся перестановкой букв к1ик2 - одинаковые, так что 13! Слов разбиваются на пары одинаковых. Следовательно, если мы не различаем к1 и к2, то число всех слов будет равно 13!/2!. Но эта совокупность также разбивается на пары одинаковых с точки зрения буквы “о„ слов и т.д. 13! 13! Ответ: = = —. 2!2!2!2! 16

  • Слайд 9

    Пример 6. Сколько существует четырехзначных чисел, у которых все цифры нечетные? Сколько существует четырехзначных чисел, в записи которых есть хотя бы одна четная цифра?

  • Слайд 10

    Всего нечетных цифр — пять, поэтому выбор к-йцифры числа может быть сделан nк=5 способами (к =1, 2, 3, 4) а количество четырехзначных чисел, у которых все цифры нечетные, равно 5·5·5·5 = 625.

  • Слайд 11

    Правило суммы Если объект а можно выбрать т различными способами, аобъект bможно выбрать nразличными способами, причемрезультаты выбора объектов а и b никогда не совпадают, то выбор“либо а, либо b» можно осуществить т + nразличными способами.

  • Слайд 12

    Пример 7. Сколько различных пар можно образовать из 28 костей домино так, чтобы кости, входящие в пару, можно было приложить друг к другу?

  • Слайд 13

    Выбор пары костей — это выбор двух карточек вида a1b1, a2b2, где можно считать, что а ≤ b. Выберем первую кость - это можно сделать 28 способами, из них в 7 случаях кость окажется дублем, т.е. кость вида aa, а в 21 случае — кость вида ab, а

  • Слайд 14

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

  • Слайд 15

    Определение. Всякая упорядоченная выборка объема k из множества, состоящего из nэлементов, называется размещением из n элементов по k элементов и обозначается через Аn . k

  • Слайд 16

    Определение. Размещение из nэлементов по nназывается перестановкой из n элементов и обозначается через Рn .

  • Слайд 17

    Справедлива формула Аn =n (n-1)...(n - к + 1) k где 1 ≤ к ≤ n.

  • Слайд 18

    На первое место в выборке можно поместить любой из nэлементов, на второе - любой из (n- 1) оставшихся и т.д. После выбора элементов на(k-1)-е место останется n-(к-1) = n-к+1 элемен- 1 2k-1 k тов, любой из которых можно поместить на к-е место. По правилу произведения получаем Аn =(n-1)...(n - к + 1) В частности, Рn=An=n(n-1)… ·2·1 = n!(2) n k

  • Слайд 19

    An= n(n - 1)...(n- k+1)·(n-k)!=n! (n-к)!(n-к)! k

  • Слайд 20

    Пример 9. Сколько шестизначных чисел, кратных 5, можно составить из цифр 0, 1,2, ..., 9 при условии, что цифры в записи числа не повторяются?

  • Слайд 21

    Последней цифрой искомого числа может быть 0 или 5. В первом случае остальные пять цифр можно выбирать из множества {1,2, ..., 9} 9! и число вариантов равно А9 = — = 15120. Если число 4! oканчиваетсяцифрой 5, то в качестве первой цифры можно взять любую из восьми цифр 1, 2, 3, 4, 6, 7, 8, 9 - нельзя использовать 0, т.к. число должно быть шестизначным. Цифры со второй по четвертую можно выбрать A8= 1680 различными способами. Следовательно, по правилупроизведения имеется 8·A8чисел, оканчивающихся цифрой 5. По правилу суммы находим, сколько существует чисел, удовлетворяющих условию задачи. А9+8·A8 = 28560. Ответ: 28560. 5 4 4 5 4

  • Слайд 22

    Пример 10. Сколькими способами можно расставить на книжной полке десятитомник Пушкина так, чтобы том 2 стоял рядом с томом 1 и справа от него? Ответ: 9!

  • Слайд 23

    § 3. Сочетания

  • Слайд 24

    Определение. Всякая неупорядоченная выборка объема к из множества, состоящего из nэлементов (к≤n), называется сочетанием из n элементов по к элементов и обозначается через Сn . k

  • Слайд 25

    Из любого набора,содержащего к элементов, можно с помощью перестановок получить k! упорядоченных выборок объемаk, поэтому Откуда (4)

  • Слайд 26
  • Слайд 27

    Пример 11. Хоккейная команда состоит из 2 вратарей, 7 защитников и 10 нападающих. Сколькими способами тренер может образовать стартовую шестерку, состоящую из вратаря, двух защитников и трех нападающих?

  • Слайд 28

    Вратаря можно выбрать способами, защитников - способом, нападающих– способами. Всего, по правилу произведения, существует 2 · 21 · 120 = 5040 способов выбора стартовой шестерки. Ответ: 5040.

  • Слайд 29

    Пример 12. На плоскости проведены nпрямых, среди которых нет ни одной пары параллельных прямых и ни одной тройки прямых, пересекающихся в одной точке. Найти число точек пересечения этих прямых и число треугольников, образованных этими прямыми.

  • Слайд 30

    Число точек пересечения прямых равно числу способов выбора неупорядоченной пары прямых, т.е.. Аналогично, каждый треугольник определяется тройкой прямых, поэтому общее число треугольников равно . Ответ:и .

  • Слайд 31

    Пример 13. Для проведения письменного экзамена по комбинаторике надо составить 4 варианта по 7 задач в каждом. Сколькими способами можно разбить 28 задач на 4 варианта?

  • Слайд 32

    Задачи для первого варианта можно выбрать способами. После этого останется 21 задача, так что второй вариант можно составить способами. Для третьего варианта задачи можно выбрать способами, а для четвертого - = 1 способом.

  • Слайд 33

    По правилу произведения получаем число. Но так как варианты равноправны, то полученное число надо разделить на 4! Ответ: =

  • Слайд 34

    Свойства чисел : 1°. , если 0≤к≤n; 2°. , если 0≤к≤n+1; 3°.

  • Слайд 35

    Свойство 1°

  • Слайд 36

    Свойство 2°

  • Слайд 37
  • Слайд 38

    Треугольник Паскаля:

  • Слайд 39

    Свойство 3° Положим Так как каждое число строки с номером п входит в качестве слагаемого в два соседних числа следующей строки, то Sn+1 = 2Sn. Следовательно, т.к. S0=1.

  • Слайд 40

    § 4. Бином Ньютона

  • Слайд 41

    (a + b) =a +2ab + bи (a + b) = а +3а b + 3ab +b .

  • Слайд 42
  • Слайд 43

    Если в формуле (5) взять а =b = 1, то получится известное намсвойство 3° чисел , а если взять а=1, b = -1, то получим еще одно комбинаторное равенство:

  • Слайд 44
  • Слайд 45

    Формула (6) называется полиномиальной. Например, (а + b + с) = а + b + с + 3(а b + а с + b а + b с + с а + c b ) + 6abc.

  • Слайд 46

    Пример 14. Найти n, если известно, что в разложении (1 + x) коэффициенты при х и хравны.

  • Слайд 47

    В n-й строке треугольника Паскаля два коэффициента равны в том и только том случае, когда они занимают клетки, равноудаленные от крайних. Действительно, треугольник Паскаля симметричен:, а при движении от края к середине строки коэффициенты возрастают: при и при

  • Слайд 48

    Следовательно, равно тогда и только тогда, когда 12 = n-5, т.е. n= 17. Ответ:n= 17.

  • Слайд 49

    Пример 15. Найти коэффициент при х в разложении (1 + х+х).

  • Слайд 50

    В силу формулы (6) = Так как уравнение 5k2 + 9к3=19 имеет только одно решение в неотрицательных числах k2=2, k3= 1, то коэффициент при х равен

  • Слайд 51

    2) Обозначим через. Тогда Рассмотрим k-е слагаемое (0≤k≤30): Такое слагаемое будет содержать х, если для некоторого твыполняется равенство 5k+ 4m = 19. Ясно, что это возможно только при k=3 и т=1. Следовательно, коэффициент при х равен =12180.

  • Слайд 52

    Литература 1. Кутасова А.Д., Пиголкина Т.С, Чехлов В.И., Яковлева Т.Х.,Пособие по математике для поступающих в вузы. /под ред. Г.Н.Яковлева - M.: Наука, 1988. 2. Виленкин Н.Я. Популярная комбинаторика. — М.: Наука, 1975. 3. Генкин С.А., Итенберг И.В., Фомин Д.В. Ленинградскиематематические кружки. — Киров, 1994.

  • Слайд 53

    Контрольные вопросы Сколько делителей у числа 2004 ? Сколько диагоналей в выпуклом 2004-угольнике? Сколько различных натуральных решений имеет неравенство n+m≤2004? 4. Чему равен коэффициент при х y в выражении (х + у) после раскрытия скобок? 5. С помощью соответствующей строки треугольника Паскалявыпишите формулу для вычисления (а-b) .

  • Слайд 54

    Задачи 1(3). Сколько различных слов можно получить, переставляя буквы в слове «параллелограмм»? 2(4). Сколькими способами можно переставлять буквы слова «раз-­ мещение» так, чтобы три буквы «е» не шли подряд? 3(3). Решите уравнение 4(3). Известно, что никакие три диагонали выпуклого восьмиуголь­ника не пересекаются в одной точке. Найдите число точек пе­ресечения диагоналей. 5(4). Сколькими способами можно поставить на шахматную доску белого и черного слонов так, чтобы они не били друг друга? 6(5). Найдите сумму всех трехзначных чисел, которые можно напи­сать с помощью цифр 1, 2, 3, 4, 5 (любую из цифр можно ис­пользовать несколько раз). 7(5). Докажите тождество 8(6).Сколькими способами можно распределить 12 различных книг по четырем полкам так, чтобы на каждой полке ока­залась ровно три книги? 9(6). Сколькими способами можно распределить 12 одинако­вых книг по четырем полкам так, чтобы на каждой полке была хотя бы одна книга? В задачах №8 и №9 все полки разные. 10(6). В выпуклом восьмиугольнике проведены все диагона­ли, причем известно, что никакие три диагонали не пере­секаются в одной точке. На сколько частей разделится восьмиугольник? 11(6). Найдите наибольший коэффициент многочлена (1 + 2х). 12(6). Найдите коэффициент при хв разложении по степе ням х 1+(1+x)+…+(1+x) .

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

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