Теория вероятностей элементы комбинаторики

Осмотрим некоторое множество Х
Х
, состоящее из n
n
частей X=x1,x2,...,xn
X
=

x
1
,
x
2
,
.
.
.
,
x
n

. Будем выбирать из этого множества различные упорядоченные подмножества Y
Y
из k
k
частей.

Размещением из n
n
частей огромного количества Х
Х
по k
k
элементам назовем любой упорядоченный набор (xi1,xi2,...,xik)
(
x
i
1
,
x
i
2
,
.
.
.
,
x
i
k
)
частей множества Х
Х
.

Если выбор частей огромного количества Y
Y
из Х
Х
происходит с возвращением, т.е. каждый элемент огромного количества Х
Х
может быть избран несколько раз, то число размещений из n
n
по k
k
находится по формуле nk
n
k
(размещения с повторениями).

Если же выбор делается без возвращения, т.е. каждый элемент множества Х
Х
можно избирать только один раз, то количество размещений из n
n
по k
k
обозначается Akn
A
n
k
и определяется равенством
Akn=n(n1)...(nk+1)=n!(nk)!.
A
n
k
=
n

(
n

1
)

.
.
.

(
n

k
+
1
)
=
n
!
(
n

k
)
!
.
(размещения без повторений).

Пример. Пусть даны шесть цифр: 1; 2; 3; 4; 5; 6. Найти сколько трехзначных чисел можно составить из этих цифр.

Решение. Если числа могут повторяться, то количество трехзначных чисел будет m=nk=63=216
m
=
n
k
=
6
3
=
216
. Если цифры не повторяются, то m=A36=654=120
m
=
A
6
3
=
6

5

4
=
120
.

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

Решение. Расписание на каждый день может отличаться либо предметами, или порядком расположения этих предметов, поэтому имеем размещения: A310=1098=720
A
10
3
=
10

9

8
=
720
.

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

Приватный случай размещения при n=k
n
=
k
называется перестановкой из n
n
элементов. Число всех перестановок из n
n
элементов равно Ann=Pn=n!
A
n
n
=
P
n
=
n
!
.

Пример. 30 книжек стоит на книжной полке, из их 27 разных книг и 1-го автора три книги. Сколькими способами можно расставить эти книги на полке так, чтоб книги 1-го творца стояли рядом?

Решение. Будем считать три книжки 1-го творца за одну книгу, тогда число перестановок будет P28
P
28
. А три книги можно переставлять меж собой P3
P
3
способами, тогда по правилу творения имеем, что искомое число методов одинаково: N=P3P28=3!28!
N
=
P
3

P
28
=
3
!

28
!
.

Сочетания

Пусть теперь из огромного количества Х
Х
выбирается неупорядоченное подмножество Y
Y
(порядок частей в подмножестве не имеет значения). Сочетаниями из n
n
частей по k
k
именуются подмножества из k
k
частей, отличающиеся друг от друга хотя бы одним элементом. Общее число всех сочетаний из n
n
по k
k
обозначается Ckn
C
n
k
и одинаково
Ckn=Aknk!=n!(nk)!k!=n(n1)...(nk+1)k!.
C
n
k
=
A
n
k
k
!
=
n
!
(
n

k
)
!

k
!
=
n

(
n

1
)

.
.
.

(
n

k
+
1
)
k
!
.

Правосудны равенства:
C0n=1,Cnn=1,Ckn=Cnkn.
C
n
0
=
1
,
C
n
n
=
1
,
C
n
k
=
C
n
n

k
.

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

Решение. Так как порядок студентов не главен, используем формулу для числа сочетаний:
C327=27!24!3!=272625123=2925.
C
27
3
=
27
!
24
!

3
!
=
27

26

25
1

2

3
=
2925.

Подробности и онлайн калькуляторы для комбинаторики

Еще наглядно с картинками и примерами про главные формулы комбинаторики (размещения, перестановки, сочетания) и их применение для решения задач тут: Формулы комбинаторики. Для прыткого нахождения значений - онлайн-калькуляторы:

Вычисление числа перестановок (факториал)
Вычисление числа размещений
Вычисление числа сочетаний
Правила суммы и творения

При решении задач комбинаторики употребляют следующие верховодила:

Правило суммы. Если некий объект А
А
может быть избран из совокупы объектов m
m
методами, а другой объект В
В
может быть избран n
n
методами, то избрать либо А
А
, или В
В
можно m+n
m
+
n
методами.

Правило творения. Если объект А
А
можно выбрать из совокупы объектов m
m
методами и после каждого такового выбора объект В
В
можно избрать n
n
методами, то пара объектов (А,В)
(
А
,
В
)
в обозначенном порядке может быть выбрана mn
m

n
способами.

Пример. Наряд студентки состоит из блузы, юбки и туфель. Женщина имеет в собственном гардеробе четыре блузы, 5 юбок и трое туфель. Сколько нарядов может иметь студентка?

Решение. Пусть поначалу студентка избирает блузу. Этот выбор может быть совершен четырьмя методами, так как студентка имеет четыре блузы, потом пятью методами произойдет выбор юбки и тремя методами выбор туфель. По принципу умножения выходит 4*5*3=60 нарядов (композиций).