А. Размещения без повторений

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

 

Упорядоченные подмножества из n элементов по k элементов каждое, называются размещениями из n элементов по k элементов (или кратко: размещениями из n по k). Таким образом, размещения отличаются либо составом элементов, либо их порядком.

Пусть дано множество, состоящее из п элементов. Размещением из п элементов по к (к < п) элементов называется упорядоченное подмножество, содержащее к различных элементов данного множества Все эти подмножества отличаются друг от друга или составом элементов, или порядком их распределения. Но число элементов во всех этих подмножествах равно к.

Размещениями из n по m называются всевозможные упорядоченные подмножества, содержащие m элементов из данных n. Обозначаются и вычисляются по формуле:

Пример 10. Сколько можно составить четырехзначных чисел, содержащих различные цифры из 5 цифр.

Решение: Четырехзначное число – это упорядоченная последовательность цифр, т.е. имеем дело с размещениями без повторений: А₅⁴=5!/(5-4)!=5!/1!=5×4×3×2=120.

Пример 11. В классе 10 учебных предметов и 5 разных уроков в день. Сколькими способами может быть составлено расписание на 1 день?

Решение:

Пример 12. Сколькими способами можно выбрать 3 из 10 различных шаров?

Ответ: А₁₀³=720.

B. Размещения с повторениями

Размещением с повторениями из m элементов по k элементов называется такое упорядоченное множество, которое содержит k элементов, причем один и тот же элемент может входить в это множество несколько раз (от нуля до k). Число всех размещений с повторениями из m по k равно m^k, т.е. Ā^k_m = m^k

Размещениями с повторениями из n элементов по k элементов называются упорядоченные множества, каждое из которых содержит k необязательно различных элементов из данного множества n элементов. Число размещений с повторениями вычисляется по формуле:

Пример 13. Сколько различных пятизначных чисел можно составить при помощи цифр 1, 2, 3?

Решение. Согласно предыдущему, искомое число равно Ā⁵₃ =3⁵=243

Пример 14. Кодовый замок имеет на диске 12 букв. Секретное слово состоит из 5 букв. Сколько неудачных попыток можно сделать? Общее число комбинаций Ā⁵₁₂ = 12⁵=248832. Число неудачных попыток 248832-1=248831.

Пример 15. В стену здания вмонтированы 8 гнезд для флажков. В каждое гнездо вставляется либо голубой, либо красный флажок. Сколько различных случаев распределения флажков на здание.

Решение: Так как порядок расположения элементов важен и не все элементы используются в данном соединении, то это размещение. А так как всего 8 гнезд, а флажков 2 вида (голубой и красный), то они будут повторяться, т.е. это размещение с повторением.

Сочетания

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

Определение. Подмножества из n элементов по k элементов каждое, отличающиеся хотя бы одним элементом, называются сочетаниями из n элементов по k элементов (или кратко: сочетания из n по k). Таким образом, сочетания отличаются только составом элементов. Число сочетаний из n по k обозначается: C^k_n.

Пусть дано множество, состоящее из п элементов. Сочетанием из п элементов по к (0 < к < п) элементов называется любое подмножество, которое содержит к различных элементов данного множества. Таким образом, различными подмножествами считаются только те, которые отличаются составом элементов. Подмножества, отличающиеся друг от друга лишь порядком следования элементов, не считаются различными. Число всех возможных сочетаний из п элементов по к обозначается C^k_n. Так как число перестановок из к равно k!, то число размещений из п элементов по к — А^k_n будет в к! раз больше, чем число сочетаний из п

элементов по к - С^k_n, т.е. А^k_n =n! × C^k_n.

Отсюда: C^k_n = А^k_n /k!= n!/(n-k)! ×k!

Пусть имеются n различных элементов. k- сочетаниями без повторений из n элементов называют k-расстановки, составленные из этих элементов, и отличающиеся друг от друга составом, но не порядком элементов. Число k-сочетаний без повторений из n различных элементов обозначается С^k_n.

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

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

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

Решение: Так как порядок выбранных четырех человек не имеет значения, то это можно сделать C⁴₂₅ способами: C⁴₂₅ = 25!/(25-4)! ×4!=12650

Пример 17. Сколькими способами можно выбрать при игре в спортлото 6 из 49 номеров?

Ответ: C⁶₄₉=69919080

Пример 18. В кондитерской продавалось 4 вида пирожных: наполеоны, эклеры, песочные, слоеные. Сколькими способами можно купить 7 пирожных?

Ответ: C⁴₇=

 

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

Сочетанием с повторениями из m элементов по k элементов (или короче: сочетанием с повторениями из m по k) называется множество, содержащее k элементов, причем каждый элемент принадлежит к одному из m типов. Число всех вышеупомянутых сочетаний с повторениями из m по k обозначается Ĉ^k_m (обратите внимание на отличие от обозначения числа сочетаний из n по k – черта сверху).Число сочетаний с повторениями из т по k равно:

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

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

Пример 19. На почте продаются открытки 10 сортов. Сколько вариантов существует для покупки 12 открыток.

Решение: Порядок расположения элементов не имеет значения, следовательно, это сочетание. А так как открытки в наборе могут повторяться, то это сочетание с повторениями.

.

Таким образом, из 10 открыток можно выбрать набор из12 штук 293930 способами.

Пример 20. Число различных бросаний двух одинаковых кубиков равно

Пример 21. Напишем все сочетания с повторениями из трех элементов А, В, С по 3. Сколько их?

Вот они: ААА ВВВ ССС, АВВ ВСС, АСС ВВС, ААВ, ААС, АСВ. Их 10 штук, т.е.Ĉ³₃.=10.

 

Свойства сочетаний

1) С^k_n = С^n-k_n

2) С^k_n = С^k-1_n-1+ С^k_n-1

3) С⁰_n + С¹_n + С²_n + …+ Сⁿ_n = 2ⁿ

4) С^k_n * С^m-k_n-k= С^k_m+ С^m_n

Все сочетания легко вычисляются, если записать их в виде треугольной таблицы (треугольника Паскаля):

1 С_о°

1 1 C₁⁰ С₁¹

1 2 1 С₂⁰ С₂¹ С₂²

1 3 3 1 С₃⁰С₃¹ С₃²С₃³

1 4 6 4 1 С₄⁰ С₄¹С₄²С₄³С₄⁴

1 5 10 10 5 1 С₅⁰С₅¹С₅²С₅³С₅⁴С₅⁵

На основании данной таблицы можно увидеть справедливость указанных выше свойств сочетаний.

 

При определении вида комбинации удобно пользоваться схемой:

 

КОМБИНАТОРНЫЕ ЗАДАЧИ

Задача 1. Максимально возможное количество матчей, которое можно организовать в высшей лиге футбольного дивизиона страны не должно превышать 160 в один круг. Сколько (максимально) команд можно включить в состав высшей лиги.

Решение. Обозначим возможное количество команд через n, тогда число сыгранных матчей равно C²_n. По условию C²_n ≤ 160. Пусть C²_n = 160, тогда:

n!/(n-2)!* 2!=160. Тогда n=18,4;-17,4.

Число команд должно быть натуральным числом, поэтому n = 18.

Ответ. 18 команд.

Задача 2. Имеется 4 сорта чая, 5 сортов конфет и 6 сортов печенья. Сколькими способами можно организовать чаепитие-дегустацию на трех человек, если каждый может выпить одну чашку чая определенного сорта с одной конфетой и одним печеньем?

Решение. Используя правило произведения, подсчитаем, что:

1) число способов распределить сорта чая для трех дегустаторов равно 4³;

2) число способов распределить по одной конфете определенного сорта для трех дегустаторов равно 5³;

3) число способов распределить по одному печенью определенного для трех дегустаторов равно 6³.

Применяя еще раз правило произведения, мы получим, что число способов организовать данное чаепитие-дегустацию равно 4³* 5³* 6³= 1 728 000.

Задача 3. В соревнованиях принимают участие 16 команд Сколькими способами могут распределиться три первых места, т е необходимо найти число всех подмножеств, состоящих из трех элементов, отличающихся составом (номерами команд) или порядком их размещения (подмножества № 1, № 2, № 3 и № 2, № 1, № 3 являются разными). Таким образом, имеем дело с размещением. Тогда искомое число равно A³₁₆=3360

Задача 4. В отделении 10 солдат. Необходимо составить наряд из 4-х человек. Сколько существует способов составления такого наряда?

Решение. Поскольку порядок, в котором мы выбираем участников наряда, не важен, то мы имеем дело с сочетаниями их 10 по 4. Итак, C⁴₁₀=210

Задача 5. Сколько существует четырехзначных чисел, состоящих из различных цифр?

Решение. Ноль не может быть первой цифрой, следовательно, есть 9 возможностей выбрать первую цифру. Далее может следовать любая упорядоченная тройка оставшихся цифр, а для этого есть A³₉ способов. Итого, получаем 9* A³₉=4536

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

Решение: Порядок расположения элементов имеет значение и в диаграмме 4 столбца, а ручка тоже четырехцветная, т.е. все элементы присутствуют в соединении, следовательно, это соединение – перестановка. А так как окраска столбцов не повторяется (в условии сказано, что столбцы имеют разные цвета), то это перестановка без повторения. Итак, P_n = n! = 4! = 1×2×3×4 = 24 Ответ: столбцы можно закрасить 24 способами.

Задача 7. Имеется 5 кружков: 3 белых и 2 черных. Сколько различных узоров можно получить, располагая кружки в ряд.

Решение: Порядок расположения элементов имеет значение и в узоре 5 кружков, т.е. все элементы присутствуют в соединении, следовательно, это соединение – перестановка. А так как окраска кружков повторяется (в условии сказано, что 3 белых и 2 черных), то это перестановка с повторением. Итак,

Ответ: узор можно составить 10 способами.

Задача 8. Сколько словарей надо издать, чтобы можно было непосредственно выполнить перевод с любого из 5 языков на любой из 5 языков.

Решение: Порядок имеет значение (так как русско-английский и англо-русский словари различны) и не все элементы присутствуют в соединении (а только 2 из 5), значит, это размещение. Так как языки различны, то это размещение без повторения. Итак, . Ответ: надо составить 20 словарей.

Задача 9. На железнодорожной станции имеется 5 светофоров. Сколько может быть дано различных комбинаций их сигналов, если каждый светофор имеет 3 состояния.

Решение: Порядок имеет значение и не все элементы присутствуют в соединении, значит, это размещение. Так как цвета повторяются, то это размещение с повторением. Итак, . Ответ: может быть дано 243 различных комбинаций цветов.

Задача 10. 12 человек играли в городки. Сколькими способами они могут разбиться на команды по 4 человека в каждой.

Решение: Порядок расположения игроков в команде не имеет значения, следовательно, это сочетание. А так как игроки не повторяются (все члены команды различные люди), то это сочетание без повторения. Итак, .

Ответ: игроки могут разбиться на команды по 4 человека в каждой 495 способами.

Задача 11. В цветочном магазине продаются цветы 6 видов. Сколько можно составить букетов из 10 цветов в каждом (букеты отличающиеся лишь расположением цветов считать одинаковыми).

Решение: Порядок расположения цветов в букете не имеет значения, следовательно, это сочетание. А так как цветы повторяются, то это сочетание с повторением. Итак, . Ответ: букеты можно составить 3003 способами.

Задача 12. В группе 25 студентов, из которых 5 отличников, 11 хорошистов и остальные троечники. Сколькими способами можно выбрать группу для выполнения лабораторной работы, состоящей из 3 хорошистов, 1 отличника и 1 троечника.

Решение: Сначала узнаем сколькими способами можно выбрать 3 хорошистов из 11 человек. Порядок расположения студентов не важен, значит, это сочетание. А так как люди в группе не повторяются, то это соединение – сочетание без повторения. Итак, одного хорошиста можно выбрать способами. Аналогично рассуждая, приходим к тому, что 1 отличника можно выбрать способами и одного троечника можно выбрать способами. Так как команда для выполнения лабораторной работы выбирается одновременно, т.е. 5 хорошистов, затем 1 отличник, затем 1 троечник, то, применив правило произведения, получим: способами. Ответ: группу для выполнения лабораторной работы можно составить 3300 способами.

Задача 13: Имеется 4 чашки, 5 блюдец, 6 ложек (все чашки, блюдца, ложки различны). Сколькими способами можно накрыть стол к чаю на 3 человека, если каждый получает 1 чашку, 1 блюдце и 1 ложку.

Решение: Выберем для 3 человек чашки из 4 имеющихся. Порядок расположения элементов имеет значение, и не все элементы входят в соединение, значит, это размещение. Но так чашки не повторяются, то это размещение без повторения. Итак, из 4 чашек 3 можно выбрать способами. Аналогично рассуждая, получим, что из 5 блюдец 3 можно выбрать способами, а из 6 ложек 3 можно выбрать способами. Так блюдце, чашка и ложка входят в набор одновременно, то стол можно накрыть способами. Ответ: стол можно накрыть 172800 способами.

Задача 14. Группу из 20 студентов можно разместить в аудитории по 2 человека за каждой партой. Порядок их размещения имеет значения.

Решение. Количество возможных вариантов размещений вычисляется по формуле:

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

Решение. Количество трехзначных чисел в данном примере определяется по формуле размещений (3) и равно:

Задача 16. Группу из 20 студентов следует рассадить в аудитории по 2 человека за каждой партой. Порядок их размещения не имеет значения. Определить количество возможных вариантов сочетаний.

Решение. Количество возможных вариантов сочетаний вычисляется по формуле 4):

Задача 17. Флаг государства может комбинироваться из трёх полос разного цвета. Определить число комбинаций из пяти разных цветов, которые можно получить, выбирая из них три полосы разного цвета.

Решение. Если учитывать порядок в комбинации, то число вариантов равно:

Если же порядок в комбинации не имеет значения, то количество разных вариантов равно: