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

Основные понятия теории множеств и 1.3. Основные структуры.

Множество– это набор, совокупность, собрание каких-либо объектов, называемых его элементами, обладающими общим для всех них характеристическим свойством.

Обозначения: М – множество (принято обозначать заглавными латинскими буквами),

x M – элемент x принадлежит множеству М,

М = {x₁, x₂, x₃, … , x_n} – множество М состоит из элементов x_i, где i =1…n,

M = {Ø} – множество М – пустое, т.е. не содержит элементов,

А В – множество А является подмножеством множества В, т.е. все элементы множества А являются одновременно элементами множества В.

А = В – множество А равно множеству В, т.е. множество А является подмножеством множества В, а множество В является подмножеством множества А.

Способы задания множеств

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

2. Аналитический способ предполагает описание характеристического свойства множества. Пусть Р(x) – некоторое предложение, зависящее от x. Тогда запись А = {x | P(x)}, говорит о том, что множество А состоит из всех элементов x, обращающих в истинное утверждение P(x). Например, А = {x | x N} – множество, всех натуральных чисел или В = {x | x - это студент} – множество всех студентов.

3. Графический. Множество может задаваться графически. Например, А и В – множества точек круга и отрезка, соответственно:

Операции над множествами

Суммой или объединением нескольких множеств называется множество всех элементов, которые являются элементами хотя бы одного из исходных множеств. Обозначается А В.

Пример. Если А = {1,2,4,7,8} и В = {1,3,5,6,9}, тогда А В = {1,2,3,4,5,6,7,8,9}.

Пересечениеммножеств называется множество, состоящее из общих элементов исходных множеств. Обозначается А В.

Пример. Если А = {1,2,4,7,8} и В = {1,2,5,6,9}, тогда А В = {1,2}.

Разностью двух множеств А и В называется множество, состоящее из элементов множества А, не принадлежащих множеству В. Обозначается А\В.

Пример. Если А = {1,2,4,7,8} и В = {1,3,5,6,9}, тогда А\В = {2,4,7,8}.

Разность между множеством В и его частью - множеством А, называется дополнением множества А до множества В. Обозначается .

Пример. Если А = {1,2,4} и В = {1,2,4,6,8,10}, тогда = {6,8,10}.

Разбиением множества А называется такая расчлененная система U непустых подмножеств множества А, что каждый элемент А является элементом некоторого (единственного) множества системы U.

Пример. U = {{1},{2, 4},{7},{8}} – разбиение множества А = {1,2,4,7,8}.

Перестановки.

Пусть А — некоторое конечное множество, состоящее из п различных элементов;

A — {a_l; а₂; а₃;...; а_п}. (I)

Будем образовывать из элементов множества А упорядоченные множества. В качестве первого упорядоченного множества возьмем множество, в котором элементы расположены в порядке возрастания их номеров:

{a_l; а₂; а₃;...; а_п}

Второе упорядоченное множество можно образовать, поменяв местами элементы а₁ и а₂, а все остальные элементы первого множества оставив на своих местах:

{ а₂; a_l; а₃;...; а_п}

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

Всевозможные конечные упорядоченные множества, содержащие п различных элементов, которые можно получить из некоторого не­упорядоченного множества, состоящего из п различных элементов, называются перестановками из n элементов.

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

Число перестановок из п элементов (которое обычно обозначается Р_п) равно произведению п последовательных натуральных чисел, начиная с единицы. Это произведение имеет специальное обозна­чение n!(читается: n факториал):

Р_п= 1*2*3*...* (n— 1)*n = n!

Для пустого множества принимается соглашение: пустое мно­жество можно упорядочить только одним способом; поэтому считается, что

Ø! = 1.

Если в заданной перестановке поменять местами какие-либо два элемента, а все остальные элементы оставить на своих местах, то полу­чится новая перестановка.

Такое преобразование перестановки называется транспозицией.

Все n!перестановок из n элементов можно расположить в таком порядке, что каждая следующая перестановка будет излучаться из предыдущей одной транспозицией, причем в качестве исходной пере­становки можно выбрать любую из n! перестановок. В частности, от любой перестановки из n элементов можно перейти к любой другой перестановке из тех же элементов при помощи нескольких транспо­зиций.

Перестановки с повторениями. Пусть А — некоторая со­вокупность, состоящая из п элементов: А= {a_l; а₂; а₃;...; а_п}

т различных типов (m n), причем элементы одного типа, неразли­чимы между собой, И пусть k₁ элементов принадлежат первому типу, k₂ элементов принадлежат второму типу, k ₃ — третьему, k_m— m-му типу, причем k₁+k₂+k₃+…+k_m= n.

Например, если A = {1, 1, 2, 3, 1, 3}, то, считая элементами первого типа единицы, элементами второго типа двойки, а элементами третьего типа тройки, имеем

k₁ = 3, k₂ = 1, k₃=2.

Различные конечные совокупности, содержащие п элементов, из которых k₁ принадлежат первому типу, k₂— второму типу . . ., k_m— m-му, типу, называются перестановками с повторениями (кортежами), имеющими состав (или спецификацию) (k_1,k_2,k_3,…,k_m).

Число таких различных перестановок с повторениями обычно обо­значается С_п (k_1,k_2,k_3,…,k_m)

и вычисляется по формуле

С_п (k_1,k_2,k_3,…,k_m)=

Размещения.

Пусть дано некоторое конечное множество А, состоящее из п различных элементов. Выберем некоторым образом из этих п элементов т различных элементов и будем составлять из этих m элементов различные упорядоченные множества.

Конечные упорядоченные подмножества, содержащие по т эле­ментов, выбранных из n элементов основного множества, называются размещениями из п элеметов по т элементов. Число всех возможных размещений из п элементов по т обозначается

Нетрудно убедиться, что = n,

т. е. один элемент из п можно выбрать п способами, а из одного эле­мента можно образовать единственное упорядоченное множество.

Последнее равенство можно записать с использованием символа фак­ториала

;

При т = 0 получаем = 1, т. е. из любого множества единственным способом можно извлечь пустое множество, которое, по определению, можно упорядочить единственным способом.

Сочетания.

Конечные неупорядоченные множества, содержа­щие m различных элементов, выбранных из п элементов заданного мно­жества, называются сочетаниями из п элементов по т. Число сочетаний

из п элементов по т элементов обозначается .

Число сочетаний из п элементов по т равно

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

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

Например, из трех различных элементов a₁, a₂, а₃ можно составить следующие сочетания по два с повторениями:

{ a₁; a₁}, {a₁; a₂}, { a₁; а₃}, { a₂; a₂}, { a₂; а₃} { а₃; а₃}.

Число различных сочетаний из m элементов по n с повторениями обозначается и вычисляется по формуле =

Теория вероятности.

Не нашли, что искали? Воспользуйтесь поиском по сайту: