1.1 общие правила комбинаторикиПравило суммы Если некоторый объект А можно выбрать т способами, а объект В - k: способами (не такими, как А), то объект либо А, либо В можно выбрать т+k способами. Пример. В ящике имеется m разноцветных шариков. Произвольным образом вынимаем один шарик. Сколькими способами это можно сделать? Конечно, т способами. Теперь эти n шариков распределены но двум ящикам: в первом т шариков, во втором k. Произвольно из какого-нибудь ящика вынимаем один шарик. Сколькими разными способами это можно сделать? Из первого ящика шарик можно вытянуть т различными способами, из второго k: различными способами, всего п=т+k способами. Правило произведения Если объект А можно выбрать т способами, а после каждого такого выбора другой объект В можно выбрать (независимо от выбора А) k способами, то пары объектов А и В можно выбрать т+k способами. Задача. Сколько можно записать двузначных чисел в десятичной системе счисления? Поскольку число двузначное, то число десятков (т) может принимать одно из девяти значений: 1,2,3,4,5,6,7,8,9. Число единиц (k) может принимать те же значения и может, кроме того быть равным нулю. Отсюда следует, что т=9, а k=10. Всего получим двузначных чисел n=m*k =9*10=90. Следствие. Правило произведения справедливо и для любого конечного числа объектов. Если некоторый объект Аi(i=1, 2, ..., п) можно выбрать Кi (i=1,2, ..., п) способами (причем, каждый следующий объект выбирается независимо от выбора предыдущего объекта), то объекты А1,А2,…,Аn можно выбрать k =k1*k2*…kn способами. Например, сколькими способами можно составить трехзначное число, делящееся на 5? Число имеет три позиции, каждую из которых мы назовем событием: — событие A1, — число сотен, их можно выбрать k1= 9 (все цифры, кроме 0) способами; — событие A2— число десятков, их можно выбрать k2=10 (все цифры , включая 0) способами; — событие А3 — число единиц, которым удовлетворяет только две цифры: 0 и 5. следовательно, k3 = 2. Таким образом, всего получаем n = k1*k2*k3 =9*10*2=180 чисел. |
| Оглавление| |