1) какое количество методами возможно выбрать из 15 человек 5 кандидатов и назначить их на 5 разных должностей?
2) какое количество методами возможно из 20 книг отобрать 12 и расставить их в ряд на полке?
В задачах о размещениях надеется k n. , если k = n, то легко взять
Для подсчета
используем тот же способ, что употреблялся для подсчета Pn, лишь тут заберём только k ячеек. Первую ячейку возможно заполнить n методами, вторую, при заполненной первой, возможно заполнить n–1 методами. Так, существует п(п – 1) вариантов заполнения первых двух ячеек. Возможно продолжать данный процесс до заполнения последней k–й ячейки. Эту ячейку при заполненных первых k – 1 ячейках возможно заполнить
n–(k–1) (либо n–k+1) методами. Так, все k ячеек заполняются числом способов, равным
Из этого приобретаем:
Пример. какое количество существует разных вариантов выбора 4-х кандидатур из 9-ти экспертов для поездки в 4 разных государства?
Сочетаниями из n элементов по k элементов именуются подмножества, складывающиеся из k элементов множества
(множества, складывающегося из n элементов).
Одно сочетание от другого отличается лишь составом выбранных элементов (но не порядком их размещения, как у размещений).
Число сочетаний из n элементов по k элементов обозначается
(читается C из n по k).
Примеры задач, приводящих к подсчету числа сочетаний:
1) какое количество существует вариантов выбора 6-ти человек из 15 кандидатов для назначения на работу в однообразных должностях?
2) какое количество методами возможно из 20 книг отобрать 12 книг?
Выведем формулу для подсчета числа сочетаний. Пускай имеется множество
и необходимо образовать упорядоченное подмножество множества
, содержащее k элементов (другими словами образовать размещение). Делаем это так:
1) выделим какие-либо k элементов из n элементов множества
Это, в соответствии с вышесказанному, возможно сделать
методами;
2) упорядочим выделенные k элементов, что возможно сделать
методами. Всего возможно взять
вариантов (упорядоченных подмножеств), откуда направляться:
, другими словами
(1)
Пример: 6 человек из 15 возможно выбрать числом способов, равным
Несложно осознать, что осуществить выбор подмножества из т элементов множества, насчитывающего п элементов, возможно, выбрав п – т элементов, каковые не войдут в интересующее нас подмножество. Из этого следует свойство числа сочетаний
Эту формулу возможно доказать, применяя формулу (1).
Задачи на подсчет числа подмножеств конечного множества именуются комбинаторными. Разглядим кое-какие комбинаторные задачи.
1.Из семи фабрик организация обязана выбрать три для размещения трех разных заказов. какое количество методами возможно разместить заказы?
Так как из условия ясно, что любой завод может или взять один заказ, или не взять ни одного, и что выбрав три завода, возможно по-различному разместить среди них заказы, тут необходимо вычислять число размещений
2.В случае если из текста задачи 1 убрать условие различия трех заказов, сохранив все остальные условия, возьмём другую задачу. Сейчас метод размещения заказов определяется лишь выбором тройки фабрик, поскольку все эти фабрики возьмут однообразные заказы, и число вариантов определяется как число сочетаний.
3.Имеются 7 фабрик. какое количество методами организация может разместить на них три разных производственных заказа? (Заказ нельзя дробить, другими словами распределять его на нескольких фабриках).
В отличие от условия первой задачи, тут организация может дать все три заказа первому заводу либо, к примеру, дать два заказа второму заводу, а один — седьмому.
Задача решается так. Первый заказ возможно помещен семью разными методами (на первом заводе, на втором и т.д.). Поместив первый заказ, имеем семь вариантов помещения второго (в противном случае, любой метод помещения первого заказа может сопровождаться семью методами помещения второго). Так, существует 7?7=49 способов размещения первых двух заказов. Разместив их каким-либо образом, можем отыскать 7 вариантов помещения третьего (в противном случае, любой метод размещения первых двух заказов может сопровождаться семью разными методами помещения третьего заказа). Следовательно, существуют 49?7=73 способов размещения трех заказов. (Если бы заказов было n, то оказалось бы 7n способов размещения).
4.Как решать задачу 3, в случае если в ее тексте вместо слов разных производственных заказа поставить однообразных производственных заказа? Это тяжёлая задача. Ниже приводится подобная задача– Задача V с ответом.
5.Добавим к условию задачи 1 одну фразу: организация кроме этого обязана распределить три разных заказа на изготовление древесных перекрытий среди 4-х лесопилок. какое количество методами смогут быть распределены все заказы?
Любой из
способов распределения заказов на фабриках может сопровождаться
методами размещения заказов на лесопилках. Неспециализированное число вероятных способов размещения всех заказов будет равняется
6. Риэлтерская компания предлагает на продажу 5 громадных квартир и 4 малогабаритных квартиры. Банк собирается приобрести 4квартиры, причём среди них не должно быть более двух малогабаритных. какое количество вариантов выбора имеет банк?
Банк может приобрести 4 громадные квартиры. У него имеется возможность выбрать 4 из 5-ти предлагаемых квартир, и число вариантов тут равняется
. В случае если банк примет решение приобрести три громадные квартиры и одну малогабаритную, то число вариантов выбора у него будет равняется
. В случае если будет принято решение приобрести две малогабаритных квартиры и две громадных квартиры, то число вариантов будет равным
. Так, у банка имеется 105 вариантов выбора.
Комбинаторика 3. Число сочетаний
