Перестановки, размещения и сочетания. Формулы
жүктеу/скачать 21,79 Kb.
|
- Бұл бет үшін навигация:
- Размещения без повторений из n элементов по
|
Перестановки, размещения и сочетания. Формулы. В этой теме рассмотрим основные понятия комбинаторики: перестановки, сочетания и размещения. Выясним их суть и формулы, по которым можно найти их количество. Для работы нам понадобятся кое-какие вспомогательные сведения. Начнём с такого фундаментального математического понятия как множество. Подробно понятие множества было раскрыто в теме "Понятие множества. Способы задания множеств". Очень краткий рассказ про множества: показать\скрыть Рассмотрим некое непустое конечное множество U, мощность которого равна n, |U|=n (т.е. в множестве U имеется n элементов). Введём такое понятие, как выборка (некоторые авторы именуют её кортежем). Под выборкой объема k из n элементов (сокращённо (n,k)-выборкой) будем понимать набор элементов (a1,a2,…,ak), где ai∈U. Выборка называется упорядоченной, если в ней задан порядок следования элементов. Две упорядоченные выборки, различающиеся лишь порядком элементов, являются различными. Если порядок следования элементов выборки не является существенным, то выборку именуют неупорядоченной. Заметьте, что в определении выборки ничего не сказано про повторения элементов. В отличие от элементов множеств, элементы выборки могут повторяться. Для примера рассмотрим множество U={a,b,c,d,e}. Множество U содержит 5 элементов, т.е. |U|=5. Выборка без повторений может быть такой: (a,b,c). Данная выборка содержит 3 элемента, т.е. объём этой выборки равен 3. Иными словами, это (5,3)-выборка. Выборка с повторениями может быть такой: (a,a,a,a,a,c,c,d). Она содержит 8 элементов, т.е. объём её равен 8. Иными словами, это (5,8)-выборка. Рассмотрим ещё две (5,3)-выборки: (a,b,b) и (b,a,b). Если мы полагаем наши выборки неупорядоченными, то выборка (a,b,b) равна выборке (b,a,b), т.е. (a,b,b)=(b,a,b). Если мы полагаем наши выборки упорядоченными, то (a,b,b)≠(b,a,b). Рассмотрим ещё один пример, немного менее абстрактный :) Предположим, в корзине лежат шесть конфет, причём все они различны. Если первой конфете поставить в соответствие цифру 1, второй конфете – цифру 2 и так далее, то с конфетами в корзине можно сопоставить такое множество: U={1,2,3,4,5,6}. Представьте, что мы наугад запускаем руку в корзинку с целью вытащить три конфеты. Вытащенные конфеты – это и есть выборка. Так как мы вытаскиваем 3 конфеты из 6, то получаем (6,3)-выборку. Порядок расположения конфет в ладони совершенно несущественен, поэтому эта выборка является неупорядоченной. Ну, и так как все конфеты различны, то выборка без повторений. Итак, в данной ситуации говорим о неупорядоченной (6,3)-выборке без повторений. Теперь подойдём с иной стороны. Представим себе, что мы находимся на фабрике по производству конфет, и на этой фабрике производятся конфеты четырёх сортов. Множество U в этой ситуации таково: U={1,2,3,4} (каждая цифра отвечает за свой сорт конфет). Теперь вообразим, что все конфеты ссыпаются в единый жёлоб, около которого мы и стоим. И, подставив ладони, из этого потока отбираем 20 конфет. Конфеты в горсти – это и есть выборка. Играет ли роль порядок расположения конфет в горсти? Естественно, нет, поэтому выборка неупорядоченная. Всего 4 сорта конфет, а мы отбираем двадцать штук из общего потока – повторения сортов неизбежны. При этом выборки могут быть самыми различными: у нас даже могут оказаться все конфеты одного сорта. Следовательно, в этой ситуации мы имеем дело с неупорядоченной (4,20)-выборкой с повторениями. Рассмотрим ещё пару примеров. Пусть на кубиках написаны различные 7 букв: к, о, н, ф, е, т, а. Эти буквы образуют множество U={к,о,н,ф,е,т,а}. Допустим, из данных кубиков мы хотим составить "слова" из 5 букв. Буквы этих слов (к примеру, «конфе», «тенко» и так далее) образуют (7,5)-выборки: (к,о,н,ф,е), (т,е,н,к,о) и т.д. Очевидно, что порядок следования букв в такой выборке важен. Например, слова «нокфт» и «кфтон» различны (хотя состоят из одних и тех же букв), ибо в них не совпадает порядок букв. Повторений букв в таких «словах» нет, ибо в наличии только семь кубиков. Итак, набор букв каждого слова представляет собой упорядоченную (7,5)-выборку без повторений. Еще один пример: мы составляем всевозможные восьмизначные числа из четырёх цифр 1, 5, 7, 8. Например, 11111111, 15518877, 88881111 и так далее. Множество U таково: U={1,5,7,8}. Цифры каждого составленного числа образуют (4,8)-выборку. Порядок следования цифр в числе важен, т.е. выборка упорядоченная. Повторения допускаются, поэтому здесь мы имеем дело с упорядоченной (4,8)-выборкой с повторениями. Размещения без повторений из n элементов по k Размещение без повторений из n элементов по k – упорядоченная (n,k)-выборка без повторений. Так как элементы в рассматриваемой выборке повторяться не могут, то мы не можем отобрать в выборку больше элементов, чем есть в исходном множестве. Следовательно, для таких выборок верно неравенство: n≥k. Количество размещений без повторений из n элементов по k определяется следующей формулой: Akn=n!(n−k)!(1) Что обозначает знак "!"? : показать\скрыть жүктеу/скачать 21,79 Kb. Достарыңызбен бөлісу:
|