Презентация "Элементы комбинаторики" 9 класс


Подписи к слайдам:
PowerPoint Presentation

Элементы комбинаторики

9 -11 классы, МБОУ Кочневская СОШ

учитель Грязнова А.К

Основные вопросы:

      • Что такое комбинаторика?
      • Какие задачи считают комбинаторными?

      • Перестановки
      • Размещения
      • Сочетания

Не будем спорить - будем вычислять. Г. Л е й б н и ц

  • Комбинаторика – радел математики, в котором рассматриваются задачи о подсчёте числа комбинаций составленных по определённым правилам.

II. Какие задачи считают комбинаторными?

Комбинаторные задачи

Задачи подсчёта числа комбинаций из конечного числа элементов

  • Комбинаторика от латинского слова combinare, что означает «соединять, сочетать».
  • Методы комбинаторики находят широкое применение в физике, химии, биологии, экономики и др. областях знания.
  • Комбинаторику можно рассматривать как часть теории множеств – любую комбинаторную задачу можно свести к задаче о конечных множествах и их отображениях.

I. Уровни решения комбинаторных задач

1. Начальный уровень.

Задачи поиска хотя бы одного решения, хотя бы одного расположения объектов, обладающих заданным свойствами

- отыскание такого расположения десяти точек на пяти отрезках, при котором на каждом отрезке лежит по четыре точки;

- такого расположения восьми ферзей на шахматной доске, при котором они не бьют друг друга.

Иногда удаётся доказать, что данная задача не имеет решения

(например, нельзя расположить 10 шаров в 9 урнах так, что

бы в каждой урне было не более одного шара – хотя бы в

одной урне окажется не менее двух шаров).

2. Второй уровень.

2. Второй уровень.

Если комбинаторная задача имеет несколько решений, то возникает вопрос о подсчете числа таких решений, описании всех решений данной задачи.

  • 3. Третий уровень.
  • Решения данной комбинаторной задачи отличаются друг от друга некоторыми параметрами. В этом случае возникает вопрос отыскания оптимального варианта решения такой задачи.

    Например:

    Путешественник хочет выехать из города А, посетить города В, С, и D. После чего вернуться в город А.

Путь

Длина пути

Путь

Длина пути

ABCDA

1555

ACDBA

1300

ABDCA

1300

ADBCA

1450

ACBDA

1450

ADCBA

1550

С

В

А

300

200

400

500

400

350

D

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

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

  • Комбинаторные задачи на оптимизацию приходится решать мастеру, стремящемуся к быстрейшему выполнению задания, агроному, стремящемуся к наивысшей урожайности на данных полях, и т.д.

Мы будем рассматривать лишь задачи о подсчёте числа решений комбинаторной задачи.

  • Мы будем рассматривать лишь задачи о подсчёте числа решений комбинаторной задачи.
  • Этот раздел комбинаторики, называемый теорией перечислений, тесно связан с теорией вероятностей.

Правила суммы и произведения

  • 1. Сколько различных коктейлей можно составить из четырёх напитков, смешивая их в равных количествах по два?
  • AB, AC, AD, BC, BD, CD – всего 6 коктейлей
  • 2. Сколько различных двузначных чисел можно составить из цифр 0, 1, 2, 3 ?
  • Первой цифрой двузначного числа может одна из цифр 1, 2, 3 (цифра 0 не

    может быть первой). Если первая цифра выбрана, то вторая может быть любая из

    цифр 0, 1, 2, 3. Т.к. каждой выбранной первой соответствует четыре способа

    выбора второй, то всего имеется

    4 + 4 + 4 = 4·3 = 12 различных двузначных чисел.

А

D

С

В

2. Сколько различных двузначных чисел можно составить из цифр 0, 1, 2, 3 ?

  • 2. Сколько различных двузначных чисел можно составить из цифр 0, 1, 2, 3 ?
  • 4 + 4 + 4 = 4·3 = 12 различных двузначных чисел.

  • Первая цифра вторая цифра
  • 1
  • 2
  • 3

0

1

2

3

0

1

2

3

0

1

2

3

Правило произведения:

  • Если элемент А можно выбрать из множества элементов п способами и для каждого такого выбора элемент В можно выбрать т способами, то два элемента (пару) А и В можно выбрать п·т способами.

«Примеры решения комбинаторных задач: перебор вариантов, правило суммы, правило умножения».

  • Сколькими способами могут быть расставлены 4 участниц финального забега на четырёх беговых дорожках?
  • Рп = 4· 3 ·2 ·1= 24 способа (перестановки из 4-х элементов)

1 2 3 4

2 3 4 1 3 4 1 2 4 1 2 3

3 4 2 4 2 3

4 3 4 2 3 2

3 4 1 4 3 1

4 3 4 1 1 3

2 4 1 4 1 2

4 2 4 1 2 1

2 3 1 3 1 2

3 2 3 1 2 1

1 дорожка

2 доржка

3доржка

4 дор.

Р е ш е н о п е р е б о р о м в а р и а н т о в

II. Перестановки (1)

К в а р т е т

Проказница Мартышка,

Осёл,

Козёл

Да косолапый Мишка

Затеяли сыграть Квартет.

…………………………………………………….

Ударили в смычки, дерут, а толку нет.

«Стой, братцы, стой! - кричит Мартышка. –

Погодите!

Как музыке идти? Ведь вы не так сидите»

4·3·2·1 = 4! способов

II. Перестановки (2)

  • Перестановкой из п - элементов называется комбинации, отличающиеся друг от друга лишь порядком следования элементов
  • Рп- число перестановок (Р первая буква французского слова permutation- перестановка)
  • Рп= n·(n-1)·(n-2)·(n-3)·(n-4)·. . .·3 ·2 ·1= n!

    Рп = n!

В математике принято считать 0! =1 и 1! = 1

Размещения (1)

  • Четыре попутчик решили обменяться визитными карточками. Сколько всего карточек при этом было использовано?
  • получилось 12 карточек. Каждый из четырёх

    попутчиков вручил визитку каждому из

    трёх попутчиков

    4 · 3 = 12

1

3

4

2

Комбинации, составленные из k элементов, взятых из n элементов, и отличающиеся друг от друга либо составом, либо порядком расположения элементов, называются размещениями из n элементов по k (0< k ≤n ).

- размещение из n элементов по k элементов. А первая буква

французского слова arrangement : «размещение»,

«приведение в порядок»

Размещения (2)

  • Пуст имеется 4 шара и 3 пустых ячейки. Обозначим шары буквами a, b, c, d. В пустые ячейки можно по разному разместить три шара из этого набора.
  • Выбирая по-разному первый, второй и третий шары, будем получать различные упорядоченные тройки шаров
  • Каждая упорядоченная тройка, которую можно составить из четырёх элементов называется размещением из четырёх элементов по три

d

b

c

b

a

c

a

c

b

a

b

c

Размещения (3)

  • Сколько же размещений можно составить из 4-х элементов (abcd) по три?
  • abc abd acb acd adb adc
  • bac bad bca bcd bda bdc
  • cab cad cba cbd cda cdb
  • dab dac dba dbc dca dcb

Р е ш е н о п е р е б о р о м в а р и а н т о в

Размещения (4)

  • Можно решить и не выписывая самих размещений:
  • первый элемент можно выбрать четырьмя способами, так им может быть любой элемент из четырёх;
  • для каждого первого второй можно выбрать тремя способами;
  • для каждых первых двух можно двумя способами выбрать третий элемент из двух оставшихся.
  • Получаем

= 4·3·2 = 24

Решено с использованием п р а в и л а у м н о ж е ни я

Сочетания

  • Сочетанием из п элементов по k называют любое множество, составленное из k элементов, выбранных из п элементов

В отличии от размещений в сочетаниях не имеет значение порядок элементов. Два сочетания отличаются друг от друга хотя бы одним элементом

Р е ш и з а д а ч и:

1. На плоскости отмечено 5 точек.

Сколько получится отрезков, если соединить точки попарно?

2. На окружности отмечено п точек. Сколько существует треугольников с вершинами в этих точках?

Источники информации

  • В.Ф.Бутузов, Ю.М.Колягин, Г.Л. Луканкин, Э.Г.Позняк и др. «Математика» учебное пособие для 11кл общеобразовательных учреждений /рекомендовано Министерством образования РФ/ М., Просвещение, 1996.
  • Е.А. Бунимович, В.А. Булычёв: «Вероятность и статистика», пособие для общеобразовательных учебных заведений 5 – 9 классы / допущено Министерством образования Российской Федерации // Дрофа Москва 2002
  • Ю.Н. Макарычев, Н.Г.Миндюк «Алгебра: элементы статистики и теории вероятностей 7 – 9 классы» Под редакцией С.А.Теляковского М: Просвещение , 2006 г
  • Треугольнички http://works.doklad.ru/images/_E3ZV-_wFwU/md87b96f.gif
  • Остальные рисунки созданы Грязновой А.К.