Дискретно-непрерывная математика (стр. 33 )

5.4.2. Упорядоченные подмножества данного множества

(размещения).

Рассмотрим теперь упорядоченные подмножества данного множества А. Само множество А считаем неупорядоченным, поэтому каждое его подмножество может быть упорядочено каким-либо возможным способом. Число всех k-элементных подмножеств множества А равно Ckп. Каждое такое подмножество можно упорядочить k! способами. Таким образом получим все упорядоченные k-элементные подмножества множества А. Следовательно, их число будет k!• Ckп.

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

Аkп = k!• Ckп = = п (п - 1) ...(n-k+1).

Упорядоченные k-элементные подмножества множества из п элементов называются размещениями из п элементов по k. Различные размещения из п по k отличаются количеством элементов либо их порядком.

Следовательно, число различных размещений из п по k равно

Аkп = п(п-1) ...(n-k + 1).

5.5. Перестановки с повторениями

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

A=B1 B2…Bm

так, чтобы N(B1) =k1 , N(B2)=k2, ...., N(Bm) = km, где k1, k2, .,., kт — данные числа (ki≥0, k1+...+km = n)? Множества B1, В2, ..., Вт не должны иметь общих элементов.

Все описанные выше разбиения множества А на т групп В1, В2, ..., Вт можно получить так: возьмем произвольное k1-элементное подмножество B1 множества А (это можно сделать способами); среди п — k1 оставшихся элементов возьмем k2-элементное подмножество В2 (это можно сделать способами) и т. д. Общее число способов выбора различных множеств В1,..., Вт по правилу умножения равно

(напомним, что 0! = 1).

Итак, мы доказали следующую теорему.

Теорема. Пусть k1, k2, ..., km — целые неотрицательные числа, причем k1+k2+...+km=п. Число способов, которыми можно представить множество А из п элементов в виде суммы m множеств В1, В2, ..., Вт, число элементов которых составляет соответственно k1,k2, ..., km, равно

Cn(k1, ..., km)=

Числа Cn(k1, ..., km) называются полиномиальными коэффициентами. Они имеют еще одну очень важную комбинаторную интерпретацию.

Пусть имеется п букв: k1 — букв а1, k2 — букв а2, km — букв am

(k1 + k2 + ... + km = п). Определим, сколько различных слов можно сложить из этих букв. Перенумеруем места, на которых стоят буквы, числами 1, 2, ..., п. Каждое слово определяется множествами В1 (номера мест, где стоит буква а1), В2 (номера мест, где стоит буква а2), ..., Вm (номера мест, где стоит буква ат). Следовательно, число различных слов равно числу способов, которыми можно представить множество А = {1, 2, .... п} в виде суммы множеств В1, В2, ..., Вт, т. е.

Cn(k1, ..., km)=

Пример. Число различных слов, которое получим, переставляя буквы слова «математика», равно

Утверждение, установленное выше, можно сформулировать в виде следующей теоремы.

Теорема. Число различных перестановок, которые можно составить из п элементов, среди которых имеется k1 элементов первого типа, k2 элементов второго типа, ..., km элементов m-го типа, равно

Cn(k1, ..., km)=

В связи с важностью теоремы приведем еще одно доказательство. Рассмотрим одну перестановку и заменим в ней все одинаковые элементы разными. Тогда число различных перестановок, которые можно составить из рассматриваемой нами перестановки, равно k1!·k2! ... km!. Проделав это для каждой перестановки, получим п! перестановок. Следовательно,

Cn(k1, ..., km)·k1! ... km!=n!,

что и доказывает утверждение теоремы.

5.6. Взаимно однозначное соответствие. Соединения с повторениями

5.6.1. Взаимно однозначное соответствие.

Предположим, что задано 2 множества А и В. Будем считать, что между этими множествами установлено соответствие, если каждому элементу а из А соответствует некоторый элемент b из B и, наоборот, для каждого элемента b из В существует такой элемент а из A, что b соответствует а. Это соответствие будет взаимно однозначным, если каждому элементу из А соответствует только один элемент из B и различным элементам множества А соответствуют различные элементы множества В.

Пример 1. А — множество студентов группы, В-множество столов. Каждому студенту соответствует стол за которым он сидит (это не взаимно однозначное соответствие).

Пример 2. А — множество всех городских жителей Украины, В — множество всех городов Украины. Каждому элементу А соответствует город, в котором он живет (это также не взаимно однозначное соответствие).

Примером взаимно однозначного соответствия может быть соответствие между элементами упорядоченного множества A из n элементов и числами 1, 2.....п; каждому элементу соответствует его номер.

Определение. Множества, для которых существует взаимно однозначное соответствие, называются эквивалентными.

Теорема. Для того чтобы два множеств были эквивалентными, необходимо и достаточно, чтобы они имели одинаковое число элементов.

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

Предположим теперь, что А имеет п элементов и существует взаимно однозначное соответствие между А и В. Упорядочим множество А: пусть элементами А будут а1, а2, ..., ап. Обозначим через bk тот элемент В, который соответствует аk. Поскольку каждому элементу из А соответствует элемент из В, различным элементам из А соответствуют различные элементы из В, и каждый элемент из В соответствует некоторому элементу из А, то В состоит из элементов b1, b2…,bn, следовательно, B имеет п элементов.

Следствие. Если два множества эквивалентны, то они имеют одинаковое число элементов.

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

Пример 3. Рассмотрим множество А последовательностей х1, х2, …, хп из п чисел, где числа х, принимают только значение 0 и 1 и среди них ровно k единиц. Чтобы вычислить число элементов нашего множества, обращаем внимание, что оно эквивалентно множеству В всех k-элементных подмножеств множества {1, 2, .... п}: подмножество чисел {i1, ..., ik} соответствует той последовательности х1, х2, ..., хп, у которой =1, =1, ..., = 1. Следовательно,

N (A) = Ckn.

Пример 4. Найти число размещений п одинаковых предметов в m урнах.

Перенумеруем урны. Поставим в соответствие каждому размещению предметов в урнах последовательность из нулей и единиц следующим образом: сначала последовательность имеет группу нулей, количество которых равно числу предметов в первой урне, потом записываем единицу и дальше пишем столько нулей, сколько предметов во второй урне, снова единицу, потом столько нулей, сколько предметов в третьей урне, и т. д. Заканчивается последовательность группой нулей, которая является числом предметов в последней урне. Следовательность, последовательность имеет п нулей и m — 1 единиц, всего п + m—1 чисел. Например, при п=10, т=4 последовательность 1011000000000 соответствует размещению: первая урна пустая, вторая урна имеет 1 предмет, третья урна пустая, четвертая урна имеет 9 предметов; а последовательность 0010010000001 соответствует размещению: первая урна имеет 2 предмета, вторая — 2 предмета, третья — 6 предметов, четвертая — пустая.

Используя предыдущий пример, получаем, что искомое число размещений будет С т-1п+ т-1.

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

Сочетаниями из m элементов по п элементов с повторениями называются группы, которые содержат п элементов, причем каждый элемент принадлежит к одному з m типов.