Комбинаторика

Question 1

Комбинаторика

Answer 1

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

Question 2

Правило суммы

Answer 2

Пусть А и В — конечные непересекающиеся множества из m и n элементов соответственно, тогда количество элементов в их объединении — m+n.

Question 3

Правило суммы: Альтернативная формулировка

Answer 3

Пусть выбор A можно осуществить m способами, а выбор B — n способами. Тогда выбор «либо A, либо В» можно осуществить m+n способами.

Question 4

Правило произведения

Answer 4

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

Question 5

Правило произведения: Альтернативная формулировка

Answer 5

Пусть выбор А можно осуществить m способами, и для каждого из таких способов некоторый другой выбор B — n способами. Тогда выбор «А и В» в указанном порядке можно осуществить mn способами.

Question 6

Правило биекций

Answer 6

Пусть даны множества А, В и А содержит m элементов. Если существует биекция из А в В, то В тоже состоит из m элементов

Question 7

k-размещение

Answer 7

Пусть дано множество S из n элементов. Упорядоченный набор (a1..ak) элементов из S называется k-размещением, если все элементы этого набора различны. Если допускается, что элементы этого набора могут быть одинаковыми, он называется k-размещением с повторениями.

Question 8

k-сочетание

Answer 8

Неупорядоченный набор (a1..ak) называется k-сочетанием, если все его элементы попарно различны. И k-сочетанием с повторениями, если среди них допускаются одинаковые.

Question 9

Число k размещений из n элементов

Answer 9

Akn = n! / (n-k)!

Question 10

Число k размещений из n элементов (с повторениями)

Answer 10

Akn с волной = n^k

Question 11

Число k сочетаний из n элементов

Answer 11

Ckn = n! / (k! (n-k)!)

Question 12

Следствие о длине булеана от множества

Answer 12

B(S) = 2^n (здесь имеется в виду мощность)

Question 13

Сколько существует разбиений множества S из n элементов на непересекающиеся множества A и В мощностью k и n-k элементов соответственно

Answer 13

Таких разбиений Ckn

Question 14

Что называется k1,k2, km- разбиением

Answer 14

Упорядоченный набор (S1, S2..Sm) подмножеств S (из n элементов), если выполняются условия:
1) Si, Sj не пересекаются
2) объединение всех Si = S
3) Si состоит из ki элементов
4) k1+…km = n

Question 15

Число разбиений P(k1,k2..km)

Answer 15

n! / (k1! k2!…km!)

Question 16

Следствие из биномиальной теоремы

Answer 16

1) C0n + C1n + C2n + … + Cnn = 2^n
2) C0n - C1n + C2n … + (-1)^n Cnn = 0

Question 17

Полиномиальная теорема

Answer 17

(x1+x2+..xk)^n = сумме P(m1…mk)(x1)^m1(x2)^m2..(xk)^mk,
здесь m1 +…mk = n

Question 18

Биномиальная теорема

Answer 18

(x+y)^n = сумма из n слагаемых следующего вида;
Cin * x^(n-i) * y^i

Question 19

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

Answer 19

Сkn с волной = Ck(n+k-1) = C(n-1)(n+k-1)

Question 20

Число различных перестановок из n элементов, среди которых есть m1 элементов первого типа … mk элементов k-го типа, причем m1+..mk = n

Answer 20

n! / (m1! m2! … mk! )

Question 21

n(Pi1, Pi2.. Pit)

Answer 21

Число элементов из S, обладающих каждым из свойств Pi1…Pit

Question 22

Формула включения и исключения

Answer 22

n(0)= (S) - сумма(n(Pi)) + сумма(n(Pi1, Pi2)) + (-1)^s сумма(n(Pi1…Pis)) + (-1)^k сумма(n(Pi1, Pi2…Pik))
Здесь везде суммирование идет до к