Комбинаторика.

 

Общие принципы комбинаторики.



Предположим, что, играя в преферанс нам раздали восемь карт одной масти. Обычно карты выстраивают по старшинству. А сколько вообще есть способов расстановки карт? Пять? Десять? Оказывается заметно больше. Давайте рассмотрим почему. На первое место можно поставить одну из восьми карт. На вторую - одну из семи оставшихся и.т.д. Всего же число способов равно. 8*7*6*5*4*3*2*1 = 8!. Восклицательный знак после натурального числа n означает произведение всех натуральных чисел от числа n(включительно) до 0 и читается эн факториал.

Наверно не хочется просто поверить и всё. Где доказательства, что твоё решение правильно, спросите вы. И произведёте приятное впечатление любознательных читателей. Действительно почему? А вот почему. Пусть нам дано некое множество А{a1,a2,a3...an} состоящее из n элементов и множество В{b1,b2,b3...bm} состоящее из m элементов. Задумаемся, а, сколько существует таких упорядоченных пар (а;b), где элемент, а принадлежит множеству А, а элемент b принадлежит множеству В. Существует так называемое
Правило произведения: Множество А*В содержит mn элементов.
Доказательство этого утверждения можно считать очевидным, представив себе прямоугольную таблицу из n столбцов и m строк, на пересечении которых стоит элементы вида apbt, 1 ≤ p ≤ n; 1 ≤ t ≤ m; p,t - целые числа.

Аналогично рассматривается А*В*С , состоящее из упорядоченных троек, содержит nmk элементов(k - число элементов множества С). Это такая же прямоугольная таблица, содержащая mn строк, и k столбцов. Удобна следующая формулировка правила произведения.

Пусть объект а1 можно выбрать n1 различными способами, после каждого выбора объекта а1, объект а2 можно выбрать n2 различными способами, ..., после каждого выбора объектов а1, а2,...,аp-1 объект ар можно выбрать nр различными способами. Тогда количество способов, которыми можно выбрать а1, а2,...,аp равно n1* n2*...*np.

Вернёмся к исходному примеру. Пусть а1 - старшая карта, тогда её можно выбрать 8 способами, то есть n1 = 8, вторую карту а2 можно выбрать 7 способами, то есть n2 = 7 и.т.д. По правилу умножения получаем искомое число 8*7*6*5*4*3*2*1 = 40320. Хорошо видно, что с факториалом надо быть поосторожнее - уж слишком быстро растёт.

Некоторые стандартные схемы получили в комбинаторике свои названия. Скажем и о них

Определения.



Всякая неупорядоченная выборка объёма k из множества, состоящего из n элементов, называется размещением из n элементов по k элементов и обозначается через Ank

Ank = n(n - 1)(n - 2)(n - k + 1), где 1 ≤ k ≤ n

Размещение из n элементов по n называется перестановкой из n элементов и обозначается Pn

из определения размещения, очевидно, что Pn = n!

Всякая неупорядоченная выборка объёма k из множества содержащего n элементов называется сочетанием из n элементов по k элементов. Обозначается через Сnk.

Сnk = n!/(k!(n - k)!)

Попробуйте для проверки своих знаний решить следующие уравнения. Иначе напишите чего непонятно email

 

  1. Сколько различных перестановок можно образовать из букв слова "комбинаторика"
  2. Сколько существует различных пятизначных чисел, сумма цифр которых нечётна.
  3. Хоккейная команда состоит из 2 вратарей, 7 защитников, 10 нападающих. Сколькими способами можно составить стартовую шестёрку, состоящую из одного вратаря, двух защитников и 3 нападающих.
  4. Сколькими способами можно составить список из 28 учеников класса, в котором нет однофамильцев.
  5. Пусть в 11-ом классе изучается 14 предметов. Сколькими способами можно составить расписание на счастливую субботу, если в этот день 5 различных уроков.





Ответы



Вернуться назад