Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Сочетания
В тех случаях, когда не имеет значения порядок элементов в подмножестве некоторого множества, а лишь его состав, говорят о сочетаниях. К сочетаниям без повторений приводит следующая задача комбинаторики. Сколько -элементных подмножеств с различными элементами можно составить из элементов -множества ? Такие подмножества называют сочетаниями без повторений из элементов по или короче -сочетаниями, а их число обозначают (от французского слова combinaison – сочетание). Другими словами, сочетаниями без повторений называется неупорядоченная -выборка, в которой элементы не повторяются. Формулу для числа сочетаний легко получить из формулы (2) для числа размещений. Выберем какое-нибудь -элементное подмножество . Его можно упорядочить способами, а число таких подмножеств есть . Тогда справедлива формула , (5) откуда . (6) Пример 5. Сколько всего партий играется в шахматном турнире с участниками? Ответ: , так как каждая партия однозначно определяется двумя ее участниками. Пусть множество состоит из элементов различных типов: . Множество , составленное из , в котором элементы могут повторяться, называется мультимножеством. Для задания мультимножества надо указать число вхождений в него каждого элемента: , где – мощность мультимножества. Число мультимножеств мощности , составленных из элементов -множества , называют сочетаниями с повторениями и обозначают . Другими словами, сочетаниями с повторениями называется неупорядоченная -выборка, в которой элементы могут повторяться. Зашифруем каждую комбинацию из элементов с помощью нулей и единиц: для каждого типа напишем столько единиц, сколько элементов этого типа входит в комбинацию, а различные типы отделим друг от друга нулями. Если элементы какого-нибудь типа не вошли в комбинацию, то надо писать два или большее число нулей. При этом получим единиц и нулей. Тогда число будет равно числу перестановок с повторениями из единиц и нулей: . Так как , то . (7) Встречаются задачи, в которых на сочетания с повторениями налагается дополнительное условие – в них обязательно должны входить элементы фиксированных типов . В этом случае . В частности, если и требуется, чтобы в -подмножество с повторениями входил по крайней мере один элемент каждого из типов , то получим мультимножеств. Пример 6. В кондитерском магазине продавались 4 сорта пирожных: наполеоны, эклеры, песочные и слоеные. Сколькими способами можно купить 7 пирожных? Решение. Мощность мультимножества , число различных элементов . Число способов покупки пирожных равно .
5. Свойства чисел
Числа обладают целым рядом замечательных свойств, которые выражают различные соотношения между -подмножествами -множества . 1) . Это свойство непосредственно следует из определения чисел : . 2) . Для доказательства поставим в соответствие подмножеству его дополнение . Это соответствие взаимно-однозначное. При этом, если , то . Следовательно, по принципу биекции число подмножеств, составленных из элементов столько же, сколько подмножеств, составленных из элементов. Формально это свойство вытекает также из формулы (6). 3) . Для доказательства разобьем все -элементные подмножества множества на два класса: а) подмножества, не содержащие элемент . Это будут -элементные подмножества -множества, поэтому число их равно ; б) подмножества, содержащие элемент . Если из каждого такого подмножества удалить элемент , то получим -элементные подмножества -множества, число которых равно . Свойство 3) вытекает, таким образом, из правила сложения. Это свойство можно доказать также формально, используя формулу (6). При имеем . Так как , то полагают . Кроме того, придерживаются соглашения при . Тогда свойство 3) позволяет последовательно вычислить числа при . Вычисления представляют в виде треугольника Паскаля по имени французского математика Б. Паскаля (1623 – 1662), в трудах которого он применяется. Это название исторически неточно, так как такую таблицу знал уже арабский математик Омар Хайям (XIII в.). Этот треугольник имеет вид: 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 ……………………………………………..
|