Элементов по k Сочетание из

Размещение из n элементов по k	Сочетание из n элементов по k	Размещение с повторениями из n элементов по k	Сочетание с повторениями из n элементов по k.
выборка объема k из n элементов
(упорядоченная) без повторений	{неупорядоченная} без повторений	(упорядоченная) с повторениями	{неупорядоченная} с повторениями
примеры пусть множество M состоит из 3-ех элементов:M={1, 2, 3} или пусть имеется 3 ящика и 2 шара. Сколько способов разместить k шаров по n ящикам в зависимости от некоторых условий
размещение из 3 по 2 – шесть упорядоченных выборок без повторений	сочетание из 3 по 2 – три неупорядоченные выборки без повторений	размещение с повторениями из 3 по 2 – девять упорядоченных выборок с повторениями	сочетание с повторениями из 3 по 2 – шесть неупорядоченных выборок с повторениями
(1,2), (1,3), (2,3), (2,1), (3,1), (3,2).	{1,2}, {1,3}, {2,3}. { , },{ , },{ , }	(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3).	{1,1}, {1,2}, {1,3}, { , }, {2,2}, {2,3}, { , }, { , }, {3,3}.
2(k) различных шара по 3-ем(n) ящикам в ящик не более 1 шара	2(k) любых (т.е. одинаковых) шара по 3-ем(n) ящикам в ящик не более 1 шара
		2(k) различных шара по 3-ем(n) ящикам в ящик любое кол-во шаров	2(k) любых (т.е. одинаковых) шара по 3-ем(n) ящикам в ящик любое кол-во шаров
Число перестановок из n элементов без повторений		Число перестановок с повторениями из n элементов –имеется n элементов m различных типов, и рассматриваются перестановки из всех этих элементов с точностью до порядка следования однотипных элементов – количество элементов i-го типа и .	(неупорядоченная выборка из n элементов по k с возвращениями, выбранный элемент каждый раз возвращается обратно)

Теорема: Число размещений без повторений из n элементов по k	Теорема: Число сочетаний без повторений из n элементов по k	Теорема: Число размещений с повторениями из n элементов по k	Теорема: Число сочетаний с повторениями из n элементов по k
доказательства
Доказательство: В k-размещении (а1, a2,…,ak) n-элементного множества M элемент а1можно выбрать n способами. После этого элемент a2 можно выбрать n – 1 способами (из оставшихся n – 1 элементов множества M). После этого элемент a3 можно выбрать n – 2 способами. И так далее. Наконец, элемент ak можно выбрать n – k + 1 способами. По правилу произведения: n (n – 1) (n – 2)… (n – k + 1); умножив и разделив правую часть равенства на (n – k)(n – k – 1)…3∙2∙1. Получим Обозначают Следствие: Число перестановок n-элементного множества без повторений Pn = n!	Доказательство: Обозначим через число сочетаний без повторений из n элементов по k. Каждому k -сочетанию (а1, a2,…,ak) n-элементного множества M соответствует k! перестановок. Тогда число размещений откуда и следует требуемая формула. Обозначают	Доказательство: В k-размещении (а1, a2,…,ak) n-элементного множества M элемент а1 можно выбрать n способами, элемент a2 – тоже n способами, наконец, элемент ak – n способами. По правилу произведения Следствие: Рассмотрим n элементов m различных типов, причем в каждом типе все элементы одинаковы. Тогда перестановки из всех этих элементов с точностью до порядка следования однотипных элементов называются перестановками с повторением. Если – количество элементов i-го типа, то и количество всевозможных перестановок с повторениями равно .	Доказательство: Каждому k -сочетанию (а1, a2,…,ak) n-элементного множества M=(а1, a2,…, ai,…,an) взаимно однозначно сопоставим вектор с n + k – 1 координатами, состоящий из n – 1 нулей и k единиц. Нули «разделяют» вектор на n частей так, что на каждом i-ом месте стоит столько единиц, сумма которых равна количеству вхождений элемента ai из M в k -сочетание (а1, a2,…,ak) Общее число единиц в векторе равно k. В нашем примере для M={a, b, c} получим {a,a}↔{1,1,0,0}, {a,b}↔{1,0,1,0}, {a,c}↔{1,0,0,1}, {b,b}↔{0,1,1,0}, {b,c}↔{0,1,0,1}, {c,c}↔{0,0,1,1}. Вопрос: сколько таких векторов? Сколькими способами из n + k – 1 координат можно выбрать k координат, в которых будут стоять единицы? ИЛИ Пусть n – 1 нулей – это n – 1 перегородка, разделяющие n ячеек, в каждую i-ую ячейку положим столько шаров, сколько раз повторяется ai элемент из M в k -сочетании (а1, a2,…,ak). {a,a}↔{| | }, {a,b}↔{|| }, {a,c}↔{| |}, {b,b}↔{ || }, {b,c}↔{ ||}, {c,c}↔{ | |}. Если M = {a, b, c, d, e}, то сочетанию {a, b, b, c, c, e, e} сопоставим разбиение  |  | | |  Всего шаров k = 7, перегородок n – 1 = 4, а промежутков между шарами k – 1 = 6. Это соответствует расстановке в ряд k шаров и n – 1 перегородок так, чтобы между (i – 1) -ой и (i) -ой перегородками находилось ровно столько шаров, сколько раз  входит элемент ai из M в k -сочетание (а1, a2,…,ak). Таких расстановок