Соединения с повторениями




Лабораторная работа №5. Тема: «Основные понятия комбинаторики»

1 Теоретические сведения

Правила суммы и произведения

 

Важную роль при решении многих комбинаторных задач играют 2 правила: правило суммы и произведения.

Сформулируем эти правила с точки зрения теории множеств и комбинаторики.

 

Правила суммы

 

- Теоретико – множественная формулировка

 

Пусть A – множество из m элементов; B – множество из n элемнтов. AÇB=Æ. Тогда, объединение множеств: AÈB содержит m+n элементов.

В общем случае: Пусть |M1|=m1, |M2|=m2, …, |Mk| = mk и Mi Ç Mj=Æ "i,j=1.. k, i¹j. Тогда, |M| = |M1È M2È…ÈMk| = m1+ m2+…+ mk.

 

- Комбинаторная формулировка

 

Если объект a может быть выбран m способами, а объект b – n другими способами, то выбор "a или b" может быть осуществлен m+n способами.

Выбор a и b – взаимоисключающий, выбор a исключает выбор b; выбор a не совпадает с каким-либо способом выбора b.

 

В общем случае:

Если объект a1 может быть выбран m1 способами; … ak – mk способами. Выбор "a1 или a2…или ak " может быть осуществлен m1 +m2 +…+mk способами.

Например: Из Киева в Донецк в течении суток отправляется 3 поезда, 1 самолет и 2 автобуса. Сколько существует способов выехать из Киева в Донецк?

Решение: По правилу суммы имеем N= 3+1+2 = 6 способов.

 

Правило произведения

 

- Теоретико – множественная формулировка

 

Если A и B – конечные множества и |A|=m, |B|=n, то мощность множества A´B равна m´n.

 

В общем случае; если |M1|=m1, |M2|=m2, …, |Mk|=mk, то |M1´M2´…´Mk|= =m1´m2´…´mk.

 

 

- Комбинаторная формулировка

 

Если объект a может быть выбран m способами, и после этого объект b может быть выбран n способами, то выбор пары (a,b) может осуществляться m´n способами (выбор a и b независимы).

 

В общем случае:

Пусть объект a1 может быть выбран m1 способом; объект a2 – m2 способами; … ak – mk способами, причем выбор a1 не влияет на число способов выбора a2 …ak, выбор a2 на число способов выбора a3 …ak, … Тогда, выбор упорядоченного множества объектов (a1, a2 …ak) – в указанном порядке можно осуществить m1´ m2´ ´mk способами.

 

Например: Сколько различных танцующих пар можно составить из 3-х девушек и 2-х юношей?

Решение: По правилу произведения имеем N= 3´2=6 пар.

 

Сложный выбор объектов

 

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

 

Например: Имеется три различных флага. На флагштоке поднимается сигнал, состоящий не менее, чем из 2-х флагов. Сколько различных сигналов можно поднять на флагштоке, если порядок сигналов учитывается?

 

Решение: Сигнал может состоять либо из 2-х сигналов, либо из 3-х. Одновременное выполнение 2-х действий невозможно.

 

N=N2+N3 (правило суммы)

N2=3´2=6 (правило произведения)

N3=3´2´1=6 (правило произведения)

N=12

 

 

Соединения без повторений

 

Соединения – простые комбинаторные объекты, к которым относятся перестановки, сочетания и размещения.

 

 

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

 

Перестановка из n элементов – упорядоченная последовательность элементов n- элементного множества (кортеж).

Различные перестановки – отличаются порядком элементов в них.

 

Например:

Пусть A={1,2,3}

Перестановки: 123, 132, 213, 231, 312, 321.

 

Число перестановок из n различных объектов равно: Pn=n!

 

Определим n!=1*2*3*…*n, 0!=1, n!=(n-1)!*n

 

Например:

1. Число способов стать в очередь за стипендией из 17 человек?

P17=17!

 

2. Сколькими способами можно расставить на полке 5 книг?

P5=5!

 

3. Сколько различных слов можно образовать, переставляя буквы в слове "ковш"?

P4=4!

 

 

Размещения

 

Размещения – упорядоченная последовательность из m элементов множества, содержащего всего n элементов.

Различные размещения – отличаются совокупностью элементов и (или) порядком их следования.

 

Например:

Пусть A={1,2,3}

Размещения из 3 по 2: 12, 21, 13, 31, 23, 32.

 

Число размещений из n по m равно:

 

 

Например:

1. Сколькими способами можно расставить на полке 5 книг из 7?

 

2. Сколько различных 4х символьных идентификаторов можно получить в алфавите {A,B,C,D,E}.

Замечание:

Формула верна для всех m£n.

При m=n = =Pn.

 

Сочетания

 

Сочетания из k по m – набор из m элементов, без учета порядка элементов в наборе. Сочетание – произвольное неупорядоченное m-подмножество из n элементов. Различные сочетания – отличаются набором элементов, но не их порядком.

Например:

A={1,2,3}

Сочетания из 3 по 2: 12, 31, 32.

 

Число сочетаний из n различных объектов по m равно:

, m<n.

 

 

Anm=Cnm*m! Þ Cnm= =

 

 

Свойства сочетаний

           
     
 

 


при k£0 и k ³n

 

 

2 Симметричность числа сочетаний:

 

 

3 Правило Паскаля:

 

Для числа сочетаний из n по m справедливо следующее рекуррентное соотношение:

 

 
 

 

 


4 Треугольник Паскаля

 
 


Числа, n=0,1 … выпишем в виде треугольника:

 

 
 


n=0 1

1 1 1

2 1 2 1

3 1 3 3 1

4 1 4 6 4 1

5 1 5 10 10 5 1

                   
       
 
 
 
 
   

 

 

 

 


Коэффициенты − биноминальные коэффициенты в выражении, которое известно, как бином Ньютона.

 

 


При a=x=1

           
   
   
 
 


, если, - число k-элементных подмножеств

 
 

Соединения с повторениями

 

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

 



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-12-29 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: