1.4 размещения. упорядоченные множества

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

В комбинаторике конечные упорядоченные множества назы­ваются размещениями.

Упорядоченные множества будем записывать в крутых скоб­ках, располагая его элементы в заданном порядке (х1 ;х2 ,….,х n)  

Например, упорядочивая трехэлементное множество {а,b, с}. мы получим 6 упорядоченных множеств:

(a,b, с); (а,с, b); (b, а. с);(b, с, а); (с, b, а); (с, а,b).

Размещения из п элементов по т (т<п) — это такие соединения из n элементов по m, которые отличаются одно от другого либо порядком элемен­тов, либо, но крайней мере. одним элементом.

Число размещений из n элементов но m обозначают Аmn. Пусть исходное множе­ство состоит из букв (а, b, с). Ставится задача: посчитать количе­ство размещений из трех элементов по два: А23.

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

Для наглядности составим таблицу, где и запишем все возмож­ные подмножества.

                                           а                          b                             c

           а                          (a; a)                   (a; b)                        (a; c)

           b                          (b; a)                   (b; b)                        (b; c)

           c                          (c; a)                    (c; b)                        (c; c)  

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

Число возможных размещений из n различных элементов по т находятся по формуле:

                                          Āmn=nm  (*)

В дальнейшем размещения без повторений мы будем называть одним словом - «размещения».

Размещение без повторений - каждый элемент, входящий в комбинацию, представлен единственным экземпляром (исключая элементы диагонали таблицы)

Будем составлять упорядоченные двухэлементные подмноже­ства из данных трех элементов а, b, с:

(а,b); (а, с); (b,а); (b,с); (с, а); (с, b).

На первое место можно поставить любой из трех элементов, это можно сделать тремя способами, на второе место — любой из оставшихся элементов, то есть двумя способами, всего получим 3*2 соединений, т. е.

А23=3*3=6 Очевидно, что А1n =п. Действительно, один элемент из А1n  ,можно выбрать n способами, а из этого элемента получается одно упорядоченное множество.

Докажем, что при 1 ≤m< п имеет место соотношение:

Аm+1n=(n-m) Аmn    (**)

Имея п элементов, будем распределять их по m+1 местам. Раз­мещение будем производить следующим образом: сначала выбе­рем из данных n элементов какие-либо т элементов и разместим их по первым m местам. Это можно сделать Аmn способами. На остав­шееся (m+1)-е место можно поставить любой из оставшихся п - т элементов, что можно сделать п - т способами. Итак, при каждом из Аmn заполненных первых мест получим n - m возможных запол­нений (т+1)-го места. Следовательно, всего их будет (п - т) Аmn, что и требовалось доказать.

Пользуясь формулой (*), получаем  окончательно:

Аmn  =n!/(n-m)!   (***)

При m=0 по формуле (**) получаем: А0n =1.

Это верно: существует только одно пустое множество, оно яв­ляется подмножеством любого множества.

Заметим еще, что 0!=1; 1! =1;  и Аnn =Р„ =п! Приведем таблицу значений Аmn при n≤5.

Пример 1. Учащиеся 11-го класса изучают 9 учебных предметов. В расписании учебных занятий на один день можно по­ставить 4 различных предмета. Сколько существует различных способов составления расписания на один день?

Решение. Имеем 9-элементное множество, элементы кото­рого учебные предметы. При составлении расписания мы будем выбирать 4-элементное подмножество и устанавливать в нем порядок. Число таких способов равно числу размещений из де­вяти по четыре, то есть А49

А49 = 9*8*7*6=3024;

Пример 2. В чемпионате участвуют 12 команд. Сколькими различными способами могут быть распределены три различные медали?

Решение. А312 =12 •11•10=1320.

Пример 3. Решить уравнение А5n = 30 • А4n-2

Решение. Используя формулу (***), перепишите уравнение в виде

n • (n -1) •  (n - 2) • (n - 3) • (n - 4) =  30 • (n - 2) •  (n - 3) • (n - 4) • (n - 5). Учитывая, что n > 6, разделим обе его части на (n - 2) • (n - 3) • (n - 4); далее, имеем .(n(n-1)=30• (n -5))             (n2 -31•  n+150= 0)<=> (n1 =6,n2 =25).

Контрольные вопросы:

Что такое множество?2. Что изучает комбинаторика?  3.  Правила суммы и произведения? 4. Что такое размещение? 5. Как вычислить размещение m элементов из n? 6. Что такое перестановка? 7. Как вычислить число перестановок n предметов?