Число сочетаний с повторениями формула – основные формулы. Перестановки, размещения, сочетания. Задачи с решением по комбинаторике

Сочетание без повторений | matematicus.ru

Сочетанием без повторений называют комбинации, составленные из n элементов по m элементам, которые отличаются друг от друга хотя бы одним элементом.

Обозначение: $С_n^m$

Допустим, имеется три буквы А, В и С.

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

При подсчете числа сочетаний элементов — порядок не важен.

Запишем формулу сочетания


Пример 1

В классе 20 учащихся. Сколькими способами можно выделить двух человек для дежурства? Так как каждая группа учащихся в 2 человека должна отличаться хотя бы одним из учащихся. Отсюда, применим формулу комбинаторики — сочетание, имеем


Пример 2

Пусть имеется множество, содержащие 4 буквы: {А,В,С,D}.

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

Решение

По формуле сочетания имеем,

 $C_4^3 =\frac{{4!}}{{\left( {4 — 3} \right)!\cdot3!}} = \frac{{4!}}{{3!}} = \frac{{1\cdot2\cdot3\cdot4}}{{1\cdot2\cdot3}} = 4$


Пример 2

  Сколькими способами можно распределить три путевки в один санаторий между пятью желающими?

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


Пример 3
В научном конкурсе участвует 12 человек, из них 5 женщин и 7 мужчин. Сколькими способами можно сформировать группу из 7 человек, чтобы в ней было 3 женщины?

Решение 
Из пяти женщин необходимо выбрать по три. Следователь, число таких способов отбора равно $С_5^3$

Число способов отбора мужчин, четырех из семи равно $С_7^4$

По формуле комбинаторики – сочетания, группу можно сформировать способами:


Пример 4

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

Решение 
Число способов выбора офицера: $С_3^1$

сержантов $С_6^2$

по аналогии, число комбинаций выбора курсантов, получаем $С_30^7$

 

Итак, получаем число способов составления суточного наряда

www.matematicus.ru

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

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

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

Число сочетаний с повторениями из n элементов по m будем обозначать символом

Формула для вычисления числа сочетаний с повторениями:

(1.6)

Замечание: m может быть и больше n.

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

Решение.

,

где m>n.

Ответ. Существует 84 различных способа выбора пирожных.

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

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

Число перестановок их n элементов обозначается символом Рn, это то же самое, что число размещений из n элементов по n в каждом, поэтому

(1.7)

Пример 1.5. Менеджер ежедневно просматривает 6 изданий экономического содержания. Если порядок просмотра изданий случаен, то сколько существует способов его осуществления?

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

По условию задачи n = 6.

Следовательно:

.

Ответ. Издания можно просмотреть издания 720 способами.

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

Число перестановок с повторениями выражается при помощи формулы:

,

(1.8)

где числа повторений.

Пример 1.6. Каким числом способов можно разделить m + n + s предметов на три группы, чтобы в одной группе было m предметов, в другой - n предметов, в третьей - s предметов?

Решение.

Ответ:

1.8. Правила комбинаторики

Правило суммы

(принцип логического сложения)

Если объект а может быть выбран m способами, а объект b может быть выбран другими n способами (не такими как а), то выбор элемента а или b из объединенной совокупности может быть осуществлен m+n способами.

Правило произведения

(принцип логического умножения)

Если объект а может быть выбран m способами и после каждого такого выбора объект b может быть выбран n способами, то выбор пары объектов а и b в указанном порядке может быть осуществлен mn способами.

Задачи к теме 1

1. Для разгрузки поступивших товаров менеджеру требуется выделить 4 из 15 имеющихся рабочих. Сколькими способами можно это сделать, осуществляя отбор в случайном порядке?

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

3. Руководством риэлтерской фирмы принято решение о необходимости рекламы нового вида услуг. По расчетам отдела рекламы, выделенных средств хватит для того, чтобы поместить объявления только в 7 из 12 городских газет. Сколько существует способов случайного отбора газет для размещения рекламы?

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

5. Расписание одного дня занятий на II курсе состоит из трех пар. В течение семестра студенты изучают 12 дисциплин. Сколько существует вариантов составления расписания занятий на один из дней недели, если в течение дня проводятся занятия по разным дисциплинам?

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

7. а) Сколько различных «слов», каждое из которых содержит 6 букв, можно составить из слова «экспертиза»? б) Сколько различных «слов», каждое из которых содержит 10 букв, можно составить из слова «экспертиза»?

8. Распределение пар в первом круге Уимблдонского турнира проводится методом жеребьевки. Сколько комбинаций пар возможно составить, если в турнире участвуют 20 теннисисток?

9. Администрация города объявила тендер на строительство медицинского центра. В конкурсную комиссию поступило 8 запечатанных пакетов со сметами от различных строительных фирм. Сколько существует способов очередности вскрытия пакетов, если они вскрываются конкурсной комиссией в случайном порядке после окончания срока подачи заявок?

10. Для обнаружения нефти на участке необходимо пробурить до 11 скважин. Однако, компания имеет средства для бурения только 6 скважин. Сколько способов отбора шести различных скважин у компании?

11. В Российской Федерации номерной знак автомобиля каждого региона состоит из трех букв и трех цифр. Чему равно общее число возможных номерных знаков региона, если, для его составления используется 12 букв русского алфавита и 10 цифр. Рассмотрите два случая, когда: а) цифры и буквы в номере не повторяются; б) если повторяются?

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

13. PIN – код пластиковой карты состоит из 4 цифр. Сколько всевозможных комбинаций PIN – кода существует, если: а) цифры в коде не повторяются? б) повторяются?

14. Издательство планирует выпустить в текущем году 6 различных учебников по статистике. Каким количеством способов можно выбрать 30 экземляров, если в библиотеке университета должны быть представлены все виды изданных учебников по статистике?

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

16. Код банковского сейфа состоит из 8 цифр. Сколько можно составить различных кодовых комбинаций, если: а) цифры не повторяются? б) цифры повторяются?

17. В мореплавании принято давать сигналы, используя разноцветные флаги. Сколько сигналов можно составить, используя одновременно 8 флагов, из которых 1 красный, 2 синих, 3 зелёных и 2 белых?

18. Фирма планирует приобрести путевки для отдыха 25 сотрудников. Сколько существует вариантов приобретения путевок, если: а) контракт будет заключен с четырьмя пансионатами? б) с двумя пансионатами?

19. Компьютерный ключ к антивирусной программе состоит из 9 цифр. Сколько существует различных вариантов компьютерных ключей, если: а) цифры ключа не повторяются? б) цифры ключа повторяются?

20. В парфюмерном магазине имеется 5 различных косметических наборов. Фирме необходимо приобрести 18 подарков к празднику. Сколько в таком случае существует вариантов выбора подарков?

studfiles.net

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

Комбинаторика в MS EXCEL. Примеры и методы

Подсчитаем в MS EXCEL количество Сочетаний с повторениями из n по k (выборка с возвращением). Также с помощью формул выведем на лист соответствующие варианты Сочетаний (английский перевод термина: combinations with repetition).

Сочетания с повторениями (выборка с возвращением) — это Сочетание n объектов по k в предположении, что каждый объект может участвовать в сочетании несколько раз.

Примечание: О Сочетаниях без повторений (без возвращения элементов) можно прочитать в статье Сочетания без повторений: Комбинаторика в MS EXCEL

Например, из множества содержащего 3 (n) различных элемента (a, b, c) можно сформировать 6 =ФАКТР(3+2-1) / (ФАКТР (3-1) * ФАКТР (2)) упорядоченных наборов по 2 (k) элемента: ааab, ac, bbbc, сс. В отличие от Сочетаний без повторений наборы ааbb и сс  допустимы. В отличие от Размещений наборы ac и ca считаются одинаковыми (порядок не важен).

В отличие от Сочетаний без повторений, k может быть меньше или больше n. Например, из множества содержащего 2 (n) различных элемента (a, b) можно сформировать 4 =ФАКТР(2+3-1) / (ФАКТР (2-1) * ФАКТР (3)) упорядоченных наборов по 3 (k) элемента (т.е. 4 сочетания с повторениями из 2 по 3): ааaаab, abb, bbb.

В файле примера MS EXCEL приведен подсчет количества Сочетаний с повторениями и созданы формулы для вывода всех Сочетаний для заданных n и k.

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

Задача

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

Так как не важно, в какой последовательности женщина будет выбирать платки, то нам нужно определить число Сочетаний с повторениями покупки 3-х платков 4-х возможных цветов. Т.е. n=4, а k=3. Оказывается, что таких вариантов =(4+3-1)!/(4-1)!/3! равно 20.

Воспользуемся файлом примера, чтобы убедиться, что мы решили задачу правильно.

По аналогии с решением задачи в статье Размещения без повторений сопоставим произвольным образом 4-м различным цветам числовые значения: 1; 2; 3; 4.

Выставив в ячейках В5 и В6 значения 4 и 3 соответственно, определим все варианты размещений.

Примечание: О Перестановках можно прочитать в статье Перестановки без повторений: Комбинаторика в MS EXCEL, а о Размещениях в статье Размещения без повторений: Комбинаторика в MS EXCEL.

excel2.ru

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *