Тема 1.3.2- 1.3.3 Размещения, перестановки, сочетания
Правила суммы и произведения – это общие правила решения комбинаторных задач. Кроме них в комбинаторике пользуются формулами для подсчета числа отдельных видов комбинаций, которые встречаются наиболее часто. Рассмотрим некоторые из них. Используя цифры 7,4 и 5образовать всевозможные двузначные числа. Решение: 77, 74, 75, 47, 44, 57, 54, 55. Мы образовали различные кортежи длины 2 с повторяющимися элементами из трех цифр. В комбинаторике такие кортежи называют размещениями с повторениями из трех элементов по два элемента. Определение. Размещение с повторениями из k элементов по m элементов – это кортеж длины m, составленный из m элементов k элементного множества. Таким образом два размещения из k элементов по m элементов отличаются друг от друга либо составом элементов, либо порядком их расположения. Возникает вопрос: «Сколько всевозможных размещений по m элементов каждое можно образовать из k элементов данного множества?». Обозначают число всевозможных размещений с повторениями из k элементов по m элементов – А . Выведем эту формулу. Пусть в множестве Хсодержится k элементов. Будем образовывать из них различные кортежи по m элементов. Такие кортежи образуют множество Х х Х х … Х, содержащее m множителей. По правилу произведения n(Х х Х х …х Х) = n(Х) х n(Х)… n (Х) = k х k … х k = km m множителей m множителей
Таким образом А лn = km Пользуясь формулой, легко посчитать (смотри задачу выше), что = 32 = 9, т.к. речь идет о размещениях с повторениями из трех элементов по два. Задача: Из цифр 7,4 и 5 составить двузначные числа, чтобы цифры в записи числа не повторялись. Решение: 74, 75, 47, 45, 57, 54. Таким образом, встречаются задачи, в которых требуется подсчитать числа кортежей длины m, образованных из k элементов некоторого множества, при условии что, элементы в кортеже не повторяются. Такие кортежи называются размещениямибез повторений из k элементов по m элементов. Определение. Размещение без повторений из k элементов по m элементов – это кортеж длины m, составленный из неповторяющихся элементов множества, в котором k элементов. Обозначается - читается: число размещений без повторений из k элементов по m элементов. Выведем эту формулу: Пусть k = n (x). Будем образовывать из них различные размещения без повторений из m элементов. Тогда выбор первого элемента можно осуществить k способами, выбор второго (k – 1) способом (т.к. после выбора первого элемента кортежа в множестве Хостается k -1 элемент). Третий элемент можно выбрать k -2 способами и т.д., третий элемент можно выбрать k- (m -1) способами. Значит, = k (k – 1) (k – 2) … (k – m + 1) m множителей
Задача: Сколько всевозможных трехзначных чисел можно записать, используя цифры 7,4,5, чтобы числа не повторялись? Решение. В задаче рассматриваются размещения без повторений из трех элементов по три, и их число можно подсчитать по формуле: = 3 (3 – 1)(3 – 2) = 6. Числа: 745, 754, 457, 475, 547, 574. Заметим, что в данном случае разные числа получаются в результате перестановки цифр. Поэтому размещения из k элементов по k элементов называется перестановкамииз k элементов без повторений. Обозначают Pk и вычисляютпо формуле: = Pk Читают: число перестановок без повторений из k элементов. Pk = k! (k! = 1 х 2 х 3 … k, читают «k факториал» например, 5! = 1 х 2 х 3 х 4 х 5 = 120). Из элементов множества Х = {7,4,5} можно образовать не только кортежи различной длины, но и различные подмножества. В комбинаторике их называют сочетаниями без повторений. Определение. Сочетание без повторений из k элементов – это m – элементное подмножество множества, содержащего k элементов. Два сочетания из k элементов по m элементов отличаются друг от друга хотя бы одним элементом. Обозначается: Читают: число сочетаний без повторений из k элементов по m элементов. Образуем различные двухэлементные подмножества из элементов множества Х = 7,4,5. Их будет три: 7,4 ; 7,5 ; 4,5. Из элементов каждого такого подмножества можно образовать 2 кортежа длины 2.
(7,4) (7,5) (4,5) (4,7) (5.7) (5,4) Все полученные кортежи являются размещениями без повторений из трех элементов по два и их число равно = 3х2 = 6. т.е. = Пусть n (Х) = k. Образуем из них сочетания без повторений по m элементов. Они будут представлять собой m – элементные подмножества множества Х. Всего таких подмножеств будет . Из элементов каждого подмножества можно образовать m! перестановок, т.е. кортежей длины m В итоге получим m ! х кортежей длины m , образованных из k элементов множества х. Их число равно . Таким образом = m! х à =
Популярное: Почему двоичная система счисления так распространена?: Каждая цифра должна быть как-то представлена на физическом носителе... Почему человек чувствует себя несчастным?: Для начала определим, что такое несчастье. Несчастьем мы будем считать психологическое состояние... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (1767)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |