2014-02-04
773
Основное правило комбинаторики
Рассмотрим такую задачу. Пусть из пункта А города Киева в пункт В можно доехать тремя видами транспорта: ((Т) троллейбус, (А) автобус и (М) метро), а из пункта В в пункт С - только двумя видами транспорта: ((Т) троллейбус и (А) автобус). Сколькими способами можно доехать из пункта А в пункт С города Киева? Решение этой задачи сводится, очевидно, к подсчету числа элементов в декартовом произведении множеств {А, Т, М} х {А, Т}. Число таких элементов, как мы знаем, равно произведению числа элементов первого множества на число элементов второго множества, т. е. в нашем случае это 3*2 = 6. Следовательно, существует шесть способов доехать из пункта А в пункт С. Оказывается, что за этой простой задачей стоит правило, которое называется основным правилом комбинаторики.
Пусть необходимо выполнить последовательно k действий. Если первое действие можно выполнить n1 способами, второе – n2способами и так далее до k-го действия, которое можно выполнить nk способами, то все k действий можно выполнить n1*n2*…*nk способами.
|
|
|
Пример1:
Сколькими способами на первенстве мира по футболу могут распределиться медали, если в финальной части играют 24 команды? Решение. Золотую медаль может получить любая из 24 команд, т. е. имеем 24 возможности. Серебряную медаль может выиграть одна из 23 команд, а бронзовую - одна из 22 команд. По основному правилу комбинаторики общее число способов распределения медалей 24. 23. 22 = 12 144.
Пример 2:
Сколько трехзначных чисел можно составить из цифр 0, 1,2,3,4, 5, если:
Цифры могут повторяться.
Решение. Первой цифрой может быть одна из цифр 1,2,3,4,5, поскольку 0 не может быть первой цифрой, ибо в таком случае число не будет трехзначным. Если первая цифра выбрана, то вторая может быть выбрана шестью способами, как и третья цифра. Следовательно, общее число трехзначных цифр 5*6*6 = 180.
Ни одна из цифр не повторяется дважды.
Решение. Первой цифрой может быть одна из пяти цифр - 1,2, 3, 4, 5. Если первая цифра выбрана, то второй может быть также одна из пяти цифр (тут уже учитывается 0), а третья может быть выбрана четырьмя способами из четырех цифр, что остались. Следовательно, общее количество таких трехзначных чисел 5*5*4 = 100.
Цифры нечетные и могут повторяться.
Решение. Первой цифрой может быть одна из трех цифр: 1, 3, 5. Второй тоже может быть одна из этих трех цифр. Аналогично и третья цифра может быть выбрана тремя способами. Таким образом, общее количество таких чисел равняется 3*3*3 = 27.
Пусть А и В – непустые множества такие, что
и 
. Тогда 
. Определение: Если элемент 
можно выбрать m способами, а элемент 
– n способами, то выбор элемента 
можно осуществить m+n способами.
|
|
|
Пусть X1,X2,…,Xk – попарно непересекающиеся множества, 
, где 
, тогда очевидно выполняется неравенство
.
