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

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

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


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

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

Теоретические сведения

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

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

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

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

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

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

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

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

• размещения с повторениями {аа, ab, ас, ba, bb, be, са, cb, сс},

К = 9;

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

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

р =п'

  • (1.19)
  • 1 п

где п = 1 • 2 • 3 • ... • п.

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

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

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

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

Атп = п(п-1)(л-2)--.(л-/и + 1). (1.20)

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

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

  • (п - т)
  • (1.21)

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

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

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

С'”=---. (1.22)

т(п - т)

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

  • (1.23)
  • (1.24)
  • 1/ ^/7 ^/7 ’

С*т _1_

и/7 и/7 “ иА7+1 5

3) С - С* = С„* • С_-/. (1.25)

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

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

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

(1.26)

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

Задачи

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

Решение.

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

4 * 3 * 2 • 1 2!

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

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

= 60 480.

9 - 8 - 7 - 6 - 5 - 4 - 3 - 2 -1 3!

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

Решение.

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

= 5*4*3 = 60.

Задача 1.73. В слове НИЯУ выбирают две буквы. Сколькими способами это можно сделать?

Решение.

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

2!(4 - 2)!

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

Решение.

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

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

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

Решение.

Используя формулу размещения, получаем = 6 • 5 = 30.

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

Решение.

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

А = 6- 5 = 30.

Задача 1.77. В слове SHUT меняют местами буквы. Чему равно количество всех возможных различных слов?

Задача 1.78. В слове АТОМ меняют местами буквы. Чему равно количество всех возможных различных слов?

Задача 1.79. В слове КНИГИ меняют местами буквы. Чему равно количество всех возможных различных слов?

Задача 1.80. В слове КЛИКА меняют местами буквы. Чему равно количество всех возможных различных слов?

Задача 1.81. Чему равно количество различных способов выбора (порядок не имеет значения) 4 томов из 7-томного собрания сочинений А.П. Чехова?

Задача 1.82. Чему равно количество различных способов выбора (порядок не имеет значения) 3 томов из 7-томного собрания сочинений А. П. Чехова?

Задача 1.83. Чему равно количество различных способов выбора (порядок не имеет значения) 5 томов из 7-томного собрания сочинений А.П. Чехова?

Задача 1.84. Чему равно количество различных способов выбора (порядок не имеет значения) 2 томов из 7-томного собрания сочинений А.П. Чехова?

Задача 1.85. Чему равно количество различных трехбуквенных комбинаций, которые можно составить из букв слова ЦВЕТОК (все буквы в комбинации различны)?

Задача 1.86. Чему равно количество различных двухбуквенных комбинаций, которые можно составить из букв слова КОМАР (все буквы в комбинации различны)?

Задача 1.87. Чему равно количество различных двухбуквенных комбинаций, которые можно составить из букв слова ЦВЕТОК (все буквы в комбинации различны)?

Задача 1.88. Чему равно количество различных трехбуквенных комбинаций, которые можно составить из букв слова КОМАР (все буквы в комбинации различны)?

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