[Michael_home]

Комбинаторика,
1) то же, что математический комбинаторный анализ.
2) Раздел элементарной математики, связанный с изучением количества комбинаций, подчинённых тем или иным условиям, которые можно составить из заданного конечного множества объектов (безразлично, какой природы; это могут быть буквы, цифры, какие-либо предметы и т.п.).
Одной из важных классических задач комбинаторики является задача нахождения количества способов размещения какого-то числа заданных объектов в некотором заданном количестве мест ("ящиков") таким образом, чтобы они удовлетворяли при этом некоторым заданным условиям (ограничениям). Рассматриваются также размещения с повторением (т. е. всевозможные наборы из m предметов n различных видов, порядок в наборе существен) и сочетания с повторением (то же, но порядок в наборе не существен).

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

Теорема. Число всех размещений с повторениями из n элементов по k равно n^k.

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

Пример 1. Сколькими способами можно выбрать четырехзначное число, в десятичной записи которого нет нуля?
Решение. Четырехзначные числа указанного вида можно рассматривать как строки длиной 4, составленные из элементов множества Х = {1, 2, 3, 4, 5, 6, 7, 8, 9}, т.е. как размещения с повторениями из 9 элементов по 4. Следовательно, искомое число способов равно: 94 = 6561.

Пример 2. Рассмотрим последовательности из 2 чисел, в которых каждый член - целое число в диапазоне от 0 до 1. Как перебрать все такие последовательности?
Решение. Нужно вычислить, сколько всего шагов по перебору вариантов нам нужно сделать. А для этого нам необходимо знать, сколько всего существует размещений с повторениями для заданного количества мест N и заданного количества чисел K, которые мы можем поставить на каждое место.

Итак, рассмотрим имеющиеся у нас N позиций. На первую позицию мы можем поставить любое из K чисел. Какое бы число мы не поставили на первое место, на второе место мы опять можем поставить любое из K чисел, таким образом, первые два места мы можем занять K x K способами. Продолжая так и далее, получим, что занять все позиции числами мы можем K x … x K = K^N способами.
Количество последовательностей длины N из K различных символов равно K^N.
Таким образом, чтобы перейти от первой последовательности к последней, нужно совершить K^N - 1 переход.