Перестановки с повторениями

Тема занятия: Элементы комбинаторики. Перестановки.

Лекция.

Определение: Комбинаторика – это раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов.

Слово «комбинаторика» происходит от латинского слова «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 участников финального забега на восьми беговых дорожках?

Решение: P₈= 8!=1 ∙ 2 ∙ 3 ∙ 4 ∙ 5 ∙ 6 ∙ 7 ∙ 8 = 40320.

Ответ: 40320.

Пример 2. Сколькими способами можно составить расписание на один день, если в этот день предусмотрено 6 уроков по 6 разным предметам?

Решение: P₆= 6!=1 ∙2 ∙ 3 ∙ 4 ∙ 5 ∙ 6 = 720.

Ответ: 720.

Пример 3. Сколькими различными способами можно разместить на скамейке 10 человек?

Решение: P₈= 8!=1 ∙ 2 ∙ 3 ∙ 4 ∙ 5 ∙ 6 ∙ 7 ∙ 8 ∙ 9 ∙ 10 = 3628800.

Ответ: 3628800.

Пример 4. Сколько слов можно получить, переставляя буквы в слове Гора?

Решение: P₄= 4!=1 ∙2 ∙ 3 ∙ 4 = 24.

Ответ: 24.

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

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

P₅= 5!=1 ∙ 2 ∙ 3 ∙ 4 ∙ 5 = 120.

Ответ: 120.

 

Перестановки с повторениями

У мамы 2 яблока и 3 груши. Каждый день в течение 5 дней подряд она выдает по одному фрукту. Сколькими способами это может быть сделано?

Решение: Имеем набор {я, я, г, г, г}. Всего перестановок пятиэлементного множества 5!, но мы не должны учитывать перестановки, в которых объекты одного типа меняются местами несколько раз, поэтому нужно поделить на возможное число таких перестановок: 2! · 3!.

В итоге получаем

Ответ: 10.

Формула:

 

Типичная смысловая нагрузка: «Количество способов, которыми можно переставить n объектов, среди которых 1-й объект повторяется n₁ раз, 2-й объект повторяется n₂раз, 3-й объект повторяется n₃раз, …, k-й объект повторяется n_kраз».

Пример 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.