Тема занятия: Элементы комбинаторики. Перестановки.
Лекция.
Определение: Комбинаторика – это раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов.
Слово «комбинаторика» происходит от латинского слова «combinare», что в переводе на русский означает – «сочетать», «соединять». Комбинаторные задачи возникли и в связи с такими играми, как шашки, шахматы, домино, карты, кости и т.д.
Термин "комбинаторика" был введён знаменитым Готфридом Вильгельмом Лейбницем, - всемирно известным немецким учёным.
Комбинаторные задачи делятся на: задачи на перестановки,задачи на размещение, задачи на сочетание
Определение: Факториал – это произведение всех натуральных чисел от 1 до n.
Обозначение: n! = 1 · 2 · 3 ·... · n. Читается: «эн факториал».
Пример: 4! = 1 · 2 · 3 · 4 = 24.
Кроме того: 0! = 1. 1!=1
Задачи на перестановки
Сколькими способами можно расставить 3 различные книги на книжной полке?
Это задача на перестановки.
Решение: Выбираем одну из 3-х книг и ставим на первое место. Это можно сделать 3-мя способами.
Вторую книгу мы можем выбрать из 2-х оставшихся двумя способами, получаем 3·2 способов.
Третью книгу мы можем выбрать 1 способом.
Получится 3·2·1=6 способов.
Ответ: 6.
Определение: Перестановками из n элементов называются комбинации из n элементов, отличающиеся друг от друга только порядком расположения в них элементов.
Формула
Типичная смысловая нагрузка: «Сколькими способами можно переставить n объектов?»
Пример 1. Сколькими способами можно расставить 8 участников финального забега на восьми беговых дорожках?
Решение: P8= 8!=1 ∙ 2 ∙ 3 ∙ 4 ∙ 5 ∙ 6 ∙ 7 ∙ 8 = 40320.
Ответ: 40320.
Пример 2. Сколькими способами можно составить расписание на один день, если в этот день предусмотрено 6 уроков по 6 разным предметам?
Решение: P6= 6!=1 ∙2 ∙ 3 ∙ 4 ∙ 5 ∙ 6 = 720.
Ответ: 720.
Пример 3. Сколькими различными способами можно разместить на скамейке 10 человек?
Решение: P8= 8!=1 ∙ 2 ∙ 3 ∙ 4 ∙ 5 ∙ 6 ∙ 7 ∙ 8 ∙ 9 ∙ 10 = 3628800.
Ответ: 3628800.
Пример 4. Сколько слов можно получить, переставляя буквы в слове Гора?
Решение: P4= 4!=1 ∙2 ∙ 3 ∙ 4 = 24.
Ответ: 24.
Пример 5. Сколько различных шестизначных чисел, кратных 5, можно составить из цифр 1, 2, 3, 4, 5, 6 при условии, что цифры в числе не повторяются?
Решение: Чтобы число было кратным 5, цифра 5 должна стоять на последнем месте. Остальные цифры могут стоять на оставшихся пяти местах в любом порядке. Следовательно, искомое количество шестизначных чисел, кратных 5, равно числу перестановок из 5 элементов, т.е.
P5= 5!=1 ∙ 2 ∙ 3 ∙ 4 ∙ 5 = 120.
Ответ: 120.
Перестановки с повторениями
У мамы 2 яблока и 3 груши. Каждый день в течение 5 дней подряд она выдает по одному фрукту. Сколькими способами это может быть сделано?
Решение: Имеем набор {я, я, г, г, г}. Всего перестановок пятиэлементного множества 5!, но мы не должны учитывать перестановки, в которых объекты одного типа меняются местами несколько раз, поэтому нужно поделить на возможное число таких перестановок: 2! · 3!.
В итоге получаем
Ответ: 10.
Формула:
Типичная смысловая нагрузка: «Количество способов, которыми можно переставить n объектов, среди которых 1-й объект повторяется n1 раз, 2-й объект повторяется n2раз, 3-й объект повторяется n3раз, …, k-й объект повторяется nkраз».
Пример 1: Сколько различных буквосочетаний можно получить перестановкой карточек со следующими буквами: К, О, Л, О, К, О, Л, Ь, Ч, И, К?
Решение: Всего: 11 карточек, среди которых буква:
К – повторяется 3 раза;
О – повторяется 3 раза;
Л – повторяется 2 раза;
Ь – повторяется 1 раз;
Ч – повторяется 1 раз;
И – повторяется 1 раз.
По формуле количества перестановок с повторениями:
Ответ: 554400.
Пример 2: Сколько слов можно получить, переставляя буквы в слове Институт?
Решение: В слове «институт» 8 букв, из них две буквы «и», три буквы «т» и по одной букве «н», «с» и «у». Поэтому всего можно получить перестановками букв различных слов.
Ответ: 3360.
Пример 3: Алексей занимается спортом, причём 4 дня в неделю – лёгкой атлетикой, 2 дня – силовыми упражнениями и 1 день отдыхает. Сколькими способами он может составить себе расписание занятий на неделю?
Решение: По формуле количества перестановок с повторениями:
способами можно составить расписание занятий на неделю.
Ответ: 105.
Пример 4: Сколько чисел, больших 3000000, можно составить из цифр 3, 2, 2, 1, 1, 1, 0.
Решение: На первом месте обязательно должна стоять тройка. Оставшиеся 6 цифр образуют перестановку с повторениями: .
Ответ: 60.