Сочетания и размещения 11 класс онлайн-подготовка на Ростелеком Лицей
Размещение
Задача
В чемпионате России по футболу участвуют 16 команд. Сколькими способами можно предсказать тройку призеров?
Решение
Данная задача решается способом произведения. На первое место можно выбрать 16 вариантов, на второе только 15 оставшихся, на третье, соответственно, 14. Итого:
Задачи подобного типа, где из вариантов нужно выбрать , причем порядок их следования важен (в данном случае важно, кто займет первое место, кто второе, кто третье) называются размещением:
Задача
У девочки Ксюши есть 5 поклонников. Она хочет сходить вечером на два фильма, причем не с одним и тем же поклонником. Сколькими способами можно сделать выбор?
Решение
В данной задаче порядок важен. Поэтому используем формулу размещения:
С другой стороны, можно воспользоваться правилом произведения.
На первый фильм есть пять вариантов, на второй 4, итого:
Перестановка
Рассмотрим частный случай размещения, когда из элементов нужно выбрать все элементов, порядок по-прежнему важен. Такой частный случай называется перестановкой:
Задача
Сколькими способами можно расставить класс из 30 человек в шеренгу?
Решение
В данном случае имеем частный случай размещения – перестановку. Так:
Уравнения в комбинаторике
Пример
Здесь очевидны некоторые ограничения: – иначе не имеет смысла выражение , кроме того,
Остается решить обыкновенное квадратное уравнение: ; .
Второй корень не подходит исходя из ограничений.
Ответ: .
Размещение при наличии одинаковых объектов
Пример
Сколько существует способов переставить буквы в слове стол? В слове каша?
Решение
Очевидно, что в первом случае это число перестановок: .
Во втором же случае следует обратить внимание на то, что некоторые буквы совпадают. Для решения поставим буквам индексы 1 и 2 – теперь это разные буквы и .
Теперь ответ такой же, как и в первом случае –
Теперь отметим, что каждой перестановке слова соответствует такая же перестановка, где буквы стоят наоборот: .
Так, ответ на поставленный вопрос: .
Интересно знать!
Пример
Найти количество способов переставить буквы в слове молоко.
Решение
По аналогии пронумеруем буквы , тогда количество перестановок
Теперь проанализируем. Для каждого варианта перестановки существует ряд вариантов, которые отличаются только индексам букв . найдем количество этих вариантов. Очевидно, что это число перестановок
Так, ответ в задаче:
Пример
Найти количество способов переставить буквы в слове математика.
Решение
Здесь повторяются три комплекта букв.
Решим задачу в три этапа. Сначала по аналогии с предыдущими случаями нумеруем все повторяющиеся буквы – отдельно буквы , отдельно , отдельно : .
В этом слове количество перестановок
Теперь разберемся с буквами . для каждого варианта перестановки есть такой же, который отличается индексами букв . тогда искомое количество перестановок уменьшится в два раза: .
Аналогично для букв : .
Для букв количество вариантов уменьшится в раз.
Итого:
Сочетание
Пример
В поход пошло 4 человека. Сколькими способами можно выбрать пару дежурных, которые утром приготовят завтрак?
Решение
При первом взгляде на задачу кажется, что ответом будет количество размещений .
Обратим внимание, что порядок в данном случае не важен, то есть пара дежурных Вася и Петя или пара Петя и Вася – это одна и та же пара, два варианта превращаются в один, поэтому искомое количество вариантов:
Задачи такого типа, где порядок не важен, называются задачами о сочетаниях – в них требуется выбрать группу объектов, порядок которых не важен.
Определение
Сочетанием из элементов по называется любой выбор из элементов элементов, при этом порядок выбора не важен. Иногда сочетание называют выборкой. Число сочетаний вычисляется по формуле:
Очень важно понимать, когда порядок важен, а когда нет. В примере про дежурных порядок не важен, но если немного поменять условие: выбрать дежурных так, чтобы один отвечал за костер, а второй за мытье посуды – то порядок уже будет важен.
Решение примеров
Пример
В команде 11 человек, нужно выбрать капитана и вице-капитана. Сколькими способами это можно сделать?
Решение
Очевидно, что в данном случае порядок важен, поэтому ответом будет размещение: .
Пример
В команде из 11 человек нужно выбрать пару защитников. Сколькими способами это можно сделать?
Решение
Здесь порядок не важен – в паре защитников не имеет значения, кто первый, а кто второй, поэтому здесь ответом будет число сочетаний: .
Пример
Сколько способов существует составить трехцветный полосатый флаг (полосы горизонтальные), если есть 6 полос различных цветов?
Решение
В данном случае порядок важен, так как, например, выбрав белый, синий и красный, в зависимости от порядка можем получить флаг России или флаг Сербии. Поэтому здесь имеем число размещений: .
Пример
Сколькими способами учитель может выбрать две задачи из 20 для контрольной работы?
Решение
Здесь порядок не важен, не важно какая задача будет первой, а какая второй, поэтому ответ – число сочетаний: .
Вывод
Итак, мы вспомнили понятия перестановки, размещения, сочетания, формулы для вычислений и определения, а также решили несколько примеров.
Список литературы
1. Мордкович А.Г. Алгебра и начала математического анализа. – 10-е изд. – М.: Мнемозина, 2009. – 399 с.
2. Муравин Г.К., Муравина О.
В. Алгебра и начала математического анализа. – М.: Дрофа, 2013.
3. Колмогоров А.Н., Абрамов А.М., Дудницын Ю.П. и др. Алгебра и начала математического анализа. – М.: Просвещение, 2011.
4. Алимов А.Ш. Алгебра и начала математического анализа. – 18-е изд. – М.: Просвещение, 2012.
Дополнительные рекомендованные ссылки на ресурсы сети Интернет
1. Единая коллекция ЦОР (Источник)
2. Интернет-сайт hijos.ru (Источник)
3. Интернет-сайт 100formul.ru (Источник)
Домашнее задание
1. Сколькими способами можно рассадить 5 человек за столом?
2. Сколько четырехзначных чисел можно составить из четырех карточек с цифрами 0, 5, 7, 9?
3. В ящике находится 15 деталей. Сколькими способами можно взять 4 детали?
4. Сколькими способами из колоды в 36 карт можно выбрать 3 карты?
5. В шахматном турнире участвует человек и каждый с каждым играет по 1 партии. Сколько всего партий сыграно в турнире?
Круговые перестановки
- Авторы
- Руководители
- Файлы работы
- Наградные документы
Евсюкова Д.
С. 1
1МБОУ «СОШ № 2 ст. Архонская»
Уймина Т.А. 1
1МБОУ «СОШ № 2 ст. Архонская»
Автор работы награжден дипломом победителя III степени
Диплом школьникаСвидетельство руководителя
Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке «Файлы работы» в формате PDF
Введение
В школьном курсе понятие «круговые перестановки» встречается в 7 классе в учебнике по алгебре в разделе «Для тех, кому интересно» [3].
В комбинаторных задачах часто ставится вопрос о том, сколькими способами можно расположить в ряд, или, как говорят математики, упорядочить, все элементы некоторого множества.
Из истории комбинаторики
Комбинаторика занимается различного вида соединениями, которые можно образовать из элементов конечного множества. Некоторые элементы комбинаторики были известны в Индии еще во II в. до н. э. Индийцы умели вычислять числа, которые сейчас называют “сочетания”. В ХII в. Бхаскара вычислял некоторые виды сочетаний и перестановок. Предполагают, что индийские ученые изучали соединения в связи с применением их в поэтике, науке о структуре стиха и поэтических произведениях. Например, в связи с подсчетом возможных сочетаний ударных (долгих) и безударных (кратких) слогов стопы из п слогов. Как научная дисциплина, комбинаторика сформировалась в ХVII в. В книге “Теория и практика арифметики” (1656 г.) французский автор Андре Таке также посвящает сочетаниям и перестановкам целую главу.
Б. Паскаль в “Трактате об арифметическом треугольнике” и в “Трактате о числовых порядках” (1665 г.) изложил учение о биномиальных коэффициентах.
П. Ферма знал о связях математических квадратов и фигурных чисел с теорией соединений. Термин “комбинаторика” стал употребляться после опубликования Лейбницем в 1665 г. работы “Рассуждение о комбинаторном искусстве”, в которой впервые дано научное обоснование теории сочетаний и перестановок. Изучением размещений впервые занимался Я. Бернулли во второй части своей книги “Агs сопjесtапdi” (искусство предугадывания) в 1713 г. Современная символика сочетаний была предложена разными авторами учебных руководств только в ХIХ в [4].
Все разнообразие комбинаторных формул может быть выведено из двух основных утверждений, касающихся конечных множеств — правило суммы и правило произведения. При решении задач на перестановки используется правило умножения.
Перестановки
Каждое расположение элементов множества в определенном порядке называют перестановкой. Рассмотрим задачу: В турнире четверо участников. Сколькими способами могут быть распределены места между ними?
Будем рассуждать в соответствии с правилом умножения.
Первое место может занять любой из четырех участников. При этом второе место может занять любой из трех оставшихся, третье любой из двух оставшихся, а на четвертом месте останется последний участник. Значит, места между участниками могут быть распределены 4۰3۰2۰1 = 24 способами. Решив задачу, мы фактически подсчитали число перестановок для множества из четырех элементов. Рассуждая точно так же, можно показать, что для множества из пяти элементов число перестановок равно 5۰4۰3۰2۰1, а для множества из десяти элементов это число равно 10۰9۰8۰7۰б۰5۰4۰3۰2۰1.
Вообще если множество содержит п элементов, то число перестановок равно произведению п(п – 1)(п – 2)۰…۰2۰1. Множители в этом произведении можно записать в обратном порядке: 1۰2۰…۰(п – 2)(п – 1)п.
Такие произведения бывают очень длинными и часто выражаются огромными числами. Однако в математике есть специальный символ для их обозначения. Произведение всех натуральных чисел от 1 до п обозначают п! (читают: «п факториал»).
Значение выражения п! можно найти для любого натурального числа
Факториалы растут удивительно быстро. Можно понаблюдать за их изменением, рассмотрев таблицу, в которой приведены факториалы чисел от 1 до 10:
|
п |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
п! |
1 |
2 |
6 |
24 |
120 |
720 |
5040 |
40320 |
362880 |
3628800 |
А значение выражения 15!, которого нет в таблице, превосходит 1012, а именно:
Может быть, именно из-за быстрого роста факториалов восхищенный изобретатель этого выражения использовал восклицательный знак.
С помощью символа п! принято записывать формулу для подсчета числа перестановок. Число перестановок для множества из п элементов обозначают через Рп (читают: «Р из п», Р — первая буква французского слова permutatiоп — перестановка). Тогда Рn = n![3].
Круговые перестановки
Иногда условие задачи можно понять по-разному, и тогда при переводе условия на математический язык получаются разные задачи, в которых не совпадают ни решения, ни ответы. И это вовсе не значит, что один из получившихся ответов правильный, а другой нет [3].
Исследуем эту проблему на примере комбинаторных задач на «перестановки по кругу». Этот нелегкий вопрос будет нагляднее и проще, если прибегнуть к сюжету из знаменитой басни И.
А. Крылова «Квартет». Пусть Мартышку, Козла, Осла и Мишку нужно рассадить за круглым столом, вокруг которого стоят четыре стула под номерами 1, 2, 3 и 4. Если нам важно, кто на каком стуле сидит, то существует 4۰3۰2۰1 = 4! = 24 способа их расположения за столом [2].
Рассмотрим похожую задачу, рассмотрев различные случаи.
Сколько существует вариантов расположения шести гостей за шестиместным столом?
Эта задача имеет разные решения и соответственно разные ответы в зависимости от того, что понимать под различным расположением гостей за столом.
Если считать, что нам важно, кто на каком стуле сидит, то это простая задача на перестановки, и всего будет 6! = 720 различных вариантов посадить гостей за стол.
Однако часто бывает важно не то, кто какой стул занял, а то, кто с кем сидит рядом, т. е. взаимное расположение гостей.
Э то уже совсем другая задача. Теперь расположения, получаемые одно из другого при одновременном перемещении всех гостей вокруг стола без изменении их взаимного расположения, надо считать одинаковыми.
Ясно, что для любого расположения гостей таких одинаковых вариантов, получаемых один из другого поворотом, шесть. Значит, 6! надо разделить на 6. Так как 6! : 6 = 5!, то получается только 120 различных вариантов.
Н о если нас интересует только взаимное расположение гостей, то одинаковыми можно считать и такие симметричные расположения, при которых у каждого гостя остаются те же соседи за столом, только левый и правый соседи меняются местами.
При таком понимании общее число различных расположений гостей вокруг стола будет еще вдвое меньше: 120 : 2 = 60.[3]
Решение задач
Задача 1. Сколькими способами десять приятелей могут сесть на десятиместную карусель?
Решение. Если считать, что карусель состоит из разных предметов, то задача сводится к подсчету числа перестановок. Количество вариантов равно 10! = 3628800.
Если карусель состоит из одинаковых предметов, то безразлично, кто какое место занял.
В этом случае нас интересует лишь, взаимное расположение приятелей, и вариантов будет = 9! = 362880 (Любое расположение приятелей и варианты, получающиеся поворотами, следует считать одинаковыми.)
Задача 2. Сколько ожерелий можно составить из 20 различных бусин?
Решение. Поскольку бусы можно не только поворачивать по кругу, но и переворачивать, различных ожерелий получится [3].
Задача 3. Сколькими способами можно разместить за столом, на котором поставлено 10 приборов, 10 человек — 5 юношей в 5 девушек так, чтобы девушки чередовались с юношами?
Решение. Занумеруем места за столом последовательно числами от 1 до 10. допустим, что юноши сидят на нечетных местах, а девушки на четных. Существует
Р5 = 5! = 120 способов рассадить юношей на нечетных местах и столько же способов размещения пяти девушек на четных местах. Каждый способ размещения юношей можно скомбинировать с любым способом размещения девушек, поэтому получаем всего («правило перемножения возможностей»!) 120 ۰120 = 14 400 способов размещения.
Столько же существует способов размещения в случае, когда юноши сидят на четных местах. Всего получается 28 800 способов [1].
Задача о нашем классе. Мы готовимся к школьному конкурсу танцев. Выбирая танец, все остановились на вальсе, поэтому участников танца нужно было разбить на пары. Было решено, что пар будет 8, так как набралось именно такое количество учащихся среднего роста. И вот тут возникла самая главная проблема: кого с кем ставить в пары, располагая их по кругу, и на какое место поставить каждую пару? Я решил подсчитать все возможные случаи, используя круговые перестановки.
Решение. Чтобы перебрать все возможные пары «мальчик-девочка», нужно найти
8! = 40320. Теперь расставим пары в определённом порядке по кругу:
8! : 8 = 5040 вариантов. Получив такой ответ, все были удивлены, поэтому ограничились вариантом, предложенным нашей классной.
Заключение
Надеюсь, что рассмотренные в работе задачи и примеры убеждают нас в том, что Рассматриваемый метод круговых перестановок является одним из способов решения комбинаторных задач на расположение элементов множества в определённом порядке.
Использование данного способа позволяет решать некоторые задачи нетрадиционным методом, а иногда и упрощают их решение, обогащает арсенал средств, используемых при их решении.
Их использование развивает нестандартное мышление и даёт возможность решения некоторых практических задач оригинальным способом.
Литература:
1. Гусев В. А., Орлов А. И., Розенталь А. Л. Внеклассная работа по математике. – М.: Просвещение, 1977.
2. Дорофеев Г. В., Минаева С. С., Суворова С. Б. Алгебра: 7 класс. Книга для учителя. — М.: Просвещение, 2008.
3. Дорофеев Г. В., Суворова С. Б. и др. Алгебра: учебник для 7 класса общеобразовательных учреждений. — М.: Просвещение, 2008.
4. Перестановки, размещения, сочетания http://collection.edu.yar.ru/dlrstore/
Просмотров работы: 3282
перестановок и комбинаций – круговые перестановки: примеры
В этом уроке я рассмотрю несколько примеров, связанных с круговыми перестановками.
Пример 1 Сколькими способами можно рассадить 6 человек за круглым столом?
Решение Как обсуждалось в уроке, количество способов будет (6 – 1)! или 120 .
Пример 2 Найдите количество способов, которыми 5 человек A , B , C , D и E могут сидеть за круглым столом, так что
(i)
(i) A7 всегда сидят вместе.
(ii) C и D никогда не ставятся вместе.
Решение (i) Если мы хотим разместить A и B вместе во всех расстановках, мы можем рассматривать их как одно целое вместе с 3 другими. Таким образом, фактически мы должны организовать 4 человек по кругу, количество путей (4 – 1)! или 6 .
Давайте взглянем на эти расположения:
Но в каждом из этих расположений A и B могут поменяться местами 2 способов. Вот о чем я:
Следовательно, общее количество способов будет 6 х 2 или 12 .
(ii) Число способов в этом случае будет получено удалением всех тех случаев (из общего числа возможных), в которых C и D вместе. Общее количество путей будет (5 – 1)! или 24 . Аналогично (i) выше, количество ящиков, в которых C и D сидят вместе, будет 12 . Следовательно, необходимое количество путей будет 24 – 12 или 12 .
Пример 3 Сколькими способами можно рассадить 3 мужчин и 3 женщин за круглым столом так, чтобы ни один мужчина не сидел вместе?
Решение Поскольку мы не хотим, чтобы мужчины сидели вместе, единственный способ сделать это — заставить мужчин и женщин сидеть попеременно.
Сначала мы посадим 3 женщин на альтернативные места, что можно сделать в (3 – 1)! или 2 способов, как показано ниже. (Другие 3 мест пока игнорируем.)
Обратите внимание, что следующие варианты 6 эквивалентны:
аранжировка остается точно такой же. Поэтому у нас всего 2 расположения, как показано на предыдущем рисунке.
Теперь, когда мы это сделали, 3 мужчин могут занять оставшиеся места в 3! или 6 способов. Обратите внимание, что сейчас мы не использовали формулу для круговых расположений. Это потому, что после того, как женщины сядут, сдвиг каждого из мужчин на 2 мест даст другое расположение. После фиксации положения женщин (так же, как «нумерация» мест) расположение остальных мест эквивалентно линейному расположению.
Следовательно, общее количество путей в этом случае будет 2! х 3! или 12 .
Надеюсь, теперь вы имеете некоторое представление о круговых схемах. Следующий урок познакомит вас с комбинациями или выборками.
Есть два разных круглых стола, каждый на 5 мест, сколькими способами можно рассадить группу из 10 человек
Словесная задача
Джошуа М.
спросил 28.11.13перестановки и комбинации
Подписаться І 3
Подробнее
Отчет
2 ответа от опытных наставников
Лучший Новейшие Самый старыйАвтор: Лучшие новыеСамые старые
Ричард П. ответил 28.11.13
Репетитор
4.9(813)
Репетитор по математике и естественным наукам округа Фэрфакс
Об этом репетиторе ›
Об этом репетиторе ›
Если порядок рассадки вокруг каждого стола не имеет значения, эта проблема сводится к количеству способов, которыми можно выбрать 5 человек из группы из 10 человек.
Короткий способ сказать это: «Десять выбирают пять».
Логика здесь такова, что после выбора первого стола оставшиеся люди должны перейти ко второму столу.
Это число является комбинаторным коэффициентом 10!/[ 5! (10-5)!] (x! обозначает x факториал)
Это дает 252
. номер 4! = 24. На самом деле нужно дважды умножить на 24, по одному разу для каждой таблицы.
Таким образом, если порядок рассадки имеет значение, то ответ будет 252 x 24 x 24 = 145152
Голосовать за 1 Понизить
Подробнее
Отчет
Вивиан Л. ответил 28.11.13
Репетитор
3 (1)
Microsoft Word/Excel/Outlook, составление эссе, математика; Я ЛЮБЛЮ УЧИТЬ
Смотрите таких репетиторов
Смотрите таких репетиторов
Привет, Джошуа;
Наличие двух таблиц не имеет значения.