14. СОЧЕТАНИЯ С ПОВТОРЕНИЯМИ | Решение задач по математике и другим пре

Пусть имеются предметы n различных типов. Сколькими способами можно составить из них комбинацию из k элементов, если не принимать во внимание порядок элементов в комбинации, но при этом предметы одного и того же типа могут повторяться? Иными словами, различные комбинации должны отличаться количеством предметов хотя бы одного типа. Такие комбинации называются сочетаниями с повторениями, а их общее число будем обозначать .

Поясним это на следующем примере. Пусть имеется три элемента: a, b и c. Тогда из этих трёх элементов можно составить шесть сочетаний с повторениями по два элемента: ab, ac, bc, aa, bb, cc.

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

Следует отметить, что если, например, две комбинации по k элементов отличаются друг от друга только порядком расположения элементов, то они не считаются различными сочетаниями.

Существует специальная формула для вычисления числа сочетаний с повторениями:

(12.1)

Выведем эту формулу. Прежде всего надо занумеровать возможные типы элементов числами от 1 до n (иначе можно оказаться в положении мужа, который никак не мог вспомнить, что ему поручила купить жена: 5 пакетов молока и 2 банки пива или наоборот 2 пакета молока и 5 банок пива). Теперь можно каждую комбинацию зашифровать с помощью последовательности единиц и палочек: для каждого типа с 1-го до n-го по порядку написать столько единиц, сколько предметов этого типа входит в комбинацию, а различные типы отделять друг от друга палочками.

Например, в кондитерском магазине продаются пирожные 4 видов: корзиночки, наполеоны, песочные и эклеры. Если куплено 3 корзиночки (к), 1 наполеон (н), 2 песочных (п) и 1 эклер (э), то получим такую запись:

В этой записи палочки отделяют одну группу пирожных от другой. Если же куплено 2 корзиночки и 5 песочных, то получим запись . Ясно, что разным покупкам соответствуют при этом разные комбинации из 7 единиц и 3 палочек. Обратно, каждой комбинации единиц и палочек соответствует какая-то покупка. Например, комбинации соответствует покупка 3 наполеонов и 4 песочных (крайние группы отсутствуют).

В результате мы получим столько единиц, сколько предметов входит в комбинацию, т. е. k, а число палочек будет на 1 меньше, чем число типов предметов, т. е. n–1. Таким образом, мы получим перестановки с повторениями из k единиц и n–1 палочек. Различным комбинациям при этом соответствуют различные перестановки с повторениями, а каждой перестановке с повторениями соответствует своя комбинация.

Итак, число сочетаний с повторениями из элементов n типов по k равно числу P(k, n–1) перестановок с повторениями из n–1 палочек и k единиц. А

. Поэтому.

Пример 12.1. В кондитерской имеется 3 вида пирожных. Сколькими способами можно купить 9 пирожных?

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

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

Решение. Данная задача на отыскание числа сочетаний с повторениями из 10 элементов по 10. Следовательно,

, .

В случае, когда требуется купить 8 различных открыток, получим сочетания без повторений:

.

Пример 12.3. Сколько всего чисел (не больше 100000) можно составить из цифр 1, 2, 3, 4 и 5 в каждом из которых цифры расположены в неубывающем порядке?

Решение. Это задача о числе сочетаний из пяти цифр по одному, по два, по три, по четыре и по пяти с повторениями в каждом случае. Поскольку , , , , , то существует чисел, удовлетворяющих условию задачи.

Упражнения

12.1. Сколькими способами Буратино, кот Базилио и лиса Алиса могут поделить между собой 5 одинаковых золотых монет?

Ответ: .

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

Ответ: .

12.3. Сколько существует треугольников, длины сторон которых принимают одно из значений 4, 5, 6, 7?

Ответ: .

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

Ответ: .

< Предыдущая		Следующая >

matica.org.ua

Задачи по теме «Перестановки. Сочетания. Размещения»

Перестановки
DOCX / 73.01 Кб

 

Перестановки

№1. На столе яблоко, груша и банан. Сколькими способами их можно переставить?

/data/files/v1560842854.png (0x0)

Размещения

№2. Сколькими способами можно раздать по одному фрукту Даше и Наташе?

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

яблоко и груша; яблоко и банан; груша и банан.

Но комбинаций сейчас будет в два раза больше. Рассмотрим, например, первую пару фруктов:  яблоком можно угостить Дашу, а грушей – Наташу; либо наоборот – груша достанется Даше, а  яблоко – Наташе.

И такая перестановка возможна для каждой пары фруктов.

В данном случае работает формула количества размещений: /data/files/c1560842866.png (0x0) 3 элемента для двух ячеек

/data/files/e1560842876.png (0x0)

Сочетания   

№3. Сколькими способами можно выбрать а) один фрукт, б) два фрукта, в) три фрукта, г) хотя бы один фрукт из трех? 2 элемента из 3 элементов

формула количества сочетаний: 

/data/files/s1560842886.png (0x0)

 

№4. В ящике находится 15 деталей. Сколькими способами можно взять 4 детали? 4 элемента из 15 элементов

№5. Боря, Дима и Володя сели играть в «очко». Сколькими способами им можно сдать по одной карте? (колода содержит 36 карт) 3 элемента из 36 элементов

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

№7. Сколько двузначных чисел можно составить из цифр 1. 3, 5, 8, 9 так, чтобы в каждом числе не было одинаковых цифр? 5 элементов для 2 ячеек

Или+, и*

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

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

№10. Группу из 20 студентов нужно разделить на 3 бригады, причем в первую бригаду должны входить 3 человека, во вторую — 5 и в третью — 12. Сколькими способами это можно сделать.

1 вариант В турнире участвуют семь команд. Сколько вариантов распределения мест между ними возможно?  Из 6 открыток надо выбрать 3. Сколькими способами это можно сделать? Вычислить  (6! – 4!) : 5!

2 вариант Сколькими способами могут разместиться за круглым столом 10 человек?  Сколькими способами можно составить флаг, состоящий из трех горизонтальных полос различных цветов, если можно использовать материал семи различных цветов? (7! – 5!) : 6!

xn--j1ahfl.xn--p1ai

«Задачи на подсчет числа размещений, перестановок, сочетаний»

Урок ________

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

Тема: «Задачи на подсчет числа размещений, перестановок, сочетаний».

Цели:

— повторить формулы для нахождения числа различных видов комбинаций: размещений, перестановок, сочетаний без повторов; изучить формулы для нахождения числа различных видов комбинаций: размещений, перестановок, сочетаний с повторами, научиться распознавать задачи на нахождение размещений, перестановок, сочетаний; решить простейшие комбинаторные задачи с помощью этих формул;

— развивать познавательный интерес студентов, логическое мышление, умение применять знания в изменённой ситуации, делать выводы и обобщения; развивать  умения сравнивать, систематизировать, обобщать;

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

Оборудование:

Ход урока

I. Организационный момент

Преподаватель проверяет готовность к уроку.

Я рада приветствовать всех Вас на сегодняшнем уроке.

II. Мотивация. Сообщение темы, целей урока

1. Вопросы:

1. Определения: перестановки, размещения, сочетания.

2. Важен ли порядок? В каких соединениях? (размещение)

2. Решение задач:

№1. Экзамен состоит из 5 задач, которые можно решать в любом порядке. Сколькими способами можно расставить задачи. (способов)

№2. В магазине продается 8 различных наборов марок, посвященных спортивной тематике. Сколькими способами можно выбрать из них 3 набора. (способа)

№3. Сколько четырехзначных чисел, в которых нет одинаковых цифр, можно составить из цифр 0, 2, 4, 6, 8. (всего чисел А, а чисел начинающихся с нуля —

, тогда А—=96)

Тема сегодняшнего урока «Задачи на подсчет числа размещений, перестановок, сочетаний.». Давайте вместе попробуем сформулировать цели урока:

— научиться распознавать задачи на нахождение размещений, перестановок, сочетаний;

— решать простейшие комбинаторные задачи с помощью этих формул.

III. Изучение новой темы

1. Перестановка

Рассмотрим слово «КВАНТ», состоящее из 5 различных букв. Если менять порядок букв, получим 5!=120 перестановок

Если проделать то же самое со словом «АТАКА», то перестановок будет меньше, потому что, меняя местами 1,3 и 5-ю буквы, будем получать то же самое слово. Т.к. три буквы А можно менять местами 3!=6 способами, то перестановок будет в слове «АТАКА» в 6 раз меньше, т.е.

Вывод: Перестановками в такой выборке, где есть один элемент, называются перестановками с повторениями. Обозначается : Р_{(n1, n2,….., nk)}

Р(n1, n2,….., nk)₌, где n- количество повторений элементов

Задача: Сколько различных перестановок можно сделать из букв слова «МАТЕМАТИКА»

Решение:

Всего – 10 букв

«М» — 2 повтора

«А» — 3 повтора

«Т» — 2 повтора

«Е» — 1 повтор

«И» — 1 повтор

«К»- 1 повтор

перестановки

Ответ: 151200 перестановки

2. Сочетания.

Рассмотрим следующую задачу.

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

Решение

. Данная задача на отыскание числа сочетаний без повторений, т.к. требуется купить 8 различных открыток

Ответ: 45 способов

Проделаем то же самое, но только определим «Сколькими способами можно купить в нем 8 открыток?

Решение.

Данная задача на отыскание числа сочетаний с повторениями из n = 10 элементов по k =8. Следовательно, она решается по формуле

 

Ответ : 24310 способов

Вывод: Иными словами, выборки которые отличаются количеством элементов хотя бы одного типа, называются сочетаниями с повторениями, а их общее число будем обозначать .

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

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

3. Размещения.

Рассмотрим задачу:

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

способов

А теперь ту же задачу, но вопрос сформулируем иначе.

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

Задача такого вида называется «размещения с повторением», обозначается   и вычисляется по принципу умножения.

Вычисляется по следующей формуле:

Решение. Задача сводится к распределению 5 пассажиров по 7 этажам (т. е. набор упорядоченный), причем возможны повторения (т. е. несколько пассажиров могут выйти на одном этаже). Таким образом, задача сводится к нахождению числа размещений с повторениями:

Задача: Сколькими способами девочка Яна может разложить 12 кукол по трём ящикам, если каждый ящик может вместить все куклы?

Ответ: 

IV. Закрепление.

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

Решение. Число всех букв, каждая из которых записывается одним символом, равно 

Число всех букв, каждая из которых записывается двумя символами, равно .

Число всех букв, каждая из которых записывается тремя символами, равно .

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

Число всех букв, каждая из которых записывается пятью символами, равно .

Число всех указанных букв будет равно 62.

Задача №2. Сколько всего чисел (не больше 100000) можно составить из цифр 1, 2, 3, 4 и 5 в каждом из которых цифры расположены в неубывающем порядке?

Решение. Это задача о числе сочетаний из пяти цифр по одному, по два, по три, по четыре и по пяти с повторениями в каждом случае. Поскольку , , , , , то существует чисел, удовлетворяющих условию задачи.

V. Подведение итогов занятия. Рефлексия.

(Обобщаются новые знания, делаются выводы о достигнутых целях урока. Поощряются активные студенты, выставляются обоснованные преподавателем оценки.)

1) Подведем итоги нашего занятия.

Проверь себя:

1. Соединения виды перечислить?

2. На какие они делятся ? ( повторения и без)

3. Важен ли порядок? В каких соединениях? (размещение)

4) Формулы нахождения: перестановок, размещения, соединения с повторениями и без.

2) Обсуждение и выставление оценок за урок.

3) Рефлексия:

Достиг ли ты своих целей? ______________

Оцени степень усвоения: _______________

Продолжи одно из предложений:

“Мне понятно…

“Я запомнил…

“Мне на уроке…

“Я думаю…

VI. Домашнее задание

Решите задачи:

1. Сколькими способами можно разместить 8 пассажиров по трем вагонам?

Ответ: .

2. Сколькими способами Буратино, кот Базилио и лиса Алиса могут поделить между собой 5 одинаковых золотых монет?

Ответ: .

3. Сколько различных браслетов можно сделать из 5 одинаковых изумрудов, 6 одинаковых рубинов и 7 одинаковых сапфиров ( всего в браслет входит 18 камней)? ( =)

infourok.ru

Задачи на сочетания без повторений

Задача в общем виде: Дано конечное множество М. Необходимо найти число к-элементных подмножеств.

1. На день рождения Лене подарили коробку конфет (в коробке 30 штук). Сколькими способами она может выбрать по одной конфете маме, папе, сестренке и двум братьям?

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

3. Дмитрий Сычев из «Локомотива» в целях поддержания интереса к футболу у подростков должен посетить 10 школ Перми для детей с дивиантным поведением. Всего в городе 30 таких школ. Сколькими способами он может сделать выборку?

4. В «Лукойл» требуются 9 охранников. В агентстве «Альфа» есть 15 человек, подходящих на эту должность. Сколькими способами может быть набран отдел охраны «Лукойла»?

5. Заявления на проживание в общежитии написали 146 человек. Свободных лишь 92 места, можно освободить еще 12, переселив некоторых студентов. Сколькими способами может быть отобрана группа студентов для проживания в общежитии?

6. На горнолыжной базе есть 20 разных трамплинов. Группа туристов сняли базу на 3 часа. За это время они могут спуститься с шести трамплинов. Сколькими способами они могут сделать это?

7. В классе 6 учеников, абсолютно не общающихся друг с другом. Учитель, для сплочения коллектива, в течение 20 дней приглашает на консультации троих из них так, чтобы компания ни разу не повторилась. Сколькими способами он может сделать это?

8. Трое юношей и две девушки выбирают место работы. В городе есть 3 завода, где требуются рабочие в литейные цеха (туда берут только мужчин), 2 ткацкие фабрики (туда приглашают женщин) и 2 фабрики, где требуются и мужчины, и женщины. Сколькими способами они могут распределиться между этими предприятиями?

9. На школьном вечере присутствуют 12 девушек и 15 юношей. Сколькими способами можно выбрать из них 4 пары для танцев?

10. У семиклассника Лени есть 7 книг по математике, а у восьмиклассника Бори – 8 книг. Сколькими способами они могут обменять три книги одного на три книги другого?

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

Задача в общем виде: Дано конечное множество М. Необходимо найти число к-элементных «подмножеств», каждое из которых может содержать одинаковые элементы. к может быть как меньше, так и больше числа элементов множества М.

1. В магазине 10 разных открыток. Ребятам надо поздравить 13 преподавателей с днем учителя. Сколькими способами они могут купить открытки?

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

3. На озере водится 4 вида рыб. Петя решил поймать 8 рыб и пойти домой. Сколько различных наборов рыб можно составить?

4. Сколько можно построить треугольников, длины сторон которых принимают одно из следующих значений: 4, 5, 6, 7 см?

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

6. У Остапа Бендера в мешке 100 слонов, из которых k разноцветных, и он раздает их т детям по слону в руки (k<m<100). Сколькими способами может состояться раздача слонов?

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

8. Саша купил 3 набора елочных шаров разных цветов по 6 в каждом. Елку достаточно украсить 15 шарами. Сколькими способами можно выбрать комплект украшений?

9. Сколькими способами можно выбрать из полной колоды карт, содержащей 52 карты, 6 карт, если карты одной масти считать одинаковыми?

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

studfile.net