Рассмотрим некоторые комбинаторные задачи

Элементы комбинаторики

Комбинаторика с (лат. соединение, сочетание) — раздел математики изучающий приёмы вычислений числа различных комбинаций.

Какие задачи называют комбинаторными? Те, где спрашивается каким числом можно осуществить требуемое.

1. Принципы в подсчёте числа комбинации или правила суммы и произведения.

Большинство задач решается с помощью этихдвух принципов.

Принцип суммы. «Если некоторый объект А можно выбрать т способами, а другой объект В можно выбрать n способами, то выбор «либо А, либо В» можно осуществить (т +n) способами».

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

Пример 1......

Принцип произведения. «Если объект А можно выбрать т способами, и если после каждого такого выбора объект В можно выбрать n способами, то выбор пары «А и В» в указанном порядке можно осуществить (т n) способами».

Пример 2......

2. Комбинации по типу перестановок, размещений и сочетаний. Такие комбинации встречаются чаще обычного. Рассмотрим их.

2.1. Перестановки. Пусть имеется множество из n элементов. Установленный в некотором множестве порядок называют перестановкой его элементов.

Примеры перестановок: распределение n различных должностей среди n человек или расположение n различных предметов в одном ряду.

Зададимся вопросом: «Сколько различных перестановок можно образовать в множестве из n элементов!» Число перестановок обозначается Рn (читается "Р из n").

Чтобы вывести формулу числа перестановок, представим себе n ячеек, пронумерованных числами 1,2,...,n. Все перестановки будем образовывать, располагая элементы множества в этих ячейках. В первую ячейку можно занести любой из n элементов (иначе: первую ячейку можно заполнить n различными способами). Заполнив первую ячейку, можно найти (n-1) вариантов заполнения второй ячейки. Таким образом, существует n(n-1) вариантов заполнения двух первых ячеек. При заполнении первых двух ячеек можно найти (n-2) варианта заполнения третьей ячейки, откуда получается, что три ячейки можно заполнить n(n-1)(n-2) способами. Продолжая этот процесс, получим, что число способов заполнения n ячеек равно n(n-1)(n-2)·…· 3·2 ·1. Отсюда

Рn = n(n-1)(n-2)·…· 3·2 ·1.

Число n (n-2)·…· 3·2 ·1, то есть произведение всех натуральных чисел от 1 до n, называется «n-факториал» и обозначается n! Отсюда Pn=n!



По определению считается: 1!=1. Но чему равен 0!=?. Для любого n>1 справедливо
n!=n(n-1)! Положим n=1, тогда 1!=1·0!, следовательно, 0!=1.

Пример 3. Сколько существует вариантов замещения пяти различных вакантных должностей между пятьюкандидатами?

N=5!=5·4·3·2·1=120.

2.2. Размещения.Размещениями из n элементов по т элементов будем называть упорядоченные подмножества, состоящие из т элементов множества, состоящего из n элементов. Число размещений из n элементов по т элементов обозначается (читается "А из n по т ").

Зададимся вопросом: «Сколько упорядоченных подмножеств по т элементов в каждом можно получить из заданного множества в n элементов?»

Одно размещение из n элементов по т элементов может отличаться от другого как набором элементов, так и порядком их расположения.

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

В задачах о размещениях полагается т < п. В случае если т=n, то легко получить = Рn =n!

Для вычисления используем тот же метод, что использовался для подсчета Рn только здесь выберем лишь т ячеек. Первую ячейку можно заполнить n способами, вторую, при заполненной первой, можно заполнить (n-1) способами. Таким образом, существует n(n- 1) вариантов заполнения первых двух ячеек. Можно продолжать этот процесс до заполнения последней т -й ячейки. Эту ячейку при заполненных первых (m – 1) ячейках можно заполнить
n – (m – 1) = n – m +1 способами. Таким образом, все т ячеек заполняются числом способов, равным

n(n – 1)(n – 2)... (n – m + 2)(n – m + 1) =



Отсюда получаем:

Пример 4. Сколько существует различных вариантов выбора четырёх кандидатур из девяти специалистов для поездки в четыре страны?

2.3. Сочетания. Сочетаниями из n элементов по т элементов называются подмножества, состоящие из т элементов множества, состоящего из n элементов.

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

Число сочетаний из n элементов по тэлементов обозначается (читается "С из n по т ").

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

Выведем формулу для подсчета числа сочетаний. Пусть имеется множество из n элементов. Образуем подмножество, содержащее т элементов, т.е. сочетание. Известно число упорядоченных подмножеств из т элементов всего множества из n элементов, т.е. размещений из n по т: . Количество неупорядоченных подмножеств будет в m! раз меньше. Т.е. во столько раз сколькими способами можно установить порядок во множестве из тэлементов. Следовательно, .

Пример 5. Шесть человек из пятнадцати можно выбрать числом способов, равным

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

Эту формулу можно легко доказать, используя формулу для числа сочетаний.

Рассмотрим некоторые комбинаторные задачи.

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

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

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

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

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

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

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

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

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

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

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

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

Задача 4. Сколько существует различных вариантов рассадки двенадцати человек за круглым столом, причём один вариант отличается от другого тем, что хотя бы у одного человека при разных вариантах разные соседи слева.

Ответы: 1) 8·9!; 2) ; 3) ; 4) 11!

Решение задачи 1. Всего существует 10! различных перестановок десяти книг. Чтобы подсчитать, сколько можно найти перестановок, в которых первый и пятый тома стоят рядом, предположим, что к первому тому приклеен справа пятый том, и они как бы образуют отдельную книгу. Таким образом, получилось девять книг, которые могут быть расставлены 9! способами. Теперь нужно учесть, что первый и пятый тома могут быть склеены в другом порядке, и можно получить ещё 9! различных перестановок десяти книг, в которых первый и пятый тома стоят рядом. Отсюда следует, что ответ задачи составляет число, равное 10! – 2·9! = 8·9!

Решение задачи 2. Один выбор тройки автомобилей малой грузоподъёмности от другого может отличаться не только составом выбранных машин, но и их распределением по торговым организациям. Возможно, что эти торговые организации расположены на различных расстояниях от автокомбината, что у них разные условия оплаты труда и т. п. Таким образом , здесь речь идет о размещениях из семи по три, число которых равно .

Напротив, выбор тяжелых грузовиков определяется только их составом, так как все они будут работать, как можно заключить из формулировки задачи, в одинаковых условиях. Таким образом, здесь речь идет о сочетаниях из десяти по пять, число которых равно .

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

Решение задачи 3. Если флаги составлять из трёх полос трёх разных цветов, то один флаг от другого может отличаться не только выбором цветов полос, но и порядком их расположения. Это значит, что из пяти кусков можно изготовить различных флагов, состоящих из трёх полос трёх различных цветов.

По условию задачи каждый флаг можно изготовить из полос двух цветов, например, следующих сверху вниз в таком порядке: "красная, белая, красная", или в таком порядке: "белая, красная, белая". Выбор двух цветов можно осуществить числом способов, равным и при каждом варианте выбора получить два различных флага.

Из сказанного следует, что всего можно изготовить различных флагов.

Решение задачи 4.

Заномеруем всех людей числами от 1 до n. Посадим за стол человека с номером 1 на любое место. Будем называть это место первым. Для того, чтобы занять место слева от него (назовём это место вторым) есть n – 1 претендент. Таким образом, мы получаем n – 1 вариант посадки двух человек. Выбрав кого-либо из претендентов на второе место, и обозначив место слева от второго третьим, будем на третье место иметь n – 2 претендента. Отсюда следует, что первые три места можно занять числом способов, равным (n – 1)(n – 2). Действуя таким образом дальше, мы очевидно переберём все способы посадки n человек за круглым столом, и этих способов будет
(n – 1)·(n – 2)·…·3·2 =(n – 1)!


6521458318364463.html
6521495292808359.html
    PR.RU™