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

Теорема [1/2] Общее количество различных наборов при выборе k элементов из n без возвращения и с учетом порядка равняется: n×(n – 1)×(n – 2)×…×(n – k + 1) = n!/(n – k)! и называется числом размещений из n элементов по k элементов: A^k_n .

Доказательство Первый шар можно выбрать n способами, второй шар – (n – 1) способами, третий шар – (n – 2) способами, ..., k-ый шар – [n – (k – 1)]= (n – k + 1) способами. Тогда по правилу умножения получаем искомое выражение.

Следствие Общее количество различных наборов при выборе n элементов из n без возвращения и с учетом порядка равняется: n×(n – 1)×(n – 2)×…×(n – k + 1)×…×2×1 = n! и называется числом перестановок из n элементов по n элементов: P_n = Aⁿ_n = n!.

Теорема [1/1] Общее количество различных наборов при выборе k элементов из n без возвращения и без учета порядка равняется: n!/[k!×(n – k)!] и называется числом сочетаний из n элементов по k элементов: C^k_n = A^k_n / k!.

Доказательство Согласно следствию из предыдущей теоремы, k различных номеров шаров можно упорядочить k! способами. Поэтому из каждого набора, выбранного без возвращения и без учета порядка, можно образовать k! наборов, отличающихся друг от друга не составом, а только порядком следования номеров. Т.е. при выборе без возвращения и с учетом порядка возможно в k! раз больше наборов, чем при выборе без учета порядка. Поэтому число наборов при выборе без учета порядка равно A^k_n / k!

Следствие Размещения, перестановки и сочетания связаны соотношением: A^k_n = P_k×C^k_n .

Теорема [2/2] Общее количество различных наборов при выборе k элементов из n с возвращением и с учетом порядка равняется n^k.

Доказательство Первый шар можно выбрать n способами. При каждом из этих способов второй шар можно выбрать также n способами, и так k раз. Общее число наборов равно n^k.

Теорема [2/1] Общее количество различных наборов при выборе k элементов из n с возвращением и без учета порядка равняется: C^k_n+k–1.

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

Все мыслимые размещения шаров по ящикам можно получить, меняя местами шары и внутренние перегородки ящиков. Число таких мест, которые можно занять либо шарами, либо внутренними перегородками равно n – 1 + k. Количество способов расставить k шаров на этих n – 1 + k местах, заполняя оставшиеся места перегородками, равно C^k_n+k–1.

В рассмотренном эксперименте количество шаров k_i в i-ом ящике соответствует k_i раз появлению i-го элемента в выборке из n элементов по k элементов согласно условию теоремы.

Задачи

№11. Сколько трехзначных чисел можно составить из различных цифр (A³₁₀ – A²₉ = 10!/(10 – 3)! – 9!/(9 – 2)! = 10!/7! – 9!/7! = 8×9×10 – 8×9 = 720 – 72 = 648).

№12. Президент банка должен назначить двух вице-президентов из числа пяти директоров. Сколько вариантов имеется у президента, если:

а) вице-президенты по должности не равны (A²₅ = 5!/(5 – 2)! = 120/6 = 20);

б) вице-президенты по должности равны (C²₅ = 5!/[2!×(5 – 2)!] = 120/(2×6) = 10).

№13. Сколько различных слов можно составить, переставляя буквы в слове "мама"? (N₁ = P₄ = 4! = 24 – если цвет букв разный; и N₂ = P₄/(P₂×P₂) = 4!/(2!×2!) = 24/4 = 6 – если цвет букв одинаковый: «ммаа», «мама», «маам», «амма», «амам», «аамм»).

№14. Сколько различных слов можно составить, переставляя буквы в слове "математика"? (N₁ = P₄ = 10! = 3 628 800 – если цвет букв разный; и N₂ = P₄/(P₂×P₃×P₂) = 10!/(2!×3!2!) = 3628800/24 = 151 200 – если цвет букв одинаковый).