За столом пять мест сколькими способами можно рассадить пятерых гостей

Комбинаторика (стр. 3 )

Из за большого объема этот материал размещен на нескольких страницах: 1 2 3 4

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

Решение. Р4 = 4! = 24.

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

Решение. Р5 = 5! = 120.

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

Решение. Присвоим каждой краске номер от 1 до 8. Тогда каждый искомый способ задается перестанов­кой восьми чисел 1, 2,…, 8. Значит, таких переста­новок 8!. Поэтому она может написать «Новый Год» 8! = 40 320 способами.

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

ОПРЕДЕЛЕНИЕ. Пусть дан кортеж длины п, состав­ленный из элементов множества X = <х1,…, xk>. При­чем буква х1 входит в этот кортеж n1, раз,…, буква xk — пk раз. Тогда п = n1 + . + nk.. Если переставлять в этом кортеже буквы, то будут получаться новые кортежи, имеющие тот же состав. Эти кортежи назы­ваются перестановками с повторениями из букв x1,…xk, имеющими состав (n1, . nk). Число таких пе­рестановок обозначим Р(n1, . nk).

Р(n1, . nk)=

Упражнение. Вычислите: Р<2, 5, 3);

Решение. Р(2, 5, 3); п = 2 + 5 + 3 = 10, п1 = 2, n2 = 5, n3 = 3.

Р(2, 5, 3) =

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

Решение. Это слово имеет состав: м — 2, а — 3, т — 2, е — 1, и — 1, к — 1, то есть (2, 3, 2, 1, 1, 1), поэтому получим

Р(2, 3, 2, 1, 1, 1) =

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

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

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

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

Р(7, 7, 7, 7) =

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

Ответ:

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

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

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

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

Ответы: 1. 226 800. 2. 5! • 5! = 14 400. 3. 103 • 323.

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

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

2. Задача-шутка. Как-то раз в воскресенье семеро друзей зашли в кафе. Хозяин кафе сказал, что если друзья в каждое следующее воскресенье будут садить­ся по-разному и перепробуют все способы посадки, то с этого момента он обещает кормить всех мороженым бесплатно. Удастся ли друзьям воспользоваться пред­ложением хозяина кафе?

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

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

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

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

1. Сколькими способами можно разместить 12 че­ловек за столом, на который поставлено 12 прибо­ров?

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

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

а) последней была цифра 4;

б) первой была цифра 2, а второй 3?

4. Имеется 10 книг, среди которых:

а) восемь книг разных авторов и двухтомник одного автора, которого не было среди предыдущих семи;

б) семь книг разных авторов и трехтомник восьмого автора.

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

Занятие 5. Сочетания

• дать понятие сочетаний с повторениями и без повторений;

• закрепить тему при решении задач.

В начале урока разбираются задачи, заданные на дом.

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

ОПРЕДЕЛЕНИЕ 1. Два кортежа называются эквивалентными, если они имеют одинаковый состав.

ОПРЕДЕЛЕНИЕ 2. Классы эквивалентности, на которые разбивается вся совокупность кортежей длины k из п элементов, называются сочетаниями с повторениями п элементов по k, их число обозначают .

Упражнение. Вычислите:

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

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

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

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

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

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

ОПРЕЛЕЛЕНИЕ. Число k-подмножеств в п-множестве X называют сочетаниями из п по k. Число таких сочетаний обозначают .

Упражнение. Вычислите: .

Источник

Презентация на тему «Комбинаторика»

Выбранный для просмотра документ Комбинаторика.pptx

Описание презентации по отдельным слайдам:

КОМБИНАТОРИКА Размещения, перестановки, сочетания

Произведение подряд идущих первых n натуральных чисел обозначают n! и называют «эн факториал»: Определение 1: n!=1·2·3·…·(n-2)·(n-1)·n

Теорема 1: n различных элементов можно расставить по одному на n различных мест ровно n! способами. Рn=n! — перестановки

6 слонят Сколькими способами можно их расставить? Например: 6!=1·2·3·4·5·6=720

Задача 1: К хозяину дома пришли гости A,B,C,D. За круглым столом – пять разных стульев. а) Сколькими способами можно рассадить гостей за столом? б) Сколькими способами можно рассадить гостей за столом, если место хозяина дома уже известно? A B C D хозяин

Решение: а) На 5 стульев должны сесть 5 человек (включая хозяина дома). Значит, всего имеется Р5 способов их рассаживания: Р5 =5!= 1·2·3·4·5= 120

Решение: б) Так как место хозяина фиксировано, то следует рассадить четырех гостей на четыре места. Это можно сделать Р4 способами: Р4 =4!= 1·2·3·4= 24

Задача 2: В чемпионате по футболу участвовало 7 команд. Каждая команда сыграла по одной игре с каждой командой. Сколько всего было игр?

Решение: Первый способ: Рассмотрим таблицу 7х7, в которой вписаны результаты игр. В ней 49 клеток: По диагонали клетки закрашены, т.к. никакая команда не играет сама с собой. Если убрать диагональные клетки, их останется 49-7=42. 1 2 3 4 5 6 7 1 3:1 0:5 2:2 0:0 1:0 1:3 2 4:3 1:0 1:0 0:0 1:1 3 1:3 1:0 1:2 0:0 4 1:1 1:1 1:4 5 1:0 0:0 6 2:2 7

Решение: В нижней части таблицы результатов нет, т.к. все они получаются отражением уже имеющихся результатов из верхней части таблицы. 3:1 1:3 Поэтому количество всех проведенных игр равно половине от 42, т.е. 21. 1 2 3 4 5 6 7 1 3:1 0:5 2:2 0:0 1:0 1:3 2 4:3 1:0 1:0 0:0 1:1 3 1:3 1:0 1:2 0:0 4 1:1 1:1 1:4 5 1:0 0:0 6 2:2 7

Второй способ: Произвольно пронумеруем команды №1, №2,…, №7 и посчитаем число игр поочередно. Команда №1 встречается с командами №2-7 – это 6 игр. Команда №2 тоже проведет 6 встреч, но одну игру , с командой №1, мы уже посчитали. Получается 5 новых игр. Команда №3 проведет 6 встреч, из которых две, с №1 и №2 мы посчитали, значит, добавится еще 4 игры. Продолжая, получим: 6 игр 5 игр 4 игры 3 игры 2 игры 1 игра 21 игра 6+5+4+3+2+1=21 1 2 3 4 5 6 7 1 3:1 0:5 2:2 0:0 1:0 1:3 2 4:3 1:0 1:0 0:0 1:1 3 1:3 1:0 1:2 0:0 4 1:1 1:1 1:4 5 1:0 0:0 6 2:2 7

Третий способ: Используем геометрическую модель: 7 команд – это вершины выпуклого семиугольника, а отрезок между двумя вершинами – это встреча двух соответствующих команд: сколько отрезков, столько игр. Из каждой вершины выходит 6 отрезков. Получается 7·6 отрезков, каждый из которых посчитан дважды: как АВ, так и ВА. Значит, всего проведен (7·6):2=42:2=21 отрезок. А В С D E F G

Выводы: Состав игры определен, как только мы выбираем две команды. Значит, количество всех игр в турнире для n команд – это количество всех выборов двух элементов из n данных элементов. При этом порядок выбора не важен.

Теорема 2: Если множество состоит из n элементов и требуется выбрать два элемента без учета их порядка, то такой выбор можно произвести способами.

Определение 2: Число всех выборов двух элементов без учета их порядка из n данных элементов называют числом сочетаний из n элементов по 2 и обозначают [«цэ из эн по два»]

Задача 3: Встретились 11 футболистов и 6 хоккеистов и каждый стал по одному разу играть с каждым в шашки, которые они «давненько не брали в руки». Сколько встреч было: а) между футболистами б) между хоккеистами в) всего?

А что получится, если мы будем учитывать порядок двух выбираемых элементов? Теорема 3: Если множество состоит из n элементов и требуется выбрать два элемента учитывая их порядок, то такой выбор можно произвести способами.

Определение 3: Число всех выборов двух элементов с учетом их порядка из n данных элементов называют числом размещений из n элементов по 2 и обозначают [«а из эн по два»]

Задача 4: В классе 27 учеников. К доске нужно вызвать двоих. Сколькими способами это можно сделать, если: а) первый ученик должен решить задачу по алгебре, а второй – по геометрии; б) они должны быстро стереть с доски? Решение: В случае а) порядок важен, а в случае б) – нет. Значит, а) б)

А как будут выглядеть формулы, если в них верхний индекс заменить на 5, 7, 10 и т.д.? Сколькими способами можно выбрать 5 учеников из 30 для дежурства в столовой; 7 монет из 10 данных; 10 карт из колоды в 32 карты? Определение 4: Число всех выборов k элементов из n данных без учета порядка называют числом сочетаний из n элементов по k и обозначают Число всех выборов k элементов из n данных с учетом их порядка называют числом размещений из n элементов по k и обозначают

Теорема 4: Для любых натуральных чисел n и k таких, что k 24 слайд

Задача 5: В классе 27 учеников, из них нужно выбрать троих. Сколькими способами это можно сделать, если: а) первый ученик должен решить задачу, второй – сходить за мелом, третий – пойти дежурить в столовую? б) им следует спеть в хоре?

Задача 6: «Проказница Мартышка, Осел, Козел и Косолапый Мишка затеяли сыграть квартет». Мишке поручили выбрать 4 любых инструмента из имеющихся 11. а) найти число всевозможных выборов инструментов; б) найти число всевозможных рассаживаний участников квартета с выбранными четырьмя инструментами (инструменты, как в басне Крылова, занимают четко отведенные позиции).

Курс повышения квалификации

Дистанционное обучение как современный формат преподавания

• Сейчас обучается 801 человек из 76 регионов

Курс повышения квалификации

Методика обучения математике в основной и средней школе в условиях реализации ФГОС ОО

• Сейчас обучается 283 человека из 69 регионов

Курс профессиональной переподготовки

Математика: теория и методика преподавания в образовательной организации

• Сейчас обучается 605 человек из 75 регионов

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

Номер материала: 37849032614

Международная дистанционная олимпиада Осень 2021

Не нашли то что искали?

Вам будут интересны эти курсы:

Оставьте свой комментарий

Авторизуйтесь, чтобы задавать вопросы.

Безлимитный доступ к занятиям с онлайн-репетиторами

Выгоднее, чем оплачивать каждое занятие отдельно

Российские адвокаты бесплатно проконсультируют детей 19 ноября

Время чтения: 2 минуты

В России выбрали топ-10 вузов по работе со СМИ и контентом

Время чтения: 3 минуты

В российских школах оборудуют кабинеты для сообщества «Большой перемены»

Время чтения: 1 минута

Рособрнадзор откажется от ОС Windows при проведении ЕГЭ до конца 2024 года

Время чтения: 1 минута

Минпросвещения разрабатывает образовательный минимум для подготовки педагогов

Время чтения: 2 минуты

Минпросвещения будет стремиться к унификации школьных учебников в России

Время чтения: 1 минута

Подарочные сертификаты

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

Все материалы, размещенные на сайте, созданы авторами сайта либо размещены пользователями сайта и представлены на сайте исключительно для ознакомления. Авторские права на материалы принадлежат их законным авторам. Частичное или полное копирование материалов сайта без письменного разрешения администрации сайта запрещено! Мнение администрации может не совпадать с точкой зрения авторов.

Источник