Перестановки размещения сочетания примеры. Сводка формул для всех видов соединений комбинаторика - перестановки и размещения с повторениями и без повторений с примерами

Число размещений без повторений из n по k n k различными координатами.

Число размещений без повторений находится по формуле:

Пример: Сколькими способами можно построить 3-значное число с различными цифрами, не содержащее цифры 0?

Количество цифр
, размерность вектора с различными координатами

Число размещений с повторениями

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

Число размещений с повторениями находится по формуле:

.

Пример: Сколько слов длины 6 можно составить из 26 букв латинского алфавита?

Количество букв
, размерность вектора

Число перестановок без повторений

Число перестановок без повторений из n элементов – это число способов, сколькими можно расположить на n различных местах n различных элементов.

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

.

Замечание: Мощность искомого множества А удобно искать по формуле:
, гдех – число способов выбрать нужные места; у – число способов расположить на них нужные элементы; z – число способов расположить остальные элементы на оставшихся местах.

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

Всего способов расставить 5 книг на 5-ти местах – равно = 5! = 120.

В задаче х – число способов выбрать два места рядом, х = 4; у – число способов расположить две книги на двух местах, у = 2! = 2; z – число способов расположить остальные 3 книги на оставшихся 3-х местах, z = 3! = 6. Значит
= 48.

Число сочетаний без повторений

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

Число сочетаний без повторений находится по формуле:

.

Свойства:

1)
; 2)
; 3)
;

4)
; 5)
; 6)
.

Пример. В урне 7 шаров. Из них 3 белых. Наугад выбирают 3 шара. Сколькими способами это можно сделать? В скольких случаях среди них будет ровно один белый.

Всего способов
. Чтобы получить число способов выбрать 1 белый шар (из 3-х белых) и 2 черных шара (из 4-х черных), надо перемножить
и
Таким образом искомое количество способов

Упражнения

1. Из 35 учащихся класс по итогам года имели “5” по математике – 14 человек; по физике – 15 человек; по химии – 18 человек; по математике и физике – 7 человек; по математике и химии – 9 человек; по физике и химии – 6 человек; по всем трем предметам – 4 человек. Сколько человек имеют “5” по указанным предметам? Сколько человек не имеет “5” по указанным предметам? Имеет “5” только по математике? Имеет “5” только по двум предметам?

2. В группе из 30 студентов каждый знает, по крайней мере, один иностранный язык – английский или немецкий. Английский знают 22 студента, немецкий – 17. Сколько студентов знают оба языка? Сколько студентов знают немецкий язык, но не знают английский?

3. В 20 комнатах общежития института Дружбы Народов живут студенты из России; в 15 – из Африки; в 20 – из стран Южной Америки. Причем в 7 – живут россияне и африканцы, в 8 – россияне и южноамериканцы; в 9 – африканцы и южноамериканцы; в 3 – и россияне, и южноамериканцы, и африканцы. В скольких комнатах живут студенты: 1) только с одного континента; 2) только с двух континентов; 3) только африканцы.

4. Каждый из 500 студентов обязан посещать хотя бы один из трех спецкурсов: по математике, физике и астрономии. Три спецкурса посещают 10 студентов, по математике и физике – 30 студентов, по математике и астрономии – 25; спецкурс только по физике – 80 студентов. Известно также, что спецкурс по математике посещают 345 студентов, по физике – 145, по астрономии – 100 студентов. Сколько студентов посещают спецкурс только по астрономии? Сколько студентов посещают два спецкурса?

5. Староста курса представил следующий отчет по физкультурной работе. Всего – 45 студентов. Футбольная секция – 25 человек, баскетбольная секция – 30 человек, шахматная секция – 28 человек. При этом, 16 человек одновременно посещают футбольную и баскетбольную секции, 18 – футбольную и шахматную, 17 – баскетбольную и шахматную, 15 человек посещают все три секции. Объясните, почему отчет не был принят.

6. В аквариуме 11 рыбок. Из них 4 красных, остальные золотые. Наугад выбирают 4 рыбки. Сколькими способами это можно сделать? Найти число способов сделать это так, чтобы среди них будет: 1) ровно одна красная; 2) ровно 2 золотых; 3) хотя бы одна красная.

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

8. Из колоды в 36 карт выбирают 4 . Сколько способов сделать это так, чтобы: 1) все карты были разных мастей; 2) все карты были одной масти; 3) 2 красные и 2 черные.

9. На карточках разрезной азбуки даны буквы К, К, К, У, У, А, Е, Р. Сколько способов сложить их в ряд так, что бы получилось «кукареку».

10. Даны карточки разрезанной азбуки с буквами О, Т, О, Л, О, Р, И, Н, Г, О, Л, О, Г. Сколько способов сложить их так, что бы получилось слово «отолоринголог».

11. Даны карточки нарезной азбуки с буквами Л, И, Т, Е, Р, А, Т, У, Р, А. Сколько способов сложить их в ряд так, что бы получилось слово «литература».

12. 8 человек становятся в очередь. Сколько способов сделать это так, что бы два определенных человека А и Б оказались: 1) рядом; 2) на краях очереди;

13. 10 человек садятся за круглый стол на 10 мест. Сколькими способами это можно сделать так, чтоб рядом оказались: 1) два определенных человека А и Б; 2) три определенных человека А, Б и С.

14. Из 10 арабских цифр составляют 5-значный код. Сколькими способами это можно сделать так, чтобы: 1) все цифры были разными; 2) на последнем месте четная цифра.

15. Из 26 букв латинского алфавита (среди них 6 гласных) составляется шестибуквенное слово. Сколькими способами это можно сделать так, чтобы в слове были: 1) ровно одна буква «а»; 2) ровно одна гласная буква; ровно две буквы «а»; в) ровно две гласные.

16. Сколько четырехзначных чисел делятся на 5?

17. Сколько четырехзначных чисел с различными цифрами делятся на 25?

19. Брошены 3 игральные кости. В скольких случаях выпала: 1) ровно 1 «шестерка»; 2) хотя бы одна «шестерка».

20. Брошены 3 игральные кости. В скольких случаях будет: 1) все разные; 2) ровно два одинаковых числа очков.

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

Основные правила комбинаторики.

Комбинаторика - это раздел математики, изучающий способы расположения объектов в соответствии со специальными правилами и методы подсчета числа всех возможных способов. Правило умножения. Если некоторый выбор A можно осуществить m способами, а для каждого из них некоторый другой выбор B можно осуществить n способами, то выбор A и B (в указанном порядке) можно осуществить m×n способами. Пример 1. На гору ведут 6 дорог. Сколькими способами можно подняться на гору и спуститься с горы, если подъем и спуск должен быть по разным дорогам? Решение. Дорогу на гору можно выбрать 6-ю способами, так как подъем и спуск должны быть по разным дорогам, то выбрать дорогу для спуска можно 5-ю способами. Тогда по правилу умножения число способов выбора дороги для подъема и спуска равно 6×5=30. Правило сложения. Если некоторый выбор A можно осуществить m способами, а выбор B можно осуществить n способами, то выбор A или B можно осуществить m+n способами. Пример 2. В ящике имеется 6 красных карандашей, 5 синих и 3 простых карандаша. Сколькими способами можно выбрать цветной карандаш? Решение. Цветной карандаш - это красный или синий, следовательно, по правилу сложения число способов выбора цветного карандаша равно 6+5=11. Замечание. Данные правила можно обобщить на большее число выборов. Вопрос. Сколько основных правил комбинаторики существует?

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

Определение 1. Множество называется упорядоченным, если каждому элементу этого множества поставлено в соответствие некоторое натуральное число от 1 до n, где n - это число элементов данного множества, причем разным элементам поставлены в соответствие разные числа.

Упорядоченные множества считаются различными, если они отличаются либо своими элементами, либо их порядком. Определение 2. Различные упорядоченные множества, составленные из элементов данного множества, отличающиеся лишь порядком элементов, называются его перестановками. Пример 3. Рассмотрим множество M={a,b,c}. Это множество из трех элементов. Составим его различные перестановки: (a,b,c),(a,c,b),(b,a,c),(b,c,a),(c,a,b),(c,b,a). Получили 6 перестановок. P n - число всех перестановок множества из n элементов.

P n =n! (1), где

n!=1·2·3·...·n (читается "н факториал"). Замечание. 0!=1; (n+1)!=n!·(n+1) . Пример 4. Сколько шестизначных чисел, кратных пяти, можно составить из цифр 0,1,2,3,4,5, при условии, что в числе нет одинаковых цифр? Решение. Числа, кратные пяти(делящиеся на пять), оканчиваются либо на 0, либо на 5. Если последняя цифра числа 0, то остальные цифры можно располагать в любом порядке, получим перестановки из пяти элементов, их P 5 =5!=120. Если на конце 5, то остальные можно расположить P 5 =120 способами, но среди них не подходят те, которые начинаются на 0, так как это будут не шестизначные числа. а пятизначные, данных чисел P 4 =4!=24.Тогда требуемых чисел будет 120+120-24=216.

Вопрос. Сколько существует перестановок из шести элементов?

Ваш ответ : 720

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

Если взять цифры 1, 2, 3, 4, то из них можно составить 24 перестановки. Но если взять четыре цифры 1, 1, 2, 2, то можно получить только следующие различные перестановки: (1,1,2,2),(1,2,1,2),(1,2,2,1),((2,2,1,1),(2,1,2,1),(2,1,1,2), то есть шесть перестановок, их в 4 раза меньше, чем перестановок из четырех различных чисел, так как перестановки, в которых меняются местами одинаковые числа - это не новые перестановки, их 2!·2!=4. Рассмотрим задачу в общем виде:пусть имеется множество из элементов, в котором элементывстречаютсяраз, элементывстречаютсяраз,..., элементывстречаютсяраз, причем.

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

Пример 4. Сколькими способами можно расселить 8 студентов по трем комнатам: одноместной, трехместной и четырехместной? Решение. Различныеспособы расселения студентов по комнатам являются перестановками с повторениями, так как внутри, например, трехместной комнаты выбранные студенты могут занимать спальные места по-разному, но эти варианты не будут являться новыми перестановками, поэтому получаем: То есть всего 280 способов расселения студентов.Вопрос. Вычислить

Сочетания.

Пусть некоторое множество содержит n элементов.

Определение 4. Всякое m- элементное подмножество n- элементного множества называется сочетанием из n элементов по m. - число всех сочетаний.

(3)

Пример 5. Для соревнований из 30 спортсменов надо выбрать трех человек. Сколькими способами это можно сделать? Решение. Команда из 3 спортсменов - это подмножество из трех элементов, то есть сочетание из 30 по 3, поэтому количество способов выбора таких команд вычисляется по формуле (3): .

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

1. 2.. Из данных свойств следует, что, тогда, далее,,и так далее. Можно расположить эти числа в виде таблицы:

.....................................................

.......................

Эта таблица в виде треугольника называется треугольником Паскаля.

Определение 5. Выражение a+b называется биномом.

Формула (4) называется биномиальной формулой Ньютона, а коэффициенты называются биномиальными коэффициентами. Из данной формулы вытекает следующее свойство числа сочетаний

Вопрос. .

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

Пусть имеется множество, содержащее n видов элементов, поэтому есть взять какое-то подмножество этого множества, то в нем могут быть одинаковые элементы. Определение 6. Сочетание с повторениями - это m- элементное подмножество множества, содержащего n видов элементов, в котором элементы повторяются. - число всех сочетаний с повторениями из n по m. Состав m- элементного подмножества имеет вид, где. Заменяя каждое из чиселсоответствующим количеством единиц и разделяя единицы нулями, получаем набор, состоящий из m единиц и n-1 нулей. Каждому составу отвечает только одна запись из нулей и единиц, а каждая запись задает только один состав, следовательно, число различных составов равно числу перестановок с повторениями из n-1 нулей и m единиц. Получаем формулу для вычисления всех сочетаний с повторениями.

(5)

Пример 6. В кондитерском магазине продаются пирожные четырех видов: наполеоны, эклеры, песочные и бисквитные. Сколькими способами можно купить 7 пирожных? Решение. Любая покупка - это подмножество, в котором могут быть одинаковые элементы, поэтому это сочетание с повторениями. Число всех возможных покупок находим по формуле (5): .Вопрос. В формуле (5) m может быть больше n.

Размещения

Определение 7. Упорядоченное m - элементное подмножество n- элементного множества называется размещением. - число всех размещений из n элементов по m. Число всех размещений из n по m больше числа всех сочетаний из n по m, так как из каждого подмножества из m элементов с помощью перестановок можно получить m! упорядоченных подмножеств, получаем формулу для числа размещений

(6)

Пример 7. В группе 25 человек. Нужно выбрать актив группы: старосту, заместителя старосты и профорга. Сколькими способами это можно сделать? Решение. Актив группы - это упорядоченное подмножество из трех элементов, так как надо выбрать не только трех человек, но и распределить между ними должности, значит актив группы - это размещение, число всех размещений вычисляем по формуле (6): .Вопрос. Во сколько раз число сочетаний из 20 по 4 меньше числа размещений из 20 по 4?

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

Пусть дано множество из n элементов, в котором есть одинаковые элементы, тогда его подмножества тоже могут содержать одинаковые элементы. Определение 8. Упорядоченные m- элементные подмножества n- элементного множества, в которых элементы могут повторяться, называются размещениями с повторениями. - число всех размещений из n по m. В подмножестве из m элементов первый элемент можно выбрать n способами(то есть любой элемент множества) , так как элементы могут повторяться, то второй элемент тоже можно выбрать n способами, аналогично остальные элементы подмножества можно выбрать n способами, если воспользоваться правилом умножения, получим формулу для вычисления числа размещений с повторениями:

Пример 8. В лифт десятиэтажного дома вошли 5 человек. Каждый из них может выйти на любом этаже, начиная со второго. Сколькими способами они могут это сделать? Решение. Так как каждый человек может выйти на любом этаже, начиная со второго, то этажей для выхода 9. Надо выбрать этажи для возможности выхода каждого человека: для первого человека - можно выбрать любой из девяти этажей, аналогично для остальных пассажиров, тогда по формуле (7): способов.Вопрос. Вычислить .

Перестановка – это комбинация элементов из N разных элементов взятых в определенном порядке. В перестановке важен порядок следования элементов, и в перестановке должны быть задействованы все N элементов.

Задача : Найти все возможные перестановки для последовательности чисел 1, 2, 3.
Существуют следующие перестановки:

1: 1 2 3
2: 1 3 2
3: 2 1 3
4: 2 3 1
5: 3 1 2
6: 3 2 1

Перестановки без повторений

Количество перестановок для N различных элементов составляет N! . Действительно:

• на первое место может быть помещен любой из N элементов (всего вариантов N ),
• на вторую позицию может быть помещен любой из оставшихся (N-1) элементов (итого вариантов N·(N-1) ),
• если продолжить данную последовательность для всех N мест, то получим: N·(N-1)·(N-2)· … ·1 , то есть всего N! перестановок.

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

Рассмотрим алгоритм решения задачи. Дана исходная последовательность чисел. Для получения каждой следующей перестановки необходимо выполнить следующие шаги:

• Необходимо просмотреть текущую перестановку справа налево и при этом следить за тем, чтобы каждый следующий элемент перестановки (элемент с большим номером) был не более чем предыдущий (элемент с меньшим номером). Как только данное соотношение будет нарушено необходимо остановиться и отметить текущее число (позиция 1).
• Снова просмотреть пройденный путь справа налево пока не дойдем до первого числа, которое больше чем отмеченное на предыдущем шаге.
• Поменять местами два полученных элемента.
• Теперь в части массива, которая размещена справа от позиции 1 надо отсортировать все числа в порядке возрастания. Поскольку до этого они все были уже записаны в порядке убывания необходимо эту часть подпоследовательность просто перевернуть.

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

Реализация на С++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

#include
using namespace std;

{
int s = a[i];
a[i] = a[j];
a[j] = s;
}
bool NextSet(int *a, int n)
{
int j = n - 2;
while (j != -1 && a[j] >= a) j--;
if (j == -1)
return false; // больше перестановок нет
int k = n - 1;
while (a[j] >= a[k]) k--;
swap(a, j, k);
int l = j + 1, r = n - 1;
while (l swap(a, l++, r--);
return true;
}
void Print(int *a, int n) // вывод перестановки
{
static int num = 1; // номер перестановки
cout.width(3);
cout << num++ << ": " ;
for (int i = 0; i < n; i++)
cout << a[i] << " " ;
cout << endl;
}
int main()
{
int n, *a;
cout << "N = " ;
cin >> n;
a = new int [n];
for (int i = 0; i < n; i++)
a[i] = i + 1;
Print(a, n);
while (NextSet(a, n))
Print(a, n);
cin.get(); cin.get();
return 0;
}

Результат выполнения

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

Особого внимания заслуживает задача генерации перестановок N элементов в случае если элементы последовательности могут повторяться. Допустим, исходная последовательность состоит из элементов n 1 , n 2 ... n k , где элемент n 1 повторяется r 1 раз, n 2 повторяется r 2 раз и т.д. При этом n 1 +n 2 +...+n k =N . Если мы будем считать все n 1 +n 2 +...+n k элементов перестановки с повторениями различными, то всего различных вариантов перестановок (n 1 +n 2 +...+n k)! . Однако среди этих перестановок не все различны. В самом деле, все r 1 элементов n 1 мы можем переставлять местами друг с другом, и от этого перестановка не изменится. Точно так же, можем переставлять элементы n 2 , n 3 и т. д. В итоге имеем r 1 ! вариантов записи одной и той же перестановки с различным расположением повторяющихся элементов n 1 . Таким образом, всякая перестановка может быть записана r 1 !·r 2 !·...·r k ! способами. Следовательно, число различных перестановок с повторениями равно

Для генерации перестановок с повторениями можно использовать алгоритм генерации перестановок без повторений, приведенный выше. Введем повторяющийся элемент в массив a. Ниже приведен код программы для генерации перестановок с повторениями (изменен только код функции main() ).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#include
using namespace std;
void swap(int *a, int i, int j)
{
int s = a[i];
a[i] = a[j];
a[j] = s;
}
bool NextSet(int *a, int n)
{
int j = n - 2;
while (j != -1 && a[j] >= a) j--;
if (j == -1)
return false; // больше перестановок нет
int k = n - 1;
while (a[j] >= a[k]) k--;
swap(a, j, k);
int l = j + 1, r = n - 1; // сортируем оставшуюся часть последовательности
while (l swap(a, l++, r--);
return true;
}
void Print(int *a, int n) // вывод перестановки
{
static int num = 1; // номер перестановки
cout.width(3); // ширина поля вывода номера перестановки
cout << num++ << ": " ;
for (int i = 0; i < n; i++)
cout << a[i] << " " ;
cout << endl;
}
int main()
{
int n, *a;
cout << "N = " ;
cin >> n;
a = new int [n];
for (int i = 0; i < n; i++)
a[i] = i + 1;
a = 1; // повторяющийся элемент
Print(a, n);
while (NextSet(a, n))
Print(a, n);
cin.get(); cin.get();
return 0;
}

Результат работы приведенного выше алгоритма:

Комбинаторика - это раздел математики, основной задачей которой является подсчёт числа вариантов, возникающих в той или иной ситуации. При решении задач с использованием классического определения вероятности нам понадобятся некоторые формулы комбинаторики.

Размещения .

Определение 1. Размещением без повторений из n элементов по k называется всякое упорядоченное подмножество данного множества M={a 1 ,a 2 ,¼,a n }, содержащее k элементов.

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

Теорема 1. Число различных размещений без повторений из n элементов по k (k£ n) равно

Доказательство.

Пусть M ={a 1 ,a 2 ,¼,a n }. Требуется определить число различных строк вида (x 1 ,x 2 ,¼,x k ), где все элементы x 1 ,x 2 ,¼,x k ÎM и различны. Первый элемент x 1 можно выбрать n способами. Если x 1 уже выбран, то для выбора x 2 осталось n-1 элементов. Аналогично, x 3 можно выбрать n -2 способами и т.д. Последний элемент x k можно выбрать n-k+1 способами. Перемножая эти числа, получим формулу (4).Теорема доказана.

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

Число всевозможных вариантов расписания есть, очевидно, число различных размещений из 12 элементов по 5, то есть

Важным частным случаем, является случай, когда n=k , то есть когда в строке (x 1 ,x 2 ,¼,x n) участвуют все элементы множества M . Строки без повторений, составленные из n элементов множества M называют перестановками из n элементов. Напомним, что в математике через n! обозначают произведение всех натуральных чисел от 1 до n, то есть ¼и по определению считают, что 0!=1.

Следствие 1 . Пользуясь формулой (4), находим, что число различных перестановок P n из n элементов равно P n = n !.

Определение 2. Размещением с повторениями из n элементов по k называется любая упорядоченная строка из k элементов множества M={a 1 ,a 2 ,¼,a n }, некоторые из которых могут повторяться.

Например, слово “мама” есть размещение с повторениями из 2-х элементов M ={м, а} по 4.

Теорема 2. Число различных размещений с повторениями из n элементов по k

Доказательство.

Первый элемент в строку из k элементов может быть выбран n способами, поскольку |M|=n. Точно также 2-й, 3-й, …,k-й элементы могут быть выбраны n способами. Перемножая эти числа, получим

k раз

Теорема доказана.

Пример 2. Сколько можно составить различных двузначных чисел из цифр 1, 2, 3, 4, 5?

В этой задаче M ={1, 2, 3, 4, 5}, n=5, k=2.Поэтому ответом является число

Пример 3. Сколькими способами k пассажиров могут распределиться по n вагонам, если для каждого пассажира существенным является только номер вагона, а не занимаемое им в вагоне место?

Перенумеруем всех пассажиров. Пусть x 1 - номер вагона, выбранного первым пассажиром, x 2 - номер вагона второго пассажира, …, x k - номер вагона k -го пассажира. Строка (x 1 ,x 2 ,¼,x k ) полностью характеризует распределение пассажиров по вагонам. Каждое из чисел x 1 ,x 2 ,¼,x k может принимать любое целое значение от 1 до n. Поэтому в этом примере

M ={1, 2,…,n} и различных распределений по вагонам будет столько же, сколько строк длиной k можно составить из элементов множества M , то есть

Отметим ещё раз, что в размещениях с повторениями и без повторений важен порядок следования элементов. Если порядок следования элементов не существенен, то в этом случае говорят о сочетаниях.

Сочетания (без повторения ).

Определение 3. Пусть M={a 1 ,a 2 ,¼,a n }. Любое подмножество X мно-жества M , содержащее k элементов, называется сочетанием k элементов из n.

Отметим сразу, что в этом определении порядок следования элементов множества X несущественен и, что k£n , поскольку k=½X½, n=½M½ и XÍM .

Теорема 3. Число различных сочетаний k элементов из n равно

. (6)

Доказательство.

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

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

Правило умножения (основная формула комбинаторики)

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

Пример 1

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

Решение

Первая монета имеет альтернативы – либо орел, либо решка. Для второй монеты также есть альтернативы и т.д., т.е. .

Искомое количество способов:

Правило сложения

Если любые две группы и не имеют общих элементов, то выбор одного элемента или из , или из , …или из можно осуществить способами.

Пример 2

На полке 30 книг, из них 20 математических, 6 технических и 4 экономических. Сколько существует способов выбора одной математической или одной экономической книги.

Решение

Математическая книга может быть выбрана способами, экономическая - способами.

По правилу суммы существует способа выбора математической или экономической книги.

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

Размещения – это упорядоченные совокупности элементов, отличающиеся друг от друга либо составом, либо порядком элементов.

Размещения без повторений , когда отобранный элемент перед отбором следующего не возвращается в генеральную совокупность. Такой выбор называется последовательным выбором без возвращения, а его результат – размещением без повторений из элементов по .

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

Пример 3

Расписание дня состоит из 5 различных уроков. Определите число вариантов расписания при выборе из 11 дисциплин.

Решение

Каждый вариант расписания представляет набор 5 дисциплин из 11, отличающихся от других вариантов как составом, так и порядком следования. поэтому:

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

Пример 4

Сколькими способами можно рассадить 4 человек за одним столом?

Решение

Каждый вариант рассадки отличается только порядком участников, то есть является перестановкой из 4 элементов:

Размещения с повторениями , когда отобранный элемент перед отбором следующего возвращается в генеральную совокупность. Такой выбор называется последовательным выбором с возвращением, а его результат - размещением с повторениями из элементов по .

Общее число различных способов, которыми можно произвести выбор с возвращением элементов из генеральной совокупности объема , равно

Пример 5

Лифт останавливается на 7 этажах. Сколькими способами могут выйти на этих этажах 6 пассажиров, находящихся в кабине лифта?

Чтобы решение задачи по теории вероятностей было максимально точным и верным, многие недорого заказывают контрольную работу на этом сайте. Подробно (как оставить заявку, цены, сроки, способы оплаты) можно почитать на странице Купить контрольную работу по теории вероятностей...

Решение

Каждый из способов распределения пассажиров по этажам представляет собой комбинацию 6 пассажиров по 7 этажам, отличающуюся от других комбинаций как составом, так и их порядком. Так как одном этаже может выйти как один, так и несколько пассажиров, то одни и те же пассажиры могут повторяться. Поэтому число таких комбинаций равно числу размещений с повторениями из 7 элементов по 6:

Сочетания

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

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

Число сочетаний из элементов по равно:

Пример 6

В ящике 9 яблок. Сколькими способами можно выбрать 3 яблока из ящика?

Решение

Каждый вариант выбора состоит из 3 яблок и отличается от других только составом, то есть представляет собой сочетания без повторений из 9 элементов:

Количество способов, которыми можно выбрать 3 яблока из 9:

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

Число сочетаний с повторениями из элементов по :

Пример 7

На почте продают открытки 3 видов. Сколькими способами можно купить 6 открыток?

Это задача на отыскание числа сочетаний с повторениями из 3 по 6:

Разбиение множества на группы

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

Число разбиений на групп, когда в первую попадают элементов, во вторую - элементов, в k-ю группу - элементов, равно:

Пример 8

Группу из 16 человек требуется разбить на три подгруппы, в первой из которых должно быть 5 человек, во второй – 7 человек, в третьей – 4 человека. Сколькими способами это можно сделать?

Решение

Здесь

Число разбиений на 3 подгруппы: