Математические основы информатики. Элементы комбинаторики. (Тема 1)

Комбинаторикой называют область математики, в которой изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов.
Определение : Множество (совокупность элементов) называется занумерованным (или счетным), если каждому элементу этого множества сопоставлено свое натуральное число (номер) от 1 до n. Для краткости занумерованные множества также будут называться далее наборами.

Число перестановок.
Определение: Отличающиеся друг от друга порядком наборы, составленные из всех элементов данного конечного множества, называются перестановками этого множества.
Пример 1. Из множества, состоящего из трех элементов {1,2,3}, можно получить следующие перестановки: (1,2,3), (1,3,2), (2,3,1), (2,1,3), (3,2,1), (3,1,2).
Число всех перестановок множества из n элементов обозначается Рn и определяется по формуле
Рn = n!, где n! = 1 • 2 • 3 • ... • n.

Пример 2. Цифры 1, 2, 3, 4 написаны на четырех карточках. Сколько различных четырехзначных чисел можно составить из этих карточек?
Решение. Число различных комбинаций из четырех цифр равно 4! =24.
---------------------------------------------------------------
Пример 3. Цифры 0, 1, 2, 3, 4 написаны на пяти карточках. Сколько различных значимых пятизначных чисел можно составить из этих карточек?
Решение. Число различных комбинаций из пяти цифр равно 5! = 120. Из этого числа необходимо вычесть все комбинации, когда первое место занимает цифра «0», т.к. такие числа не имеют смысла (например, 01324). Очевидно, что число таких комбинаций равно числу перестановок чисел с 1 по 4, или 4! = 24. Таким образом, ответ задачи - 120-24 = 96.

Число размещений.
Определение: Упорядоченные наборы, состоящие из к различных элементов, выбранных из данных n элементов, называются размещениями из n элементов по к. Размещения могут отличаться друг от друга как элементами так и порядком.
Пример 4. Различными размещениями множества из трех элементов {1,2,3} по два будут наборы (1,2), (2,1), (1,3), (3,1), (2,3), (3,2).
Число всех размещений из n элементов по к обозначается
и определяется по формуле

Пример 5. Студентам надо сдать 4 экзамена за 8 дней. Сколькими способами можно составить расписание сдачи экзаменов?
Решение. Занумеруем дни сдачи экзаменов цифрами 1,2,3,... ,8.
Составлять различные расписания можно следующим образом. Выбираем дни для сдачи экзаменов, например, (2,4,6,7), а затем порядок сдачи экзаменов.
Таким образом, нужно составить различные наборы четырех чисел из восьми, которые отличаются между собой не только элементами, но и порядком.
Таких наборов = 8 • 7 • 6 • 5 = 1680.

Число сочетаний.
Определение: Неупорядоченные наборы, состоящие из к элементов, взятых из данных n элементов, называются сочетаниями из n элементов по k. Сочетания отличаются друг от друга только элементами.
Пример 6. Для множества {1,2,3} сочетаниями по 2 элемента являются {1,2}, {1,3}, {2,3}.
Число сочетаний из n элементов по k обозначается
и определяется по формуле

Пример 7. В спортивном турнире участвует 6 команд. Каждая команда должна сыграть с каждой одну игру. Сколько игр сыграно в турнире?
Решение. Различные пары команд образуют сочетания из 6 по 2, поскольку порядок среди двух команд в одной игре безразличен. Следовательно, число игр будет равно
Теорема о числе комбинаций. Число различных комбинаций элементов, составленных из различных групп, вида (а1, а2,... , аr), где аl - элемент l-й группы, содержащей nl элементов, равно n1 ∙ n2...∙ nr.

Пример 8. Из трех групп студентов необходимо составить команду, содержащую по одному человеку из каждой группы. Сколько различных команд можно составить, если в первой группе 15 человек, во второй - 16 и в третьей - 20?
Решение. Согласно вышеприведенному определению ответ задачи - 15 • 16 • 20 = 4800.

Пример 10. Какое количество различных символов (букв, чисел и т.д.) можно передать не более чем пятью знаками кода Морзе, использующего точку (•) и тире ( —)?
Решение. Рассмотрим произвольную позицию в кодировке некоторого символа. Она может иметь два значения: либо точку, либо тире. То же самое относится к любой другой позиции. Тогда, если таких позиций в коде n, то число возможных различных вариантов согласно теореме о числе комбинаций равно 2n. В условии задачи говорится, что в коде может быть не более пяти позиций, что означает возможность кодирования одно-, двухпозиционным кодом и т.д., вплоть до пятипозиционного кода. Тогда ответ задачи
21+22 + 23 + 24 + 25 = 62.

НЬЮТОНА БИНОМ
разложение алгебраической суммы двух слагаемых произвольной степени. Впервые была предложена Ньютоном в 1664–1665:
Коэффициенты формулы называются биномиальными коэффициентами.
Если n – положительное целое число, то коэффициенты обращаются в нуль при любом r > n, поэтому разложение содержит лишь конечное число членов.
Во всех остальных случаях разложение представляет собой бесконечный (биномиальный) ряд. (Условия сходимости биномиального ряда впервые были установлены в начале 19 в. Н.Абелем.)
Такие частные случаи, как (a + b)2 = a2 + 2ab + b2 и (a + b)3 = a3 + 3a2b + 3ab2 + b3 были известны задолго до Ньютона.
Если n – положительное целое число, то биномиальный коэффициент при an – rbr в формуле бинома есть число комбинаций из n по r, обозначаемое Crn или (nr).
При небольших значениях n коэффициенты можно найти из треугольника Паскаля.