3. Элементы комбинаторики.
Комбинаторика – наука, изучающая комбинации, которые можно составить по определенным правилам из элементов некоторого конечного множества.
Пусть задано множество, содержащее конечное число (n) элементов. Такие множества будем называть конечными, и обозначать {a,b,c,d, . . .s}.
Перестановки – это комбинации, составленные из всех п элементов данного множества и отличающиеся только порядком их расположения. Число всех возможных перестановок:
Рп = п! (3.1)
Если n=3: (a,b,c), (a,c,b), (b,a,c), (b,c,a), (c,a,b), (c,b,a). Р3= 3!=6.
Пример. Сколько различных списков (отличающихся порядком фамилий) можно составить из 7 различных фамилий?
Решение. Р7 = 7! = 2·3·4·5·6·7 = 5040.
Размещения – упорядоченные комбинации из т элементов данного множества (то есть, отличающиеся либо составом элементов, либо их порядком). Число всех возможных размещений:
(3.2)
Если n=3, m=2: (a,b), (a,c), (b,a), (b,c),
(c,a), (c,b).
Пример. Сколько возможно различных вариантов пьедестала почета (первое, второе, третье места), если в соревнованиях принимают участие 10 человек?
Решение.
Сочетания – неупорядоченные наборы из т элементов множества (то есть наборы, отличающиеся только составом элементов). Число всех возможных сочетаний:
(3.3)
Если n=3, m=2: (a,b), (a,c), (b,c),
Пример. В отборочных соревнованиях принимают участие 10 человек, из которых в финал выходят трое. Сколько может быть различных троек финалистов?
Решение. В отличие от предыдущего примера, здесь не важен порядок финалистов, следовательно, ищем число сочетаний из 10 по 3:
Размещение с повторениями по k элементов может содержать любой элемент сколько угодно раз от 1 до k включительно. Или не содержать его совсем, т.е. каждое размещение с повторениями из n элементов по k элементов может состоять не только из различных элементов, но из k каких угодно и как угодно повторяющих элементов. Число размещений с повторениями вычисляется по формуле:
Сочетание с повторениями из n элементов по k элементов может содержать любой элемент сколько угодно раз от 1 до k включительно. Или не содержать его совсем, т.е. каждое сочетание с повторениями из n элементов по k элементов может состоять не только из k различных элементов, но из k каких угодно и как угодно повторяющих элементов.
Следует отметить, что если, например два сочетания по k элементов отличаются друг от друга только порядком расположения элементов, то они не считаются различными
сочетаниями.
Число размещений с повторениями вычисляется по формуле:
3А.Примеры комбинаторных задач.
1)В карточке спортлото 36 клеток. Играющий должен отметить 6. Каково число всех возможных вариантов?
2) Сколькими способами можно выбрать четырех человек на 4 различные должности из 15 кандидатов на эти должности?
3) Сколько прямых можно провести через 8 точек, никакие три из которых не лежат на одной прямой?
4) Сколькими способами можно переставить буквы слова «хорошо» так, чтобы три буквы «о» не шли подряд?
5) В премьер-лиге чемпионата страны по футболу 16 команд, в сезоне они встречаются друг с другом 2 раза: на своем и чужом поле. Сколько игр проводится в премьер-лиге?
Команды, занявшие 1,2,3 места, награждаются соответствующими медалями. Сколькими способами могут распределиться призеры? А команды, занявшие 2 последних места, покидают премьер-лигу. Сколькими способами может сформироваться «клуб неудачников»? Сколькими способами могут распределиться места с 1-го по 16-е?
6) Замок сейфа открывается, если набрана правильная комбинация из четырех цифр от 0 до 9. Кода Вы не знаете. Найти наибольшее число безуспешных попыток для а) код не содержит одинаковых цифр; б) код содержит одинаковые цифры.
7) Аккорд – одновременное звучание двух и более нот. Сколько аккордов можно воспроизвести на семи нотах?