1.5 сочетания и некоторые свойства сочетаний

Рассмотрим все подмножества множества, состоящего из трех элементов (а, Ь, с}. Их восемь:

1)Ø— пустое множество, как принадлежащее любому мно­жеству;

2) {а}, {b}, {с} - одноэлементные 3 множества;

3) {а, b}, {а, с}, {b, с} - двухэлементные 3 множества;

4) {а; Ь; с} — одно множество из трех элементов, то есть пол­ное рассматриваемое множество.

В сумме получили 8 различных подмножеств.

Число подмножеств по т элементов в каждом, содержащихся во множестве из n элементов, обозначается Сmn . В комбинаторике конечные множества называются сочетаниями.

Определение. Сочетания — это такие соединения из n элемен­тов по m (т ≤ п). которые отличаются одно от другого по крайней мере одним элементом. Сmn  называют числом сочетаний из n по  m.

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

Важно, какие конкретно элементы множества входят в каждое соединение

Число сочетаний, перестановок и размещений связаны фор­мулой:

Аmn = Сmn • Рn             (*)

Действительно, чтобы получить все размещения из n элемен­тов по m  надо:

взять n –элементное множество;

выделить m-элементное множество. Это можно сделать Сmn   - способами. Всего получим Сmn упорядоченных множеств, так как в каждом m- элементном подмножестве возможно установить  Pm порядков, где Pm – число перестановок из m.

Следовательно, Аmn = Сmn • Рn     , а Сmn   = Аmn/ Рn           (**)

Подставив сюда уже известные нам выражения для Рn  и Аmn

получим:                     Сmn =n!/((n-m)!*m!)

или Сmn =(n*(n-1)*…(n-m+1))/m!   (***)

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

Сочетание с повторениями – каждый элемент, входящий в соединение, может быть представлен более чем одним элементом  Ĉ mn=(n+m-1)!/(m!*(n-m)!). В дальнейшем сочетание без повторений мы будем называть одним словом – «сочетание».

Пример. В классе 22 учащихся. Двух из них следует назначить дежурными. Сколькими способами это можно сделать?

Решение: Из 22 учащихся будем составлять всевозможные группы по 2 человека, причем порядок в группах не играет роли, следовательно, для подсчета числа способов используем сочетания: Сmn=22!/((22-2)!*2!)= 22!/(20!*2!)=22*21/(1*2)=231

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

Если порядок учитывается, то есть составляются упорядочен­ные множества, то это—размещения. Если порядок не учитывает­ся, то есть составляются множества, то это — сочетания.

Пример. Если из класса 20 человек выбирают три делегата на конференцию, то порядок не учитывается, так как каждый делегат выступает как равноправный представитель класса. Здесь мы при­влекаем сочетание

С320=  (20*19*18)/(1*2*3)

Если же в классе надо выбрать старосту, физорга и профорга, то есть всего трех человек, но теперь уже натри различных долж­ности. то при подсчете числа различных комбинаций надо учесть порядок; здесь налицо число размещений. Если в классе 20 чело­век, то число способов заполнить три выборные должности под­считывается как число размещений из 20 по 3, то есть:

А320=20*19*18.

Контрольные вопросы

1. Что такое сочетание?2.  Какова формула для числа сочетаний?3. Когда необходимо использовать при решении комбинатор­ных задач сочетание, а когда размещение?4. Чем отличается сочетания с повторением от сочетания?

1.6 Задачи по комбинаторике

1.  Сколько различных экзаменационных комиссий по 3 челове­ка можно составить, если на кафедре 20 преподавателей?

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

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

5.  Сколькими способами можно выбрать 6 различных пиро­жных в кондитерской, где имеется 11 сортов пирожных?

6. В нашем распоряжении есть 5 разноцветных флагов. Сколько различных сигналов, состоящих из 3 флагов, можно поднять на флаг­штоке?

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

8. Сколько можно образовать целых чисел, из которых каждое изображаясь бы тремя различными значащими цифрами?

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

10.  На собрании должны выступить 4 человек: А, Б. В, Д. Сколь­кими способами можно их разместить в списке факторов при усло­вии что А должен выступить непосредственно перед Б?

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

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

1З. В ящике имеется 15 деталей, среди которых 5 бракованных. Сборщик на удачу берет 3 детали. Сколько будет случаев, когда сре­ди извлеченных трех деталей будут: а) все стандартные; b) две стан­дартные; с) все бракованные?

14. Сколькими способами можно группу из 15 учащихся разде­лить на две группы так, чтобы в одной группе было 4 человека, а в другой—11 человек?

15. Сколько диагоналей имеет: а) выпуклый пятиугольник; б) выпуклый 12—угольник; в) выпуклый 25-угольник; г) выпуклый n-угольник.

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

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

18. В шахматном турнире участвуют 12 человек. Каждый из участников должен сыграть с каждым из остальных по две партии, Сколько всего партий должны сыграть участники турнира? 19. Двенадцати ученикам выдано два варианта контрольных работ. Сколькими способами их можно посадить в два ряда, чтобы  рядом не было одинаковых вариантов, а у сидящих друг за другом  был один и тот же вариант?

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