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


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

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

  • Сочетания

  • перебор
  • перестановка
  • Вопрос дня:
  • КАК РАЗЛИЧАТЬ
  • ПРИМЕНЕНИЕ ТЕОРЕМ?

  • Вопрос дня: КАК различить: задача на перестановки или
  • размещения?
  • Количество рассматриваемых элементов множества
  • совпадает с исходным
  • количеством элементом
  • меньше исходного
  • количества элементов

  • перестановки
  • размещения
  • Перестановкой из n элементов множества называется расположение этих элементов в определённом порядке
  • Размещением из n элементов
  • по k элементов называется любое
  • множество, состоящее из k элементов, взятых в определённом порядке из данных n элементов.
  • сочетания
  • Сочетанием из n элементов по k называется
  • любое множество, составленное из k элементов, выбранных из данных n элементов

Пусть имеются пять гвоздик разного цвета:

  • Пусть имеются пять гвоздик разного цвета:
  • a, b, c, d, e.
  • Требуется составить букет из трёх гвоздик.
  • Если в букет входит гвоздика a, то можно
  • составить такие букеты:
  • abc, abd, abe, acd, ace, ade
  • Если в букет не входит гвоздика a, но входит
  • гвоздика b, то можно составить такие букеты:
  • bcd, bce, bde
  • Если в букет не входят ни гвоздика a, ни гвоздика b, возможен один вариант
  • составления букета c, d, e

  • Указали все возможные способы составления букетов, в которых по-разному сочетаются три гвоздики из данных пяти
  • Составили все возможные СОЧЕТАНИЯ
  • из 5 элементов по 3 элемента.
  • Обозначение:
  • «combinations»
  • В рассмотренном примере

  • Рассмотрим множество, содержащее n элементов, и
  • из его элементов составлены все возможные
  • сочетания по k элементов.
  • Число таких сочетаний равно
  • В каждом сочетании можно выполнить
  • перестановок
  • Рk
  • В результате получим все размещения ,
  • которые можно составить из n элементов по k
  • Их число равно
  • значит
  • Отсюда

  • Другими словами:
  • Несложные преобразования
  • приводят полученную формулу к виду:
  • Запомним 0!=1

Пример 1:

  • Из 15 членов туристической группы надо
  • выбрать 3 дежурных. Сколькими способами это
  • можно сделать?
  • Речь идёт о сочетаниях из 15 элементов по 3.

Пример 2:

  • Из вазы с фруктами, в которой лежит 9 яблок и
  • 6 груш, надо выбрать 3 яблока и 2 груши.
  • Сколькими способами можно сделать такой
  • выбор?
  • Выбрать 3 яблока из 9 можно способами,
  • А выбрать 2 груши из 6 можно способами.
  • Таким образом, учитывая правило умножения, выбор,
  • соответствующий условию задачи, можно сделать

  • Вопрос дня: как распознать решение задачи
  • перестановки
  • размещения
  • сочетания