Утверждение 2.3 Число всех перестановок множества M (|M| = n) равно n!

Действительно, на первое место в n-ке можно поставить любой из n элементов множества, на второе место – любой из (n–1) оставшихся, и т. д. Для последнего места остается единственный элемент. Поэтому получаем:        
Pn = n⋅(n–1)⋅(n–2)⋅…⋅2⋅1 = n!

Сколькими способами можно расставить на полке 6 томов книг? Это можно осуществить  P6 = 6! = 720 способами.
        Понятие выборки

Пусть дано множество M = {a1, a2, a3, ..., an}, m ≤ n. Набор, состоящий из m элементов множества М, называется выборкой объема m из n элементов.

Выборки классифицируются следующим образом:

По критерию повторяемости элементов:        С возвращением объема (с повторениями) и без возвращения объема (без повторений). По критерию упорядоченности:        

Упорядоченные (размещения)  и неупорядоченные (сочетания).

В ящике n≤10 нумерованных шаров, один достают, записывают номер и бросают обратно. Так делают три раза. Сколько разных трехзначных чисел может получиться? Для подсчета нужны размещения с повторениями.
        Размещения и сочетания без повторений

Размещениями из n элементов по m называются упорядоченные выборки без повторений элементов множества, которые отличаются одна от другой либо составом элементов, либо порядком их расположения. Размещение можно рассматривать как разнозначную функцию f:{1,2,…,m}→M, для которой f(j)=aij.

НЕ нашли? Не то? Что вы ищете?

Тогда числу размещений из n элементов по m соответствует число инъективных функций или число всех возможных способов разместить n предметов по m позициям («ящикам»), не более чем по одному в «ящик». Это число будем обозначать =A(n, m) (иногда обозначают P(n, m)).

Пусть дано множество M={1,2,3,4,5}. Тогда  размещениями из 5 элементов по 2 будут, в частности, выборки (1,2), (2,1), (2,4), (4,2)  и т. п. = n⋅(n–1)⋅(n–2)⋅…⋅(n–m+1).        

Доказательство:         Размещение m элементов из n имеющихся будем рассматривать как заполнение некоторых m позиций элементами множества M. Для первой позиции существует  n различных способов. После того, как первая позиция заполнена, элемент для второй позиции можно выбрать (n–1) способами (комбинаторный принцип умножения). Если процесс продолжить, то после заполнения позиций с 1-й по (m–1)-ю останется (n–m+1) способ для последней, m-й позиции. Перемножив эти числа, получим формулу для .<

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

Пусть дано множество M={1,2,3,4,5}. Тогда сочетаниями из 5 элементов по 2 будут выборки (1,2), (2,4), (5,2)  и т. п. (Здесь (2,4)~(4,2)…)

Число сочетаний без повторений будем обозначать или C(n, m).

.

Формула для числа размещений из n элементов по m была получена ранее. Если объединить размещения, отличающиеся только порядком элементов и совпадающие по составу, в классы эквивалентности, то получим, что мощность каждого из таких классов m! Тогда число сочетаний будет определяться как C(n, m)= .

На тренировках занимаются 8 баскетболистов. Сколько разных пятерок может быть образовано тренером? Т. к. при образовании пятерки важен только ее состав, то достаточно определить пятерок.
        Размещения и сочетания с повторениями

Размещениями с повторениями (или упорядоченными выборками с возвращениями) из n элементов по k  называются упорядоченные наборы из k элементов множества M, в которых элементы множества могут повторяться.

Пусть дано множество M={1,2,3,4,5}. Тогда  размещениями с повторениями из 5 элементов по 2 будут (1,1), (1,2), (2,1), (2,2), …,(5,1)  и т. п. – любые упорядоченные пары из 2 элементов множества М.

Количество всех размещений с повторениями обозначим =В(n, k). Поскольку в таком наборе из k элементов на каждом из k мест может стоять любой из n элементов исходного множества, число размещений с повторениями равно  n⋅n⋅…⋅n = nk. ⇒ .                                                        (2.1)

а) Сколько различных трехзначных чисел можно составить из цифр 1, 2, 3, 4, 5? б) А при условии, что ни одна цифра не повторяется? Составить разные числа можно: способами (размещения с повторениями). Если ни одна цифра не должна повторяться, то таких способов будет (размещения без повторений).

В отличие от выборок без повторений, количество выбираемых объектов может быть больше, чем количество типов, т. е. может быть  k ≥ n. Если вернуться к примеру 2.12 (а), то можно рассматривать и 10-разрядные числа.

(о мощности множества  P(M) )

Для конечного множества M  |2M| = 2|M|.

Доказательство:

Пусть конечное множество M состоит из n элементов, M = {x1, …, xn}. Сопоставим каждому его подмножеству двоичный вектор длины n. Если xi входит в подмножество, то на  i-м месте в этом векторе будет стоять 1, иначе – 0. Поскольку каждая компонента вектора может принимать только значения 0 или 1, а всего таких компонент n, то число различных векторов составит 2n. <

Следствие:        

Можно сгенерировать все подмножества конечного множества M, перечислив некоторым способом все наборы из нулей и единиц длины n.

Можно выполнять такую генерацию различными способами (например, все наборы с одной «1», все с двумя «1», …). Это можно сделать наиболее эффективно, используя т. н. бинарный код Грея. Алгоритм построения бинарного кода Грея позволяет генерировать последовательность всех подмножеств  n-элементного множества таким образом, что каждое последующее подмножество получается из предыдущего добавлением или удалением единственного элемента. Подробно этот алгоритм рассматривается при выполнении лабораторной работы.

Определим отношение эквивалентности на множестве размещений с повторениями из n элементов по k: (a1,a2,…,ak) ~ (b1,b2,…,bk) ⇔ ∀c∈M  число элементов  ai = c  совпадает с числом элементов  bj = c. 

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

В примере с множеством M={1,2,3,4,5} сочетания с повторениями из 5 элементов по 2 будут отличаться от размещений тем, что одинаковые по составу наборы будут независимо от порядка элементов в них считаться эквивалентными: (1,1), (1,2)~(2,1), (2,2), (5,2)  и т. п.

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

Число всех сочетаний с повторениями обозначается =Ĉ(n, k) и вычисляется по формуле: Ĉ(n, k)=                        (2.2)

Пусть в кондитерской продается 10 различных видов пирожных. (n=10 – число типов). Сколькими способами можно купить 12 пирожных? (k=12). Ĉ(10,12)=C(10+12–1,12)=C(21,12)=21!/(12! (10–1)!)= 21!/(12! 9!).
        Контрольные вопросы
Что такое подстановка? Всегда ли существует обратная подстановка? Какая перестановка элементов множества {1,2,3,4} задана функцией подстановки ? Является ли эта подстановка циклом? Что такое транспозиция? В каком алгоритме она используется? Как называется упорядоченная выборка без возвращения объема и по какой формуле вычисляется число различных таких выборок? Сколько различных двузначных чисел можно получить, используя множество {1,2,3,4,5}? Как изменится результат, если цифры в числе не повторяются? Какая выборка (и формула) используется в каждом случае? Сколько двузначных чисел с различной суммой цифр можно получить, используя множество {1,2,3,4,5}? Цифры в числе должны быть разными. В чем отличие от предыдущей задачи? Сочетания или размещения нужно использовать? В чем отличие сочетаний с повторениями от остальных конфигураций? Пусть в киоске есть три вида открыток. Сколькими способами можно купить 6 открыток? А три открытки? Какая конфигурация используется? Биномиальные коэффициенты

Число сочетаний C(n, k)= – число различных k-элементных подмножеств n-элементного множества – встречается в формулах решения многих комбинаторных задач. Например, для определения числа подмножеств n-элементного множества, удовлетворяющих некоторому условию, задача разбивается на составные части: рассматриваются отдельно 1-элементные подмножества, 2-элементные и т. д., затем результаты складываются.

Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5