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

действием (разделив на л,!, л2! , ..., пт\). Тогда число перестановок с повторениями, имеющих такой состав, найдем по формуле л! т Пл*! к=\ Частные случаи 1. Если пх = п2 - ... = пк = ... = пт= 1, то т = п. Тогда формула должна дать число перестановок без повторений. Действительно, 2. Если л, = п2- ... = лт_] = 1, пт= п - (т - 1), то р _ ____ — ____ — Ат - 1 - („ - m + 1)! * ^ • 3. Пусть т = 2, пх=р, а л2 = л - р. Тогда число перестановок с повторениями, где все множество из л элементов разделено на две группы из л, = р и из л2 = л - р элементов, — это фактически число сочетаний, так как порядок не важен ни в одном из них. ^ п ^ Отсюда сразу получается формула Q = Р р,п-р = ^ = СЦ~Р. Задача 5. Сколькими способами можно расставить белые фигу­ ры на первой линии шахматной доски? Решение. На первой линии могут находиться король, ферзь, 2 ладьи, 2 коня и 2 слона. Без учета общепринятых шахматных правил составим кортежи длины 8, имеющие указанный состав (1, 1, 2, 2, 2). Тогда число перестановок с размещениями найдем по формуле Р < 1 , 1 , 2 , 2 , 2 ) = = 5040. Задача 6. Найти число точек пересечения диагоналей выпукло­ го л-угольника, если никакие три из них не пересекаются в одной точке. Решение. Минимальный многоугольник с диагоналями имеет четыре вершины (л > 4). Если взять любые 4 вершины многоуголь­ ника, то через них можно провести С\ = 6 диагоналей, имеющих пять точек пересечения, но только одна из них лежит внутри мно­ гоугольника (рис. 1.18). Наоборот, каждой точке пересечения диа­ гоналей поставим в соответствие четверку вершин многоугольни­ ка. Такое соответствие является взаимно-однозначным, а порядок вершин не важен. Поэтому число внутренних точек пересечения диагоналей многоугольника (и число четверок-вершин) можно найти с помощью сочетаний С„. Р _ (И1 + п 2 +••• + лт )! р _ ^ • Л2> - щ\ П 2 '....пт\ П"П2 ... "" “ 50