на шоу пришли шесть выступающих сколькими способами их можно расставить

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 способов расположения стола относительно сидящих, то предыдущий результат нужно разделить на 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 человек: А, Б, В, Г, Д. Сколькими способами можно расположить их в списке ораторов, если Б не должен выступать до того, как выступил А? Решите эту же задачу, если Б должен выступить сразу после А.

Источник

КОМБИНАТОРИКА

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

Правила сложения и умножения в комбинаторике

Правило суммы. Если два действия А и В взаимно исключают друг друга, причем действие А можно выполнить m способами, а В – n способами, то выполнить одно любое из этих действий (либо А, либо В) можно n + m способами.

Пример 1.

В классе учится 16 мальчиков и 10 девочек. Сколькими способами можно назначить одного дежурного?

Дежурным можно назначить либо мальчика, либо девочку, т.е. дежурным может быть любой из 16 мальчиков, либо любая из 10 девочек.

По правилу суммы получаем, что одного дежурного можно назначить 16+10=26 способами.

Правило произведения. Пусть требуется выполнить последовательно k действий. Если первое действие можно выполнить n₁ способами, второе действие n₂ способами, третье – n₃ способами и так до k-го действия, которое можно выполнить n_k способами, то все k действий вместе могут быть выполнены:

Пример 2.

В классе учится 16 мальчиков и 10 девочек. Сколькими способами можно назначить двух дежурных?

Первым дежурным можно назначить либо мальчика, либо девочку. Т.к. в классе учится 16 мальчиков и 10 девочек, то назначить первого дежурного можно 16+10=26 способами.

После того, как мы выбрали первого дежурного, второго мы можем выбрать из оставшихся 25 человек, т.е. 25-ю способами.

По теореме умножения двое дежурных могут быть выбраны 26*25=650 способами.

Сочетания без повторений. Сочетания с повторениями

Классической задачей комбинаторики является задача о числе сочетаний без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать m из n различных предметов ?

Пример 3.

Необходимо выбрать в подарок 4 из 10 имеющихся различных книг. Сколькими способами можно это сделать?

Нам из 10 книг нужно выбрать 4, причем порядок выбора не имеет значения. Таким образом, нужно найти число сочетаний из 10 элементов по 4:

.

Рассмотрим задачу о числе сочетаний с повторениями: имеется по r одинаковых предметов каждого из n различных типов; сколькими способами можно выбрать m () из этих (n*r) предметов?

.

Пример 4.

В кондитерском магазине продавались 4 сорта пирожных: наполеоны, эклеры, песочные и слоеные. Сколькими способами можно купить 7 пирожных?

Т.к. среди 7 пирожных могут быть пирожные одного сорта, то число способов, которыми можно купить 7 пирожных, определяется числом сочетаний с повторениями из 7 по 4.

.

Размещения без повторений. Размещения с повторениями

Классической задачей комбинаторики является задача о числе размещений без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n различных предметов?

Пример 5.

В некоторой газете 12 страниц. Необходимо на страницах этой газеты поместить четыре фотографии. Сколькими способами можно это сделать, если ни одна страница газеты не должна содержать более одной фотографии?

В данной задаче мы не просто выбираем фотографии, а размещаем их на определенных страницах газеты, причем каждая страница газеты должна содержать не более одной фотографии. Таким образом, задача сводится к классической задаче об определении числа размещений без повторений из 12 элементов по 4 элемента:

Таким образом, 4 фотографии на 12 страницах можно расположить 11880 способами.

Также классической задачей комбинаторики является задача о числе размещений с повторениями, содержание которой можно выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n предметов, среди которых есть одинаковые?

Пример 6.

У мальчика остались от набора для настольной игры штампы с цифрами 1, 3 и 7. Он решил с помощью этих штампов нанести на все книги пятизначные номера– составить каталог. Сколько различных пятизначных номеров может составить мальчик?

Можно считать, что опыт состоит в 5-кратном выборе с возращением одной из 3 цифр (1, 3, 7). Таким образом, число пятизначных номеров определяется числом размещений с повторениями из 3 элементов по 5:

.

Перестановки без повторений. Перестановки с повторениями

Классической задачей комбинаторики является задача о числе перестановок без повторения, содержание которой можно выразить вопросом: сколькими способами можно разместить n различных предметов на n различных местах?

Пример 7.

Сколько можно составить четырехбуквенных «слов» из букв слова«брак»?

Генеральной совокупностью являются 4 буквы слова «брак» (б, р, а, к). Число «слов» определяется перестановками этих 4 букв, т. е.

Для случая, когда среди выбираемых n элементов есть одинаковые (выборка с возвращением), задачу о числе перестановок с повторениями можно выразить вопросом: сколькими способами можно переставить n предметов, расположенных на n различных местах, если среди n предметов имеются k различных типов (k

Пример 8.

Сколько разных буквосочетаний можно сделать из букв слова «Миссисипи»?

Здесь 1 буква «м», 4 буквы «и», 3 буквы «c» и 1 буква «п», всего 9 букв. Следовательно, число перестановок с повторениями равно

ОПОРНЫЙ КОНСПЕКТ ПО РАЗДЕЛУ «КОМБИНАТОРИКА»

Источник

Практическое занятие на тему «Основные комбинаторные конфигурации»

Ищем педагогов в команду «Инфоурок»

Практическое занятие (2ч.)

Тема: Основные комбинаторные конфигурации .

научить применять комбинаторные конфигурации при решении задач;

сформировать умение находить нужную комбинаторную формулу при решении задачи;

формирование самостоятельности студента на занятии.

Математика / приложение к газете «Первое сентября», №15, 2004 г.

Стойлова Л.П. Математика.-М.: Изд. Центр Академия, 1997.

Прикладная комбинаторная математика.

Вариативная самостоятельная работа.

Повторение основных формул необходимых при решении комбинаторных задач.

Размещения с повторениями.

Задача 1. Сколько различных четырехзначных чи­ сел можно составить из цифр 2, 6, 7, 8 и 9, если каждая цифра может входить в комбинацию несколько раз?

Решение. Здесь порядок цифр существенен (2678 или 6278 — это разные числа). Поэтому имеем дело с кортежем длины 4 (четырехзначное число), каждый элемент которого можно выбрать пятью способами (цифр дано пять). Поэтому число различных комби­ наций равно 4 5 = 1024.

Задача 2. На референдуме предложены четыре вопроса, на которые надо ответить «да» или «нет». Сколько есть возможностей заполнения бюллетеня (на все вопросы надо дать ответ)?

Решение. Получаем кортеж длины 4 (столько во­ просов в бюллетене), каждый элемент может быть вы­ бран двумя способами («да» или «нет»). Поэтому число различных возможностей равно 2 4 =16.

Задача 3 . Неудовлетворенные решением Париса Гера, Афина и Афродита обратились к трем мудре­ цам с просьбой назвать прекраснейшую из них. Каж­ дый из мудрецов высказал свое мнение. Сколько мог­ ло возникнуть вариантов ответа на поставленный во­ прос у этой тройки?

Решение. Здесь вновь кортеж длиной 3 (три муд­ реца), каждый элемент которого может быть выбран шестью способами. Поэтому число различных возмож­ ностей равно 6 3 = 216.

Задача 5. На железнодорожной станции имеется я семафоров. Сколько может быть дано различных сигналов при помощи этих семафоров, если каждый семафор имеет три состояния: горит либо зеленый, либо желтый, либо красный свет.

Задачи для домашней работы

Сколько букв русского алфавита можно зако дировать, используя лишь комбинации точек и тире, содержащие только три знака?

Переплетчик должен переплести 12 различных книг в красный, зеленый и коричневый переплеты. Сколькими способами он может это сделать?

Задача 1. Из спортивного клуба, насчитывающего 30 членов, надо составить команду из четырех чело­ век для участия в эстафете на 100 + 200 + 400 + 800 (м). Сколькими способами это можно сделать?

Решение. Имеем кортежи длиной 4. Ни один эле­мент не может входить дважды (один бегун на один отрезок дистанции). Значит,

А 4 ₃₀ = =27·28·29·30 = 657 720.

Решение. Имеем кортежи длиной 3 (у треугольни­ка три вершины). Ни один элемент не может входить дважды. Значит,

А 3 ₅₌

Задачи для домашней работы

Сколько всего различных пятизначных чисел, не содержащих нуля?

В классе изучают девять предметов. Скольки ми способами можно составить расписание на поне­ дельник, если в этот день должно быть шесть разных уроков?

Перестановка без повторений.

Задача 1. Сколькими способами можно перестав­ лять друг с другом цифры 1, 2, 3 и 4?

Задача 2. За столом пять мест. Сколькими спосо­ бами можно рассадить пятерых гостей?

Задача 3. У Лены есть восемь разных красок. Она хочет написать ими слова «Новый Год». Сколькими способами она может это сделать, если каждая буква должна быть раскрашена одним цветом и все восемь букв должны быть разными по цвету?

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

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

Решение. Р(2, 3) = 10.

Задача 2. Сколькими способами можно положить 28 различных открыток в четыре одинаковых кон­ верта так, чтобы в каждом конверте было по семь открыток?

Решение. Пометим конверты цифрами 1, 2, 3 и 4. Тогда число различных раскладок равно

Р(7, 7, 7,7)=.

Сотрем пометки. Теперь конверты можно произволь­ но переставлять друг с другом, не меняя результата раскладки (теперь они неотличимы друг от друга). Так как число различных перестановок четырех кон­ вертов равно

Р ₄ = 4!, то число различных раскладок уменьшается в

Р ₄ = 4! раз и поэтому оно равно

Ответ:

Задачи для домашней работы

Сколько различных слов можно получить, пе реставляя буквы слова «ингредиент»?

Сколькими способами можно посадить за круг­ лый стол пять мужчин и пять женщин так, чтобы никакие два лица одного пола не сидели рядом?

Автомобильные номера состоят из четырех цифр и трех букв. Найдите число таких номеров, если ис­пользуются 32 буквы русского алфавита.

Сочетание с повторениями.

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

Решение. Здесь рассматриваются сочетания с по­ вторениями из 4 (четыре вида пирожных) по 7 (столько пирожных покупают). Значит,

Ответ: 120 способов.

Задача 2. В почтовом отделении продают открыт­ ки 10 видов. Сколькими способами можно купить в нем 12 открыток?

Решение. Здесь рассматриваются сочетания с по­ вторениями из 10 по 12. Имеем

Сочетания без повторений.

Задача 1. Сколькими способами в игре «Спортло­ то» можно выбрать шесть номеров из 49?

Решение. Здесь рассматриваются сочетания без повторения (одно число может быть по правилам игры выбрано не более одного раза) из 49 по 6.

Решение. Здесь рассматриваются сочетания без повторений.

Задача 3. Дама сдавала в багаж семь предметов, Все они оказались украденными, но два каких-либо (по ее выбору) ей согласились поискать. Сколько у нее есть возможностей выбрать два любимых предме­ та?

Задача 4. В прошлые века процветала генуэзская лотерея, сохранившаяся в некоторых странах и по­ныне. Участники этой лотереи покупали билеты, на которых стояло число от 1 до 90. Можно было ку­ пить и билеты, на которых было сразу 2, 3, 4 и 5 чисел. В день розыгрыша лотереи из мешка, содер­жащего жетоны с числами от 1 до 90, вынимали пять жетонов. Выигрывали те, у которых все номера на билетах были среди вынутых. Если участник лотереи покупал билет с одним из чисел, то он получал при выигрыше в 15 раз больше стоимости билета; если с двумя числами (амбо), то в 270 раз больше, если с тремя числами (терн) – в 5500 раз больше, если в четырьмя числами (катерн) – 75000 раз больше, а если с пятью числами (квин) – в 1000 000 раз больше, чем стоит билет. Каково отношение «счастливых» билетов при игре, когда участник купил билет с одним числом?

Решение. Общее число исходов находится из формулы сочетаний без повторений:

С 5 ₉₀ =

Если участник купил билет с одним номером, то для выигрыша необходимо, чтобы один из вынутых номеров совпал с номером на билете. Остальные 4 номера могут быть благоприятными. Но эти 4 номера выбираются из оставшихся 89 номеров. Поэтому число благоприятных комбинаций к общему числу комбинаций равно

Ответ:

Задачи для домашней работы

Сочетайте, каково отношение «счастливых» билетов при игре, когда участник купил билет с двумя числами.

Сколькими способами можно составить набор из восьми пирожных, если имеется четыре сорта пирожных?

В классе имеется шесть сильных математиков. Сколькими способами из них можно составить команду на районную олимпиаду по математике, если от класса можно послать команду из четырех человек?

Источник

Инструменты пользователя

Инструменты сайта

Боковая панель

Навигация

Загрузки всякие

Связь

Содержание

Комбинаторика (задачи)

Задача

Сколько шестизначных чисел можно составить из двух 5 и четырех 7.

Перестановки, отличающиеся друг от друга лишь расположением элементов 55, совпадают. Таких перестановок будет 2!

Перестановки, отличающиеся друг от друга лишь расположением элементов 7777, совпадают. Таких перестановок будет 4! Итого 6! / (2!4!) = 1*2*3*4*5*6 / (1*2*1*2*3*4) = 15

Задача

Сколько разных пятизначных чисел можно записать с помощью цифр 0, 2, 4, 6, 8 без их повторения?

Р5 – Р4 = 5! – 4! = (5-1) * 4! = 96 (разных пятизначных чисел)

Задача

Сколько разных пятизначных чисел можно записать с помощью цифр 1, 2, 3, 4, 5, 6, 7, 8, 9 без их повторения?

C_9^5 = 126 (разных пятизначных чисел)

Задача

Сколькими способами могут занять первое, второе и третье места 8 участниц финального забега на дистанции 100 м?

$A_8^1 A_7^1 A_6^1 = 8 \cdot 7 \cdot 6=336$

Задача

Сколькими способами может расположиться семья из трех человек в четырехместном купе, если других пассажиров в купе нет?

Задача

Сколько существует семизначных телефонных номеров, в которых все цифры разные и первая цифра отлична от нуля?

Задача

Ольга помнит, что телефон подруги оканчивается тремя цифрами 5, 7, 8 но забыла, в каком порядке эти цифры расположены. Укажите наибольшее число вариантов, которые ей придется перебрать, чтобы дозвониться подруге. [Перестановки]

Р3 = 3! = 6 вариантов

Задача

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

Задача

Во время встречи 16 человек пожали друг другу руки. Сколько всего сделано рукопожатий?

$A_<16>^2 / 2 = 15+14+\ldots+1 = 120$

Задача

Группа учащихся из 30 человек решила обменяться фотографиями. Сколько всего фотографий необходимо было для этого?

Задача

При окончании деловой встречи специалисты обменялись визитными карточками. Сколько всего визитных карточек перешло из рук в руки, если во встрече участвовали 6 специалистов?

Задача

Сколько существует вариантов рассаживания вокруг стола 6 гостей на 6 стульях?

P6 = 6! = 1·2·3·4·5·6 = 720.

Задача

Сколько прямых линий можно провести через 8 точек, из которых никакие три не лежат на одной прямой?

$C_<8>^2 = 8!/2!/6! = 28$ (прямых линий)

Задача

Определите число всех диагоналей правильного: 1) пятиугольника; 2) восьмиугольника; 3) двенадцатиугольника; 4) пятнадцатиугольника.

Ответ: 10, 66, 28, 105

Задача (принцип Дирихле)

Задача 3. В мешке 50 шаров, отличающихся только цветом: 8 красных, 9 синих, 9 желтых, остальные – поровну черные и белые. Какое наименьшее число шаров надо вынуть из мешка, не видя их, чтобы среди них было не менее 7 шаров одного цвета?

Сначала заметим, что черных и белых шаров по (50−8−9−9)/2=12>7. Если взять всего 30 шаров, то может получиться так, что мы взяли только по 6 шаров каждого цвета. Значит, нужно брать больше 30 шаров. Попробуем вытянуть 31 шар. Тогда по принципу Дирихле, если роль «клеток» играют цвета, а роль «кроликов» вытянутые шары, получаем, что какие бы мы ни вытащили шары, среди них обязательно найдется по крайней мере 7 шаров одного цвета (31=5⋅6+1).

Задача (принцип Дирихле)

Задача 4. 15 футбольных команд (в каждой по 11 человек) летят из Москвы в Санкт-Петербург на соревнования. Какое минимальное количество мест может быть в самолете, чтобы гарантированно нашлась команда, долетевшая в полном составе?

Если в самолете будет всего 150 мест, то можно будет посадить в него по 10 человек от каждой из 15 команд, тогда самолет будет заполнен целиком, но в нем не будет ни одной команды в полном составе. Значит, нужен с самолет больше, чем со 150 местами. Рассмотрим самолет, в котором 151 место. Тогда по принципу Дирихле, если роль «клеток» играют команды, а роль «кроликов» футболисты, получаем, что как бы ни произошла рассадка футболистов, среди пассажиров самолета обязательно найдется хотя бы одна команда, летевшая в полном составе (151=15⋅10+1).

Задача

Задача 5. Сколько чисел от 1 до 9999 (включая 1 и 9999) не имеют в своей десятичной записи одинаковых подряд идущих цифр? (к примеру, не подходят 1488, 2259, 3233)

Задача

Задача 1. Есть 10 различных марок шоколада. Количество способов подарить трём девочкам по шоколадке равно?

Задача

Задача 3. Сколькими способами можно вручить призы в 5 различных номинациях (в каждой номинации только один приз), если в соревновании участвуют 10 человек?

Задача

Задача 4. Сколькими способами можно вручить призы в 5 различных номинациях (в каждой номинации только один приз), если в соревновании участвуют 10 человек, при условии, что каждый участник может получить не более одного приза?

Задача

Задача 8. Группа из 8 студентов пришла в столовую. Сколькими способами они могут занять очередь друг за другом, если Маша и Таня хотят стоять рядом, а Коля не хочет быть последним?

Так как Маша и Таня хотят стоять рядом, то можно считать, что они занимают одно место вдвоём. Соответственно, мест становится 7, но надо учесть, что девочки могут между собой поменяться местами (Маша-Таня и Таня-Маша). Поэтому количество всех очередей надо будет удвоить.

Коля не хочет быть последним, поэтому для него есть 6 возможных мест в очереди. Остальные могут занять места 6⋅5…1=6! способами.

В итоге получаем, что количество способов занять очередь равно 2⋅6⋅6!=8640.

Источник