Спирина, М.С. Дискретная математика

взятых из множества, состоящего из л элементов. Число сочета­ ний обозначается С " (от фр. combinaison — сочетание). Для подсчета числа сочетаний возьмем формулу размещений дт и поделим ее на число перестановок в подмножестве (так как порядок в сочетаниях не важен). Тогда формула сочетаний без повторений имеет вид ст _ К _ п\ " Рт т \ ( п - т ) \ ‘ Отсюда видно , что С„и = я: т\ {п-т) \ =сг Отметим важные частные случаи: при т = 0 и т = л имеем С®= Сяи= 1; при т = 1 CJ = С„”-1 = я; при т = 2 С„2 = С"“2 Сочетания имеют большое практическое применение в р а з ­ личных разделах математики, например в формуле бинома Нью­ тона: Ve, й е R, V« е N U {0} (а + />)" = £ Скпап-кЪк. к =О Задача 4. Сколькими способами могут взойти 3 зерна пшени­ цы, если посажено 7 зерен? Решение. По условию задачи порядок в подмножестве из 3 з е ­ рен не важен, поэтому по формуле сочетаний имеем: С73 = 7! 3! 4! 5 -6 -7 2-3 = 35. Перестановки с повторениями. Если в кортеже имеются повто­ ряющиеся элементы, то формула Р„ = п\ уже неприменима, п о ­ скольку при переставлении одинаковых элементов кортеж не и з ­ менится. Кортеж, имеющий повторяющиеся элементы, называет­ ся перестановкой с повторениями. Пусть дан кортеж длины п, состоящий из элементов множе­ ства А = {аь а2, ..., ат) (т < п). Отсортируем в кортеже элементы: каждому числу к (1 < к < т) ставится в соответствие число пк, показывающее сколько раз элемент ак встретился в этом кортеже. т Тогда « = 2 > - Очевидно, что перестановка одинаковых элемен- к=\ тов внутри некоторого А:-го сорта не изменит кортежа, т. е. среди я! всех перестановок будет пк\ тождественных. Уменьшим число перестановок из я (я!), убрав повторяющиеся кортежи обратным 49