Соединения без повторений
В этом разделе будут рассмотрены три вида соединений без повторений: размещения, перестановки и сочетания. Ради краткости добавку «без повторений» будем опускать. 1. Размещения.Размещения из n элементов по – это упорядоченные наборы из попарно различных элементов -множества . Таким образом, два размещения из элементов по различаются либо порядком, либо составом входящих в них элементов. Например, размещения из 3-множества по 2 исчерпываются следующими упорядоченными парами: , , , , , . Нас будет интересовать задача нахождения числа всех размещений из элементов по . В качестве первого элемента можно выбрать любой из элементов множества . После того как выбран первый элемент, второй элемент можно выбрать лишь способами (можно взять любой элемент, исключая выбранный). После выбора первых двух элементов остаются лишь возможности выбрать третий элемент и т. д. Последний -й элемент можно выбрать способами – ведь до него уже выбраны элемент, а потому осталось лишь элементов. По правилу произведения получаем, что число всевозможных упорядоченных наборов равно произведению чисел , , , …, , т.е. справедлива следующая Т е о р е м а 1.Число размещений из элементов по находится по формуле = . (1) Напомним, что произведение первых n натуральных чисел, т.е. , называют n-факториалом и обозначают . Произведение можно записать в виде дроби = и поэтому формулу (1) можно переписать следующим образом = . (2) В частности, при из формулы (2) получаем = = 1. Это означает, что существует единственный упорядоченный набор длины 0 – пустой кортеж, не имеющий ни одной компоненты. Пример 1.Найти число пятизначных чисел в десятичной системе счисления, в записи которых цифры не повторяются. □ Рассуждая по аналогии с тем, как это делалось при рассмотрении примера 1 (2-й способ) из § 2, приходим к выводу, что искомое число есть . 2. Перестановки.Рассмотримтеперь различные линейные упорядочения данного -множества . Получаемые при этом упорядоченные наборы отличаются друг от друга лишь порядком входящих в них элементов. Их называют перестановками (без повторений) из n элементов, а их число обозначают через . Например, если , то = 6, так как из трех элементов можно составить шесть перестановок: , , , , , . Общая формула для получается из формулы (1), поскольку перестановка из элементов – это то же самое, что размещение без повторений из элементов по . Полагая в (1) получим = = = = . Итак, справедлива Т е о р е м а 2.Число перестановок из элементов равно -факториал, т.е. = . (3) Полагая в формуле (2) , получаем = . (4) Сравнивая (3) и (4), приходим к выводу, что 0! = 1. На первый взгляд это равенство кажется парадоксальным. Но для всех справедливо равенство = . Если потребовать, чтобы это равенство было справедливо и при , то получим . Отсюда вновь следует, что естественно положить0! = 1. Пример 2.Сколькимиспособамиможно расположить на полке 7 различных учебников так, чтобы «Алгебра» и «Геометрия» не стояли рядом? □ Условимся указанные учебники обозначать для краткости буквами А и Г соответственно. Число всевозможных способов расстановки учебников равно числу перестановок из семи элементов, т.е. . Но при этом сосчитаны и те, в которых встречаются рядом учебники А и Г, причем в двух позициях: АГ и ГА. Считая АГ и ГА за одну книгу, для каждого такого расположения получим расстановок, в которых учебники А и Г встречаются рядом. Искомое число расстановок учебников равно . 3. Сочетания.Одной из важнейших задач комбинаторики является подсчет числа k-подмножеств данного n-множества . Такие неупорядоченные подмножества называются сочетаниями из элементов по , а их число обозначают через (от французского слова combinaison – сочетание). Например, из элементов 4-множества можно составить следующие 2-множества: , , , , , . Число этих подмножеств равно 6. Следовательно, = 6. Отметим, что = 1, так как каждое множество имеет лишь одно 0-множество, а именно, пустое множество . Далее понятно, что = , поскольку в ‑множества содержится одноэлементных подмножеств. Ясно также, что . Выведем формулу, выражающую через и . Для этого укажем способ получения всех размещений из элементов по . Выберем любое k-подмножество данного n-множества . Это можно сделать способами. Каждое такое k-подмножество упорядочим всевозможными способами. Таких различных упорядочений столько, сколько можно составить перестановок из элементов, т.е. = . Понятно, что таким способом получатся все размещений из элементов по . Значит, имеет место равенство = . Отсюда вытекает справедливость следующего утверждения. Т е о р е м а 3.Число сочетаний из n элементов по k вычисляется по формуле: = = = . (5) Пример 3.Найти число всех диагоналей правильного n-угольника. □ Любые две вершины n-угольника однозначно определяют отрезок, соединяющие эти вершины. Поэтому число всевозможных отрезков, соединяющих вершины n-угольника, равно числу сочетаний из по 2, т.е. . Но среди них находятся и сторон n-угольника, которые диагоналями не являются, Таким образом, искомое число равно . Например, при получаем, что правильный 10-угольник имеет = 35 диагоналей.
Свойства сочетаний. . = . □ В самом деле, в силу формулы (5) имеем = = = . . = . □ Действительно,
= = = . . + = . □ В самом деле, + = + = = = = . . + + ….+ + … + = . □ Действительно, сумма + + ….+ + … + равна числу всех подмножеств -множества, а по теореме 5 из § 2 это число равно . 4. Треугольник Паскаля.Для вычисления числа сочетаний удобно пользоваться таблицей, имеющую форму треугольника, в n‑й строке (n=0,1,2,…) которой выписываются сочетания , , …., :
. . . . . . . . . …. . . . . . . . . . . . Таблица 1.
Такую треугольную таблицу называют треугольником Паскаля по имени французского математика Блэза Паскаля (1623‑1666), в трудах которого она встречается. Это название исторически неточно, так как такую таблицу знали уже арабские математики Гиясэддин Каши и Омар Хайям, жившие в XIII веке, а из европейских ученых с ней был знаком итальянский математик Николо Тарталья (1550‑1557). Непосредственно свойств ‑ сочетаний вытекают следующие
Популярное: Организация как механизм и форма жизни коллектива: Организация не сможет достичь поставленных целей без соответствующей внутренней... Модели организации как закрытой, открытой, частично открытой системы: Закрытая система имеет жесткие фиксированные границы, ее действия относительно независимы... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (1302)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |