Сочетания с повторениям

.

Ответ: 2520 перестановок.

Пример 2.4: Сколькими способами можно расселить 8 студентов по 3 комнатам: одноместной, трехместной и четырехместной?

Решение: n =8, n₁ =1, n₂ =3, n₃ =4.

.

Ответ: 280 способов.

§ 3. Размещения

Рассмотрим теперь такие перестановки из n различных элементов, в которых участвуют не все, а только определенное количество элементов.

Определение 3.1: Размещениями называют комбинации, составленные из n различных элементов по k элементам, которые различаются либо составом элементов, либо их порядком.

Число всех возможных размещений определяют по формуле:

.

Пример 3.1: Сколькими способами из 7 книг можно отобрать 3 и расставить их на 3 места на книжной полке?

Решение:

1 способ. n = 7, k =3.

.

2 способ. Эту задачу можно также решить по принципу произведения.

Книги должны занять 3 места. На 1 место можно поставить любую из 7 книг, на 2 место – любую из оставшихся 6, а 3 место может заполнить любая из оставшихся 5 книг. Таким образом, общее количество способов равно 7*6*5=210.

Ответ: 210 способов.

Пример 3.2: Определить количество телефонных номеров, состоящих из 5 различных цифр.

Решение:

.

Ответ: 30240 телефонных номеров.

Размещения с повторениями.

Если каждый из k элементов упорядоченного множества может быть выбран n способами, независимо от других, то число способов выбора всех k элементов вычисляется по формуле:

Пример 3.3: В НИИ работает 4 курьера А, В, С, D. Сколько существует способов рассылки 7 писем в 7 различных организаций, если доставка писем осуществляется только курьерами, работающими в НИИ?

Решение:

.

Ответ: 16384 способа.

Пример 3.4: В кабину лифта 9-этажного здания вошло 3 пассажира A, B, C, каждый из которых может выйти на любом из 8 этажей. Сколькими способами может осуществиться разгрузка лифта?

Решение:

.

Ответ: 512 способов.

§ 4. Сочетания

Определение 4.1 .: Сочетаниями называюткомбинации, составленные из n различных элементов по k элементам, которые отличаются хотя бы одним элементом.

Число сочетаний определяется по формуле:

.

Замечание 4.1. Разница между размещениями и сочетаниями состоит в том, что в размещениях порядок элементов учитывается, а в сочетаниях – нет.

Пример 4.1.: Сколькими способами можно выбрать 2 детали из ящика, содержащего 10 деталей?

Решение:

.

Ответ: 45 способов.

Пример 4.2.: Сколькими способами можно составить комиссию из 3^х человек, выбирая их из 4^х супружеских пар, если:

а) в комиссию могут входить любые трое из данных 8 человек;

б) комиссия должна состоять из двух женщин и одного мужчины?

Решение:

а) В комиссии не играет роли порядок членов, поэтому

.

б) двух женщин можно отобрать способами. Затем одного мужчину можно отобрать способами. Всю комиссию можно составить

.

Ответ: 24 способами.

Сочетаниями из n элементов по k элементов с повторениями называются группы, содержащие k элементов, причём каждый элемент принадлежит одному из n типов. Число различных сочетаний из n элементов по k элементам с повторениями вычисляется по формуле:

Пример 4.3 .: В кондитерской продаются пирожные 5 видов: бисквитные, корзиночки, буше, эклеры, трубочки. Сколькими способами можно купить 12 пирожных?

Решение:

.

Ответ: 4368 способов.

ГЛАВА 5. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ.

§ 1. Основные понятия

Определение 1.1. Граф G, по существу, есть набор из 2^х множеств любой природы – непустого множества вершин V и множества ребер E, причем каждому ребру соответствуют две концевые вершины, которые, вообще говоря, могут и совпадать.

Определение 1.2. Вершина, соединенная ровно с одним ребром, и само это ребро называются концевыми или висячими.

Определение 1.3. Различные ребра, соединяющие две вершины, называются кратными или параллельными.

Определение 1.4. Ребра с совпадающими концами называются петлями.

Определение 1.5. Граф G, имеющий n вершин, часто называют n – графом; если, кроме того, G содержит m ребер, то G – (n,m) граф.

Определение 1.6. Если e = uv некоторое ребро данного графа, то вершины u, v называются смежными.

Определение 1.7. Ребро e и вершина v инцидентны, если v – концевая вершина для e.

Определение 1.8. Ребра e и f называются смежными, если они имеют общую концевую вершину.

Определение 1.9. Две вершины, инцидентные одному и тому же ребру, называются соседними или смежными.

Определение 1.10. Степенью вершины v называется число ребер, инцидентных этой вершине, причем любая вершина учитывается дважды. Обозначение: deg_Gv или deg v.

Определение 1.11. Граф H называют подграфом графа G, если VHÍVG и EHÍEG.

Определение 1.12. Если VH=VG, то подграф H называется остовным подграфом.

Определение 1.13. Ориентированным графом G или орграфом G называется тройка (V, E, j), где j:E®V²=V´V, ставящего в соответствие каждому элементу eÎE упорядоченную пару элементов v₁v₂ÎV, называемых концами ребра e.

Определение 1.14. Если j(e)=v₁v₂ – упорядоченная пара, т.е. v₁v₂¹v₂v₁, то ребро e называется ориентированной дугой, исходящей из вершины v₁ и входящей в вершину v₂; v₁ называется началом дуги e, а v₂ – концом дуги. Если j(e)=v₁v₂- неупорядоченная пара, то ребро e называется неориентированным.

§ 2. Способы задания графов

1) Перечисление. Список ребер графа с указанием их концов и добавлением списка изолированных вершин.

2) Матрица соседства (смежности) вершин графа G.

Пусть G – любой n-граф. Упорядочим множество вершин графа VG={v_1, v_{2, ¼,} v_n}, т.е. занумеруем вершины графа числами от 1 до n.

Определим матрицу смежности B графа G. B – квадратная матрица размерности n, строки и столбцы которой соответствуют вершинам графа, причем неотрицательный элемент b_ij равен числу ребер, идущих из вершины v_i в вершину v_j (вообще говоря, b_ij¹b_ji, однако для неориентированных графов матрица соседства симметричная). Для несмежных вершин соответствующий элемент матрицы равен 0. При i=j каждую петлю учитываем дважды.

Пример 2.1. Определить матрицу смежности вершин для графа G.

1 2

Дата добавления: 2017-01-13