Полная версия

Главная arrow Математика, химия, физика arrow Дискретная математика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

Комбинаторные задачи на множествах

Комбинаторика как наука изучает количества комбинаций, подчиненных определенным условиям, которые можно составить из элементов заданного конечного множества. Природа элементов в данном случае не имеет значения [4, 6].

Мы разделяем задачи пересчета, перечисления и оптимизации.

Если нас интересует, сколько элементов, принадлежащих конечному множеству, обладает неким свойством (набором свойств), то это задача пересчета.

Если необходимо выделить все элементы множества, обладающие заданным свойством, то это задача перечисления.

Если на множестве задана некая целевая функция и нас интересуют элементы множества, на которых функция достигает экстремального значения, то это задача оптимизации.

При решении любого типа указанных задач используются следующие понятия [4].

Подмножество из т элементов на множестве X, состоящем из п элементов, называется (л, т)-выборкой, где т — объем этой выборки. Если (л, л?)-выборка рассматривается с учетом порядка элементов

в ней, то она называется (л, л7)-размещением и обозначается А™ от слова arrengment. Если т = л, то такое (л, л)-размещение называется собственно Р^-перестановкой.

Если порядок элементов в выборке (л, т) не имеет значения,

то она называется (л, т)-сочетанием и обозначается С™ от слова combination.

И перестановки, и сочетания могут быть с повторениями и без повторений.

Рассмотрим множество X = {а, Ь, с). Тогда все упорядоченные и неупорядоченные выборки объемом два выглядят следующим образом:

  • • размещения с повторениями {аа, ab, ас, ba, bb, be, са, cb, сс}, А: = 9;
  • • размещения без повторений {ab, ас, ba, be, са, cb}, А™ = 6;
  • • сочетания с повторениями {аа, ab, ас, bb, be, сс}, С™ = 6;
  • • сочетания без повторений {ab, ас, be), С™ = 3.

По определению перестановками называют комбинации, состоящие из одних и тех же л различных элементов и отличающиеся только порядком их расположения. Число всех возможных перестановок

Рп = п, (1.18)

где л! = 1 • 2 • 3 • • л.

Заметим, что по определению 0! = 1.

Перестановка л-элементного множества X — это взаимно однозначная функция/: X—» X. Если для простоты принять X- {1,..., л}, то перестановкой можно назвать упорядоченный набор из л различных чисел, лежащих в промежутке от 1 до л (далее будет рассматриваться именно этот случай).

Рассмотрим несколько задач на перестановки элементов множества.

Задача 1.14

В слове МИФИ меняют местами буквы. Чему равно количество всех возможных различных слов?

Решение.

Две буквы в слове совпадают, следовательно, число всех различных перестановок в 2! меньше возможных, т.е. равно

Задача 1.15

В слове НИЯУ МИФИ меняют местами буквы и пробел. Чему равно количество всех возможных различных слов?

Решение.

Три буквы в слове совпадают, следовательно, число всех различных перестановок в 3! меньше возможных, т.е. равно

= 60 480.

  • 9-8-7-6-5-4-3-21
  • 3!

Размещениями называют комбинации, составленные из п различных элементов по т элементов, лежащих в промежутке от 1 до п, которые отличаются либо составом элементов, либо их порядком. Другими словами, размещение — это множество с повторениями. Обозначим число его элементов через А™.

Число всех возможных размещений

А™ = п(п-)(п-2)...(п-т+ 1). (1.19)

Теорема 1.6. Число размещений

Число упорядоченных т-элементных подмножеств множества Хп, содержащего п элементов, равно

А™ =—-—. (1.20)

(п - т)

Сочетание из п элементов по т — это неупорядоченный набор (множество) из т различных чисел, принадлежащих множеству X. Таким образом, сочетаниями называют комбинации, составленные из п различных элементов по т элементов, которые отличаются хотя бы одним элементом. Так как сочетание является неупорядоченным набором, то каждому такому набору соответствует т размещений (т.е. упорядоченных наборов тех же элементов).

Теорема 1.7. Число сочетаний

Число неупорядоченных т-элементных подмножеств множества Xп, содержащего п элементов, равно

И *

?-т/7? _

т(п - т)

(1.21)

Можно привести некоторые свойства сочетаний:

і /~<т _ п-т.

А/ ''-'п — п

(1.22)

/-іт , /~<т+ _ ґіт+І.

(1.23)

о к _ /~ік

Э) ^п * .

(1.24)

Эти свойства следуют из самих определений и проверяются непосредственно подстановкой.

Рассмотрим несколько задач на размещение и сочетания.

Задача 1.16

Чему равно количество всех возможных различных слов, составленных из трех различных букв множества {А, В, С, Д ?}?

Решение.

Все буквы в слове не совпадают, следовательно, число всех различных размещений А35, равно

АІ = 5*4* = 60.

Задача 1.17

В слове ПИРАТ выбирают две буквы. Сколькими способами это можно сделать?

Решение.

Так как порядок букв в данном случае не имеет значения, то результат определяется по формуле для числа сочетаний:

  • 5!
  • 2!(5 - 2)!

Задача 1.18

Определить, сколько существует различных способов выбора (порядок не имеет значения) 3 томов из 5-томного собрания сочинений А.П. Чехова.

Решение.

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

  • 5!
  • 2!(5 — 2)!

Задача 1.19

В слове СКАНЕР выбирают по две буквы (все буквы различны) и составляют из них слова. Сколькими способами это можно сделать? Решение.

Используя формулу размещения, получаем

А} = 6-5 = 30.

Задача 1.20

В слове НИЯУ МИФИ выбирают по две буквы (все буквы различны) и составляют из них слова. Сколькими способами это можно сделать ?

Решение.

Используя формулу размещения, получаем

А] = 6-5 = 30.

Теорема 1.8. Количество перестановок с повторениями

Количество перестановок п элементов, из которых пх отностся к типу 1, п2 относится к типу 3, и т.д., вплоть до пг элементов типа г, равно

Рп = , "] ,• 0-25)

пхп2...пг

 
<<   СОДЕРЖАНИЕ   >>