Реферат: Комбинаторные формулы

2) упорядочим выделенные k элементов, что можно сделать способами. Всего можно получить вариантов (упорядоченных подмножеств), откуда следует: , то есть

(1)

Пример: 6 человек из 15 можно выбрать числом способов, равным

Несложно понять, что осуществить выбор подмножества из т элементов множества, насчитывающего п элементов, можно, выбрав п–т элементов, которые не войдут в интересующее нас подмножество. Отсюда следует свойство числа сочетаний

Эту формулу можно доказать, используя формулу (1).

Задачи на подсчет числа подмножеств конечного множества называются комбинаторными. Рассмотрим некоторые комбинаторные задачи.

1.Из семи заводов организация должна выбрать три для размещения трех различных заказов. Сколькими способами можно разместить заказы?

Так как из условия ясно, что каждый завод может либо получить один заказ, либо не получить ни одного, и что выбрав три завода, можно по-разному разместить среди них заказы, здесь нужно считать число размещений

2.Если из текста задачи 1 убрать условие различия трех заказов, сохранив все остальные условия, получим другую задачу. Теперь способ размещения заказов определяется только выбором тройки заводов, так как все эти заводы получат одинаковые заказы, и число вариантов определяется как число сочетаний.

3.Имеются 7 заводов. Сколькими способами организация может разместить на них три различных производственных заказа? (Заказ нельзя дробить, то есть распределять его на нескольких заводах).

В отличие от условия первой задачи, здесь организация может отдать все три заказа первому заводу или, например, отдать два заказа второму заводу, а один - седьмому.

Задача решается так. Первый заказ может быть помещен семью различными способами (на первом заводе, на втором и т.д.). Поместив первый заказ, имеем семь вариантов помещения второго (иначе, каждый способ помещения первого заказа может сопровождаться семью способами помещения второго). Таким образом, существует 7×7=49 способов размещения первых двух заказов. Разместив их каким-либо образом, можем найти 7 вариантов помещения третьего (иначе, каждый способ размещения первых двух заказов может сопровождаться семью различными способами помещения третьего заказа). Следовательно, существуют 49×7=7³ способов размещения трех заказов. (Если бы заказов было n, то получилось бы 7ⁿ способов размещения).

4.Как решать задачу 3, если в ее тексте вместо слов "различных производственных заказа" поставить "одинаковых производственных заказа"? Это трудная задача. Ниже приводится аналогичная задача– Задача V с решением.

5.Добавим к условию задачи 1 одну фразу: организация также должна распределить три различных заказа на изготовление деревянных перекрытий среди 4-х лесопилок. Сколькими способами могут быть распределены все заказы?

Каждый из способов распределения заказов на заводах может сопровождаться способами размещения заказов на лесопилках. Общее число возможных способов размещения всех заказов будет равно

6. Риэлтерская фирма предлагает на продажу 5 больших квартир и 4 малогабаритных квартиры. Банк намеревается купить 4квартиры, причём среди них не должно быть более двух малогабаритных. Сколько вариантов выбора имеет банк?

Банк может купить 4 большие квартиры. У него есть возможность выбрать 4 из 5-ти предлагаемых квартир, и число вариантов здесь равно . Если банк решит купить три большие квартиры и одну малогабаритную, то число вариантов выбора у него будет равно . Если будет принято решение купить две малогабаритных квартиры и две больших квартиры, то число вариантов будет равным . Таким образом, у банка есть 105 вариантов выбора.

Задачи с решениями.

Задача I.

Сколькими различными способами можно расставить на полке собрание сочинений, состоящее из 10-ти томов, при условии, что первый и пятый тома не должны стоять рядом.

Задача II.

Автокомбинат имеет 7 автомобилей малой грузоподъёмности и 10 большегрузных автомобилей. Нужно выбрать 3 автомобиля малой грузоподъёмности для обслуживания трёх торговых организаций и 5 большегрузных автомобилей для работы на стройке. Сколькими способами автокомбинат может осуществить свой выбор?

Задача III.

Имеется пять кусков материи разных цветов. Сколько из этих кусков можно сшить различных флагов, если флаги состоят из трёх горизонтальных полос, причём две соседние полосы должны быть разного цвета?

Задача IV.