Комбинаторика
  • Регистрация
1 1 1 1 1 1 1 1 1 1 Рейтинг 5.00 (1 Голос)

Пусть мы имеем конечное множество Х={,,…,}, тогда набор элементов ,…,Называется Выборкой объема r из n элементов или, иначе, (n, r)-выборкой. Выборка называется Упорядоченной, если порядок следования элементов в ней фиксирован, и две выборки, различающиеся лишь порядком следования элементов, считаются различными.

Число возможных различных упорядоченных (n, r)-выборок с такими элементами, что ¹, если и j¹k равно числу различных r-векторов <,…,>, которые могут быть построены на Х={,…,}. Это число называется числом Размещений из n элементов по r и обозначается . Докажем, что

, (2.1)

Где и называется k-факториал.

Очевидно, что для выбора у нас есть n возможностей. После выбора элемента и удаления его из Х, для выбора остается (n-1) возможность и т. д. Тогда при выборе элемента имеется [n-(r-1)] возможностей и в итоге имеем

.

Если рассмотреть множество всех различных n-векторов <xi1, xi2,…,xin>, которые можно построить на Х, то каждая такая выборка называется Перестановкой, поскольку различаются они только расположением элементов. Перестановки обозначаются Рn. Докажем, что

. (2.2)

Для этого выберем первый элемент ÎХ и рассмотрим все перестановки, в которых имеет номер 1. Число таких перестановок с очевидностью равно Рn-1. Обозначим через М множество всех перестановок множества Х, а через Мi – множество всех перестановок, в которых имеет номер i. Тогда

М=М1ÈМ2È…ÈМn,

Где , если i¹j, поскольку элементы множеств Мi и Мj различаются положением элемента .

Используя предыдущий вывод, что |Мi|=Рn-1, , можно записать

.

Используя (2.1) для размещений , соответствующих упорядоченным выборкам (n, n), можно записать:

С другой стороны, эти выборки соответствуют n-перестановкам, и из (2.2) следует, что

Откуда мы должны положить 0!=1.

Рассмотрим теперь неупорядоченные выборки {,…,} r-элементов из Х, которые считаются различными, если они отличаются хоть одним элементом. Таким образом, каждая такая (n, r)-выборка есть подмножество мощности r множества Х. Задача состоит в подсчете числа разных r-элементных подмножеств из n-элементного множества Х. Каждое такое подмножество называется Сочетанием из n-элементов по r, а их общее число обозначается . Покажем, что

. (2.3)

Для этого можем заметить, что каждой выборке (сочетанию) {,…,} соответствует r! упорядоченных выборок (размещений) <,…,> за счет перестановок r элементов, то есть

,

Откуда следует после применения (2.1), что

.

Задача 2.2. Сколькими способами можно упорядочить множество {1,2,…,2n-1, 2n} так, чтобы каждое четное число имело четный номер?

Решение. Задача состоит в расположении нечетных чисел (их всего n) по нечетным, а четных (их тоже n) - по четным местам.

Очевидно, что первая подзадача имеет решение n!. Но точно так для каждой комбинации нечетных чисел имеется n! перестановок четных чисел по четным местам. В итоге общее число комбинаций равно n! *n!= (n!)2.

Задача 2.3. Сколько существует способов упорядочить множество {1,2,…,n} так, чтобы числа 1,2,3 стояли рядом и в порядке возрастания?

Решение. Число 1 (а 2 и 3 должны стоять рядом справа) можно записать на 1-е, 2-е,…,(n-2)-е место, то есть всего (n-2) возможности. В каждом случае оставшиеся (n-3) чисел могут быть расставлены (n-3)! способами. Таким образом, число интересующих нас комбинаций равно (n-2)(n-3)!.

Задача 2.4. При повороте листа бумаги с цифрами на 180°цифры 0,1,8 не изменяются, 6 и 9 переходят друг в друга, а остальные теряют смысл. Сколько существует семизначных чисел, не содержащих одинаковых цифр и не изменяющихся при повороте листа?

Решение. Очевидно, что 4-е место (центральное) в числе могут занимать 0,1 или 8. Это составляет 3 возможности. Для каждой из этих возможностей для тройки чисел справа (или слева) от центральной цифры нужно из четырех оставшихся цифр составить комбинацию из трех цифр. Всего таких комбинаций , а следовательно, общее число возможных искомых семизначных чисел равно N=3*24=72.

Задача 2.5. На плоскости заданы n точек, все попарно соединенные линиями, называемые ребрами. Сколько всего ребер?

Решение. Пусть каждой точке соответствует элемент множества X={,…,}. Тогда каждое ребро определяет подмножество X, состоящее из двух элементов, и задача состоит в отыскании числа всех 2-х элементных подмножеств в X, которое равно числу сочетаний:

 

Рис.2.1. Схема одного из кратчайших путей на сетке

Задача 2.6. На прямоугольной сетке m´n (рис. 2.1) найти число различных кратчайших путей, соединяющих точки (0,0) и (m, n).

Решение. Любой кратчайший путь из (0,0) в (m, n) состоит из m+n отрезков, среди которых m горизонтальных и n вертикальных. Разные пути различаются лишь порядком чередования горизонтальных и вертикальных отрезков. Поэтому их число равно числу способов выбора мест n вертикальных отрезков на общем числе шагов m+n, т. е. числу сочетаний Очевидно, этот же результат будет получен, если размещать m горизонтальных отрезков на n+m шагах, а, следовательно,

. (2.4)

Применяя, использованный в задаче 2.5 так называемый Метод траекторий, можно доказать тождество

. (2.5)

Действительно, из рисунка 2.1 следует, что общее число кратчайших путей из в равно сумме путей, ведущих из в точку А1 с координатами в точку A2 с координатами , т. е.:

.

Переобозначив m+n=r, получим формулу (2.5):

.

Точно так же можно доказать, что

. (2.6)

Для этого на рисунке 2.1 положим, что m=n и обратим внимание, что в соответствии с (2.4) общее число кратчайших путей из (0,0) в (n, n) равно С другой стороны, каждый из этих путей проходит через одну и только одну из точек Ak (k, n-k), лежащих на диагонали, соединяющей точки (0,n) и (n,0). Тогда число различных путей из (0,0) в (n, n), проходящих через Ak (k, n-k), равно произведению числа путей, ведущих в Ak и из Ak в (n, n), т. е.

. (2.7)

Суммируя по всем точкам k=0,1,…,n, получим выражение, стоящее справа в (2.6).

Числа называются также Биноминальными коэффициентами, что связано с формулой бинома Ньютона:

(2.8)

Докажем эту формулу, используя представление:

.

Перемножая последовательно (a+b) n раз, получим сумму 2n слагаемых вида где равно a или b. Разобьем слагаемые на n+1 группу B0,B1,B2,…,Bn, отнеся к Bk все те произведения, в которых B Встречается множителем k раз, а A - (n-k) раз. Число произведений в Bk равно числу способов выбора k мест из возможных n мест, т. е. равно , а каждое слагаемое в равно An-kbk.. Поэтому

.

Схемы без повторений - 5.0 out of 5 based on 1 vote

Добавить комментарий


Защитный код
Обновить