Соединения без повторения

Решение

КОМБИНАТОРИКА

Два основных правила комбинаторики:

1) Правило умножения

Если действие A ₁ можно осуществить k ₁ способами, действие A ₂ – k ₂ способами, действие A_n – k_n способами, то совокупность действий A ₁, A ₂,..., A_n можно осуществить k ₁ · k ₂ ·... · k_n способами.

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

1 цифр – 5 сп.

2 цифр – 6 сп.

3 цифр – 3 сп.

n = 5 · 6 · 3 = 90 способов.

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

Если объект A ₁ можно выбрать k ₁ способами, объект A ₂ – k ₂ способами и т.д., A_n – k_n способами, то объект, содержащий A ₁ или A ₂ или... или A_n можно выбрать k ₁ + k ₂ +... + k_n способами.

К основным соединениям в комбинаторике относятся размещения, перестановки, сочетания.

1. Размещение

Выборки из n -элементов по m -элементов в каждой, отличающиеся набором элементов или порядком их следования называются размещениями из n -элементов по m.

пример. (a; b; c). Размещения из 3^х элементов по 2.

(a; b); (b; a); (a; c); (c; a); (b; c); (c; b).

– число размещений из n -элементов по m.

пример. Комиссия состоит из председателя, заместителя и ещё 5 членов. Сколькими способами можно распределить обязанности председателя и заместителя?

Дата добавления: 2014-01-07