занятие 8

Тема: Комбинаторика

    

     Сегодня - последнее занятие по комбинаторике. Здесь будет разобрано большое количество комбинаторных задач. Не поленитесь их все внимательно изучить!

     Рассмотрим задачи, где требуется посчитать количество способов, которыми можно расположить в ряд n предметов. Такие расположения называются перестановками и играют замечательную роль в комбинаторике и алгебре.

     Пусть n - натуральное число, тогда n! (эн-факториал) - это произведение последовательных натуральных чисел от 1 до n. 

Например, 2! = 1 • 2 = 2;    5! = 1 • 2 • 3 • 4 • 5 = 120

     Задача 24. Сколько существует трехзначных чисел, в записи которых цифры 1, 2, 3 встречаются ровно по одному разу?

     Решение. На первое место можно поставить любую из трех цифр, на второе - любую из двух оставшихся, а на третье - последнюю оставшуюся цифру. Таким образом всего получается 3 • 2 • 1 = 3! = 6 чисел.

     Для удобства формулировки задач следующего цикла введем следующее соглашение. Словом будем называть любую конечную последовательность букв русского алфавита. Скажем, используя буквы А, Б, В ровно по одному разу, можно составить 6 слов: АБВ, АВБ, БАВ, БВА, ВАБ, ВБА; используя же букву А дважды, а букву Б один раз - только три слова - ААБ, АБА, БАА. 

     Задача 25. Сколько различных слов можно получить, переставляя буквы в слове "ВЕКТОР"?

     Решение. Поскольку все буквы различны и всего их 6, то получаем ответ: 6! = 720 слов.

     Задача 26. Сколько различных слов можно получить, переставляя буква в слове "ЛИНИЯ"?

     Решение. В этом слове две буквы И, а остальные буквы разные. Приведу один из вариантов рассуждения. Временно будем считать, что буквы И разные: И1 и И2. Тогда получим 5! = 120 разных слов. Однако, те слова, которые получаются перестановкой букв И1 и И2 , на самом деле одинаковы. Таким образом, полученные 120 слов разбиваются на пары одинаковых. Поэтому действительно разных слов всего 120 : 2 = 60.

     Задача 27. Сколько различных слов можно получить, переставляя буква в слове "ПАРАБОЛА"?

     Решение. Считая три буквы А этого слова различными (А1, А2 и А3), получим 8! = 40320 слов. Однако, слова, отличающиеся лишь перестановкой букв А, на самом деле одинаковы. Поскольку буквы А1, А2 и А3 можно переставлять 3! способами, то все 8! слов разбиваются на группы по 3! одинаковых. Поэтому разных слов всего 8!/3! = 6720.

     Задача 28. Сколько различных слов можно получить, переставляя буква в слове "БИССЕКТРИСА"?

     Решение. В этом слове три буквы С и две буквы И. Считая все буквы различными, получаем 11! слов. Отождествляя слова, отличающиеся лишь перестановкой букв И, но не С, получаем 11!/2! различных слов. Отождествляя теперь слова, отличающиеся перестановкой букв С, получаем окончательный результат 11!/(2! • 3!) = 3326400 слов.

Задачи для самостоятельного решения

     Задача 29. На танцплощадке собрались n юношей и n девушек. Сколькими способами они могут разбиться на пары для участия в очередном танце?

     Задача 30. Чемпионат России по шахматам проводится в один круг. Сколько играется партий, если участвуют 18 шахматистов?

     Задача 31. У мамы два яблока, три груши и четыре апельсина. Каждый день в течение 9 дней подряд она дает сыну один из оставшихся фруктов. Сколькими способами это может быть сделано?

     Задача 32. Сколько различных слов можно получить, переставляя буква в слове "МАТЕМАТИКА"?

     Задача 33. Сколькими способами можно поселить 7 студентов в три комнаты: одноместную, двухместную и четырехместную?

     Задача 34. Сколько слов можно составить из пяти букв А и не более чем из трех букв Б?

Ответы и решения

     Задача 29. Первый юноша выбирает из n  девушек (или наоборот!), второй - из n -1, третий - из n - 2 девушек и т.д., то есть получаем произведение n(n-1)(n-2)...3 • 2 • 1 = n!

Ответ: n! пар

     Задача 30. Каждый из 18 участников должен сыграть 17 партий, значит, 18 • 17, но необходимо исключить повторы, получаем (18 • 17)/2 партий.
Ответ: 153 партии

     Задача 31.  Если бы яблоки были по условию разными, груши и апельсины  тоже, то вариантов было бы 9! Но в задаче предполагается, что яблоки одинаковы и способов их выбора - 2!, груши - тоже одинаковы, способов их выбора - 3!, ну и апельсинов - 4!

Исключаем из решения эти повторы, получаем: 9!/2!3!4! = 1260 способов.

    

     Задача 32.  Ответ: 10!/2!2!3! = 151200 различных слов.

     Задача 33. Ответ: 7!/1!2!4! = 105 способов.

     Задача 34. Решение:

1) 5А и 0Б, получаем 1 слово

2) 5А и 1Б, получаем 6!/5!1! = 6 слов

3) 5А и 2Б, получаем 7!/5!2! = 21 слово

4) 5А и 3Б, получаем 8!/5!3! = 56 слов

А всего 1 + 6 + 21 + 56 = 84 слова

Ответ: 84 слова