07. Перестановки
Рассмотрим частный случай, когда k=n. Соответствующее этому случаю размещение называется перестановкой.
Перестановками из n элементов называются такие комбинации, каждая из которых содержит все n элементов и которые отличаются друг от друга лишь порядком расположения элементов.
Поясним это на следующем примере. Из этих трёх элементов: a, b и c. можно составить шесть перестановок: abc, acb, bac, bca, cab, cba. Все приведённые перестановки отличаются друг от друга только порядком их расположения.
Число перестановок n различных элементов обозначают символом Pn и равно
Пример 5.1. Сколькими способами можно расставить девять различных книг на полке, чтобы определенные четыре книги стояли рядом?
Решение. Будем считать выделенные книги за одну книгу. Тогда уже для шести книг существует P6=6!=720 перестановок. Однако четыре определенные книги можно переставить между собой P4=4!=24 способами. По принципу умножения имеем
P6P4 = 720×24 = 17280.
Пример 5.2. Сколько различных четырехзначных чисел можно составить из цифр 0, 1, 2, 3, если каждая цифра в изображении числа встречается один раз?
Решение. Рассматриваемое число может быть представлено как некоторая перестановка из цифр 0, 1, 2, 3, в которой первая цифра отлична от нуля. Так как число перестановок из четырех цифр равно P4=4! и из них 3! перестановок начинаются с нуля, то искомое количество равно
4! – 3! = 3×3! = 3×1×2×3 = 18.
Пример 5.3. Сколькими способами можно посадить за круглый стол n мужчин и n женщин так, чтобы никакие два лица одного пола не сидели рядом?
Решение. Естественно предположить, что как мужчины, так и женщины различимы. Предположим также, что места за столом также различимы. Пронумеруем их. Если женщины займут чётные места n! способами, то мужчины будут занимать нечётные места тоже n! способами и наоборот. По правилу умножения получаем .
Если места за столом неразличимы, то стол можно поворачивать на одно место, то при этом расположение сидящих не изменится (такая ситуация имеет место, например, на карусели).
Вопрос. Сколькими способами можно посадить за круглый стол n супружеских пар, если супруги должны сидеть рядом?
Упражнения
5.1. Сколькими способами можно обить 6 стульев тканью, если имеются ткани 6 различных цветов и все стулья должны быть разного цвета.
Ответ: .
5.2. Дачник выделил на своём участке семь грядок для выращивания овощей, т. к. хочет иметь свои помидоры, огурцы, перец, лук, чеснок, салат и кабачки. Каждый вид должен иметь отдельную грядку. Сколькими способами он может расположить грядки для посадки?
Ответ: .
5.3. Пассажирский поезд состоит из трех багажных вагонов и восьми купированных. Сколькими способами можно сформировать состав, если багажные вагоны должны находиться в его начале?
Ответ: .
5.4. В первенстве края по футболу участвуют 11 команд. Сколько существует различных способов распределения мест в таблице розыгрыша, если на первое место могут претендовать только 4 определенные команды?
Ответ:
5.
5. Сколькими способами можно упорядочить множество {1,2,3,…,2n} так, чтобы каждое чётное число стояло на чётном месте?
Ответ: .
5.6. Четыре мальчика и четыре девочки рассаживаются в ряд на восемь подряд расположенных мест, причем мальчики садятся на четные места, а девочки – на нечетные. Сколькими способами они могут это сделать?
Ответ: .
5.7. Сколькими способами можно посадить за круглый стол трех мужчин и трех женщин так, чтобы никакие два лица одного пола не сидели рядом?
Ответ: .
5.8. На собрании должны выступить 5 человек: А, Б, В, Г, Д. Сколькими способами можно расположить их в списке ораторов, если Б не должен выступать до того, как выступил А? Решите эту же задачу, если Б должен выступить сразу после А.
Ответ: 5!/2=60; 4!=24.
| < Предыдущая | Следующая > |
|---|
Перестановки. Размещения. Сочетания. Урок решения комбинаторных задач презентация, доклад
Перестановки.
Размещения.
Сочетания.
Урок решения комбинаторных задач
9 класс
Пусть имеются три кубика с буквами А, В и С.
Составьте всевозможные комбинации из этих букв.
ABC АСВ
ВСА ВАС
CAB CBA
Эти комбинации отличаются друг от друга только расположением букв (перестановка букв).
А
В
С
Перестановки
Перестановки — это комбинации, составленные из одних и тех же элементов и отличающиеся порядком их следования.
Число всех возможных перестановок элементов обозначается Pn, и может быть вычислено по формуле:
Формула перестановки:
Рn=n!
При перестановке число объектов остается неизменными,
меняется только их порядок
С ростом числа объектов количество перестановок очень быстро растет и изображать их наглядно становится затруднительно.
3 объекта
количество перестановок 6
Рn=n!
Р3=3!=1∙2∙3=6
Задача 1. В турнире участвуют семь команд. Сколько вариантов распределения мест между ними возможно?
Р7=7!=1*2*3*4*5*6*7=5040
Ответ: 5040
Задача 2. Сколькими способами могут разместиться за круглым
столом 10 человек?
Р10 =10! = = 1*2*3*4*5*6*7*8*9*10 = 3628800
Ответ: 3628800
Вычислить: а) 5!
2. В среду в 9 классе 6 уроков: алгебра, русский язык, черчение, биология, химия, обществознание. Сколько вариантов расписания можно составить на среду?
Размещения
Пусть имеется n различных объектов.
Будем выбирать из них m объектов и переставлять всеми возможными способами между собой .
Получившиеся комбинации называются размещениями из n объектов по m, а их число равно:
При размещениях меняется и состав выбранных объектов, и их порядок.
Формула размещения:
n=3 — всего объектов (различных фигур)
m= 2 – выбор и перестановка объектов
3 объекта
Размещение по 2 фигуры
Сколькими способами можно расставить 5 томов на книжной полке, если выбирать их из имеющихся в наличии семи книг?
Ответ: 2520 способов
Вычислить:
2. Найти количество трехзначных чисел с неповторяющимися цифрами, которые можно составить из цифр: 1, 2, 3, 4, 5.
Ответ: 60 чисел
Сочетания
3 объекта
Пусть имеется n различных объектов.
Получившиеся комбинации называются сочетаниями из n объектов по m,
В сочетаниях меняется состав выбранных объектов, но порядок не важен
Задача: Сколькими способами можно распределить три путевки в один санаторий между пятью желающими?
Так как путевки предоставлены в один санаторий, то варианты распределения отличаются друг от друга хотя бы одним желающим. Поэтому число способов распределения
Ответ: 10 способов.
Задача:
Группу из 20 студентов следует рассадить в аудитории по 2 человека за каждой партой. Порядок их размещения не имеет значения. Определить количество возможных вариантов сочетаний.
Ответ: 190
Задача: В цехе работают 12 человек: 5 женщин и 7 мужчин.
Сколькими способами можно сформировать бригаду из 7 человек, чтобы в ней было 3 женщины?
Из пяти женщин необходимо выбирать по три, поэтому число способов отбора .
Так как требуется отобрать четырех мужчин из семи,
то число способов отбора мужчин
Ответ: 350
Скачать презентацию
комбинаторика — В ресторане 16 мужчин и 10 женщин сидят на 26 стульях за круглым столом. Сколько возможных способов, которыми мужчины всегда сидят вместе?
$\begingroup$
В ресторане 16 мужчин и 10 женщин сидят на 26 стульях за круглым столом. Найдите общее количество возможных способов, чтобы 16 человек всегда сидели рядом друг с другом.
Я пришел к решению $16!.10!$ Но я полагаю, что ответ не может быть таким простым, правильный ли мой подход и ответ?
Мне трудно правильно сформулировать решение.
- комбинаторика
6
$\begingroup$
Будет только одна женщина, справа от которой находится мужчина.
Где это происходит, значения не имеет, поскольку мы различаем размещение гостей только по соседям. Теперь откройте круг в этой точке, чтобы сначала была линия из женщин за 10 долларов, а затем очередь из мужчин за 16 долларов.
$\endgroup$
$\begingroup$
Я думаю, что ваше замешательство возникает из-за того, что вам снова и снова повторяли, что если $N$ объектов расположить в ненумерованных кругах из , число размещений равно $(n-1)!$, или эквивалентно, $\dfrac{n!}{n}$, против $n!$ расположений в пронумерованных кругах.
Верно, здесь у нас
Применяя формулу кругового расположения, блоки можно переставить в $(2-1)! \equiv \dfrac{2!}{2}$ способами, но мужчин и женщин можно переставлять в блоках $M!N!$ способами
$\endgroup$
$\begingroup$
На круглом столе $n$ объектов можно расположить $(n-1)!$ способами.
Сначала расставьте всех женщин на круглом столе.
женщины по $10$ можно разместить в $(10-1)! = 9!$ способов на круглом столе.
Теперь нам нужно расположить $16$ мужчин так, чтобы все они были вместе.
Мы можем разместить этих мужчин в любом из 10-долларовых промежутков между женщинами. (Предположим, что мы связали всех мужчин вместе и рассматриваем их как единый элемент).
Для размещения этого элемента (всех человечков) в промежутках по $10$ существует $10$ способов.
Но эти люди также могут изменить свой порядок. Итак, умножьте $10$ на факториал числа мужчин, то есть $16!$.
Таким образом, требуемое количество способов равно $$9! \cdot 10 \cdot 16! = 10! \cdot 16!$$
Следовательно, ваш ответ правильный!
$\endgroup$
Зарегистрируйтесь или войдите в систему
Зарегистрируйтесь с помощью Google
Зарегистрироваться через Facebook
Зарегистрируйтесь, используя адрес электронной почты и пароль
Опубликовать как гость
Электронная почта
Требуется, но никогда не отображается
Опубликовать как гость
Электронная почта
Требуется, но не отображается
Нажимая «Опубликовать свой ответ», вы соглашаетесь с нашими условиями обслуживания, политикой конфиденциальности и политикой использования файлов cookie
2.
8 ШАГ ЧЕТВЕРТЫЙ: Умножение и обозначение вместеПримеры показывают, как работает многоэтапное мышление, когда оно необходимо.
| Пример: В офисе 7 мужчин и 6 женщин. Сколькими способами можно составить комитет из пяти человек, если … а) Пол не имеет значения? б) Комитет должен состоять только из мужчин? в) Комитет должен состоять из 2 мужчин и 3 женщин? |
Ответ: а) Это просто проблема присвоения ярлыков 13 людям: пять «ВКЛ» и восемь «ВЫКЛ». Есть:
\(\dfrac{13!}{5!8!} = \dfrac{13 \cdot 12 \cdot 11 \cdot 10 \cdot 9}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = 13 \cdot 11\cdot 9 = 1287\)
способа составить комитет.
б) Это проблема только среди мужчин: 7 человек должны быть помечены. Есть \(\dfrac{7!}{5!2!}=21\) комитетов.
c) ЭТО ЗАДАЧА С ДВУМЯ ЗАДАЧАМИ!
Задача 1: Разобраться с мужчинами.
\(\dfrac{7!}{2!5!} = 21\) способов
Задача 2: Разобраться с женщинами
\(\dfrac{6!}{3!3!} = 20\) способов
По принципу умножения существует \(21 \times 20 = 420\) способов сформировать комитет.
| Пример: Компания хочет отправить бригаду из пяти сантехников на строительную площадку. Они пришлют двух опытных сантехников и трех сантехников-стажеров. Если имеется в общей сложности 10 опытных сантехников и 8 стажеров, сколько различных команд возможно? |
Ответ : Этот процесс тоже состоит из двух задач:
возможные способы пометить двух опытных сантехников как «избранных», а остальных — как «не выбранных».
Задача 2. Выберите стажеров
Существует \(\dfrac{8!}{3!5!}\) возможных способов пометить трех стажеров как «избранных», а остальных как «не выбранных».
Таким образом, по принципу умножения существует \(\dfrac{10!}{2!8!} \times \dfrac{8!}{5!3!}\) возможных команд.
КОММЕНТАРИЙ. Обратите внимание, что мы не можем контролировать, кого называть «экспертом», а кого «стажером». У нас есть только контроль над ярлыками «выбранный» и «не выбранный». То, что есть некоторые фиксированные ранее назначенные метки, является намеком на то, что можно бороться с многоступенчатой проблемой.
| Пример: Есть: |
20 американцы
10 австралийцы (включая меня, Джеймс)
10 австрийцев
В команду по математике требуется четырнадцать человек. Сколько способов, если …
а) Национальность значения не имеет?
б) В команде должны быть только американцы?
c) В команде должно быть 5 американцев, 5 австралийцев и 4 австрийца?
d) Национальность значения не имеет, но я должен быть в команде?
Ответ:
a) \(\dfrac{40}{14!26!}\) (Вы понимаете почему?)
b) \(\dfrac{20!}{14!6!}\) (Понимаете, почему?)
c) Иметь дело с американцами: \(\dfrac{20!}{5!15! }\).
Разберитесь с австралийцами: \(\dfrac{10!}{5!5!}\). Разберитесь с австрийцами: \(\dfrac{10!}{4!6!}\).
По принципу умножения всего получается \(\dfrac{20!}{5!15!} \times \dfrac{10!}{5!5!} \times \dfrac{10!}{4! 6!} \) способы создать команду.
d) Со мной в команде точно, проблема теперь в том, чтобы выбрать еще 13 членов команды из 39люди. Есть \(\dfrac{39!}{13!26!}\) способы сделать это.
| Пример: Сколькими способами можно расположить буквы АМЕРИКА … |
а) если нет ограничений?
б) если перестановка должна начинаться с М?
в) если перестановка должна начинаться с М и заканчиваться на С?
г) если перестановка должна начинаться с А?
Ответ: a) \(\dfrac{7!}{2!}\) (Почему?)
b) Это всего лишь вопрос размещения букв AERICA в шести слотах:
Существует \(\dfrac{6!}{2!}\) способов.
c) Это вопрос размещения букв AERIA в пяти ячейках:
Есть \(\dfrac{5!}{2!}\) способов.
г) Нам нужно расставить буквы MERICA в шести слотах:
Существует \(6!\) способов.
Часто есть несколько способов продумать задачу.
| Пример: Сколькими способами можно расположить буквы в слове ОРАНЖЕВЫЙ, если первая и последняя буквы должны быть гласными? |
Здесь гласные имеют статус, отличный от согласных. Это означает, что нам, вероятно, нужно думать об этой проблеме поэтапно.
Подход 1:
Задание 1: Разберитесь с гласными.
Из трех гласных одна будет помечена как «в первой позиции», одна как «в последней позиции» и одна как «вместе с согласными». Есть \(\dfrac{3!}{1!1!1!} = 6\) способов сделать это.
Задание 2: Разберитесь с согласными.
У нас есть три согласных и дополнительная гласная, выступающая в роли согласной. Нам нужно пометить их как в позиции 2, в позиции 3, в позиции 4 и в позиции 5. Есть \(\dfrac{4!}{1!1!1!1!} = 24\) способов сделать это .
Таким образом, по принципу умножения существует \(6 \times 24 = 144\) возможных желаемых комбинаций.
Подход 2:
Думайте об этом как о процессе из шести задач: поработайте с первой буквой, поработайте с последней буквой, затем поработайте со второй, третьей, четвертой и пятой буквами. Это дает диаграмму:
| ПРИМЕР: Сколькими способами можно расположить буквы ABCDE так, чтобы A не стояла ни в начале, ни в конце? |
Подход 1: Думайте об этом как о пятиэтапном процессе! Разберитесь с первой буквой, разберитесь с последней буквой, разберитесь со второй буквой, разберитесь с третьей буквой и разберитесь с четвертой буквой.
По принципу умножения умножаем результаты.
Подход 2 : Буквы B, C, D, E имеют статус, отличный от A.
Задача 1: поместите букву A
Есть 3 возможных места для этой буквы
Задача 2: поместите оставшиеся буквы
Есть четыре оставшихся позиции для четырех букв. Их можно разместить в этих позициях \(\dfrac{4!}{1!1!1!1!} = 24\) способов.
Таким образом, существует \(3 \times 24 = 72\) возможных желаемых комбинаций.
Подход 3: Есть пять слотов, в которые можно поместить буквы, причем два крайних слота имеют другой статус, чем три средних.
Задача 1. Заполните концевые прорези.
Есть четыре буквы для работы, что дает \(\dfrac{4!}{1!1!2!} = 12\) возможностей. (Здесь метки «первый слот», «последний слот» и «не используется».)
Задача 2. Заполните три средних слота
Есть три буквы для работы с выходом \(\dfrac{3!} {1!1!1!} = 6\) возможностей.
По принципу умножения имеем \(12 \times 6 = 72 \) допустимых расположений.
НЕКОТОРАЯ ПРАКТИКА:
Все ответы приведены в ДОПОЛНИТЕЛЬНОМ РУКОВОДСТВЕ к этому курсу «Перестановки и комбинации».
| Упражнение 25: Комитет из пяти человек должен быть сформирован из пяти мужчин и семи женщин. |
а) Сколько комитетов можно создать, если пол не имеет значения?
б) Сколько комитетов можно создать, если в комитете должно быть ровно две женщины?
c) Сколько комитетов может быть образовано, если в комитете должен быть один конкретный мужчина, а в комитете не должна быть одна конкретная женщина?
d) ЗАДАЧА: Сколько комитетов можно создать, если одна конкретная пара (один мужчина и одна женщина) не может вместе входить в комитет?
СОВЕТ.
Иногда проще сначала посчитать противоположное желаемому!
Следующие четыре вопроса требуют некоторого ума. Веселитесь с ними!
| Упражнение 26: Есть: |
20 американцев
10 австралийцев (включая меня, Джеймс). Сколько возможных команд включает меня, когда в команде есть американец?
| Упражнение 27: а) Двенадцать белых точек лежат в ряд. Два должны быть окрашены в красный цвет. Сколькими способами это можно сделать? |
б) Рассмотрим уравнение \(10 = x + y + z\). Сколько решений она имеет, если каждая переменная должна быть положительным целым числом или нулем?
Упражнение 28: Прилавок с мороженым предлагает «особое мегачашечку»: двенадцать шариков в миске на выбор из двенадцати возможных вкусов. Сколько различных комбинаций мегачаши он предлагает? |
КОММЕНТАРИЙ: Проблема здесь в том, что совки неразличимы. Более того, вам не говорят, сколько мерных ложек должно быть с определенной этикеткой (вкусом). Подобные проблемы сложны и подпадают под категорию того, что называется «множественный выбор».
СОВЕТ. Упражнение 27 отвечает на следующий вопрос; Десять шариков мороженого лежат в тарелке, каждый шарик одного из трех возможных вкусов. Сколько возможностей может возникнуть?
| Упражнение 29: Рассмотрим вопрос: Сколькими способами 8 человек могут сесть за круглый стол? |
Это расплывчатый вопрос. Что значит «другой»?
a) Ответьте на вопрос, отмечены ли стулья за столом север, северо-восток, восток, юго-восток, юг, …, северо-запад.
b) Ответьте на вопрос, если стулья не помечены так, чтобы два разных поворота при одинаковом расположении людей считались одинаковыми.