План

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

Интуитивное представление о числе, по–видимому, так же старо, как и само человечество, хотя с достоверностью проследить все ранние этапы его развития в принципе невозможно. Прежде чем человек научился считать или придумал слова для обозначения чисел, он, несомненно, владел наглядным, интуитивным представлением о числе, позволявшим ему различать одного человека и двух людей или двух и многих людей. То, что первобытные люди сначала знали только “один”, “два” и “много”, подтверждается тем, что в некоторых языках, например в греческом, существуют три грамматические формы: единственного числа, двойственного числа и множественного числа. Позднее человек научился делать различия между двумя и тремя деревьями и между тремя и четырьмя людьми. Счет изначально был связан с вполне конкретным набором объектов, и самые первые названия чисел были прилагательными. Например, слово “три” использовалось только в сочетаниях “три дерева” или “три человека”; представление о том, что эти множества имеют между собой нечто общее – понятие троичности – требует высокой степени абстракции. О том, что счет возник раньше появления этого уровня абстракции, свидетельствует тот факт, что слова “один” и “первый”, равно как “два” и “второй”, во многих языках не имеют между собой ничего общего, в то время как лежащие за пределами первобытного счета “один”, “два”, “много”, слова “три” и “третий”, “четыре” и “четвертый” ясно указывают на взаимосвязь между количественными и порядковыми числительными.

Названия чисел, выражающие весьма абстрактные идеи, появились, несомненно, позже, чем первые грубые символы для обозначения числа объектов в некоторой совокупности. В глубокой древности примитивные числовые записи делались в виде зарубок на палке, узлов на веревке, выложенных в ряд камешков, причем подразумевалось, что между пересчитываемыми элементами множества и символами числовой записи существует взаимно однозначное соответствие. Но для чтения таких числовых записей названия чисел непосредственно не использовались. Ныне мы с первого взгляда распознаем совокупности из двух, трех и четырех элементов; несколько труднее распознаются на взгляд наборы, состоящие из пяти, шести или семи элементов. А за этой границей установить на глаз их число практически уже невозможно, и нужен анализ либо в форме счета, либо в определенном структурировании элементов. Счет на бирках, по–видимому, был первым приемом, который использовался в подобных случаях: зарубки на бирках располагались определенными группами подобно тому, как при подсчете избирательных бюллетеней их часто группируют пачками по пять или десять штук. Очень широко был распространен счет на пальцах, и вполне возможно, что названия некоторых чисел берут свое начало именно от этого способа подсчета.

Важная особенность счета заключается в связи названий чисел с определенной схемой счета. Например, слово “двадцать три” – не просто термин, означающий вполне определенную (по числу элементов) группу объектов; это термин составной, означающий “два раза по десять и три”. Здесь отчетливо видна роль числа десять как коллективной единицы или основания; и действительно, многие считают десятками, потому что, как отметил еще Аристотель, у нас по десять пальцев на руках и на ногах. По той же причине использовались основания пять или двадцать. На очень ранних стадиях развития истории человечества за основания системы счисления принимались числа 2, 3 или 4; иногда для некоторых измерения или вычислений использовались основания 12 и 60.

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

1.2. Обозначения чисел и история систем счисления Подробнее>>

Система счисления – очень сложное понятие.

В непозиционных системах каждая цифра имеет свой вес и ее значение не зависит от положения в числе – от позиции. Пример – римская система. Скажем, число 76 в этой системе выглядит так:

Для мультипликативной системы нужно знать изображение цифр и их значение, а так же основание системы счисления.

Основанием системы счисления называется количество цифр и символов, применяющихся для изображения числа. Например р=10.

Подробнее>>

Двоичная система счисления является основной системой представления информации в памяти компьютера.

где a, b, c цифры от 0 до 9 (горизонтальная линия над буквами показывает, что это именно цифры a, b, c, а не произведение чисел a, b, c).

где a, b, c цифры 0 и 1.

– 4-х разрядное двоичное число.

В результате .

Подробно>>

Выполнение арифметических операций в двоичной системе. Подробнее>>

В компьютерах двоичная система особенно удобна тем, что двоичные цифры соответствуют тому, что электронная система может находиться лишь в одном из двух состояний – либо “выключено” (цепь разомкнута, двоичная цифра 0), либо “включено” (цепь замкнута, двоичная цифра 1). Числа, записанные в двоичной системе, требуют большего числа знаков, чем их аналоги в десятичной системе, но при проектировании компьютеров, предназначенных для работы с числами, не превышающими 10 миллионов, оказалось, что легче оперировать с 24-разрядными двоичными числами (т.е. 24 реле или переключателя типа “вкл.” – “выкл.”), чем с семизначными десятичными числами (реле или переключателями, которые могут находиться в 10 состояниях). И в двоичной, и в десятичной системе суть состоит в позиционном принципе записи чисел, поэтому ясно, что современные суперкомпьютеры стали возможны благодаря тому, что четыре тысячи лет назад в Месопотамии было совершено важнейшее открытие в области обозначения чисел.

Подробнее>>

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

1)распределение n различных должностей среди n человек;

2)расположение n различных предметов в одном ряду.

Сколько различных перестановок можно образовать во множестве ? Число перестановок обозначается P_n (читается “Р из n”).

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

Число n(n – 1)(n – 2)...× 3× 2× 1, то есть произведение всех натуральных чисел от 1 до n, называется “n-факториал” и обозначается n! Отсюда P_n =n!

По определению считается: 1!=1; 0!=1.

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

1) Сколькими способами можно выбрать из 15 человек 5 кандидатов и назначить их на 5 различных должностей?

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

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

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

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

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

Число сочетаний из n элементов по k элементов обозначается (читается “C из n по k”).

Выведем формулу для подсчета числа сочетаний. Пусть имеется множество и нужно образовать упорядоченное подмножество множества , содержащее k элементов (то есть образовать размещение). Делаем это так:

1) выделим какие-либо k элементов из n элементов множества Это, согласно сказанному выше, можно сделать способами;

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

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

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

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

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

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

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

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

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

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

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

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