МЕНЮ
Учень! Що для тебе (як для школяра) означає школа?





  • ▲  угору сторінки
  • ◄  на попередню сторінку
головна сторінка > Теорія > Алгебра > 11 класс > § 6

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

МНОЖЕСТВО
Множество — одно из основных понятий математики, которое не подлежит формальному определению.
В математике понятие множество используется для описания совокупности предметов или объектов. При этом предполагается, что предметы (объекты) данной совокупности можно отличить друг от друга и от предметов, которые не входят в эту совокупность. Например, можно говорить о множестве всех книг данной библиотеки, множестве всех вершин данного многоугольника, множестве всех натуральных чисел, множестве всех точек данной прямой. Книги данной библиотеки, вершины данного многоугольника, натуральные числа, точки данной прямой являются элементами соответствующих множеств.

Множества обычно обозначаются большими буквами A, B, X... Тот факт, что объект a является элементом множества A, записывается так: a ∈ A и читается «a принадлежит множеству A», «a входит в множество A». Запись a ∉ A означает, что a не является элементом множества A.

Множество натуральных чисел, расположенных между числами 21 и 22, не содержит ни единого числа. Такое множество называется пустым множеством. Пустое множество обозначается знаком ∅.

Множества A и B называются равными, если они складываются из одних и тех же элементов. В этом случае пишут A = B.

В школьном курсе математики приняты стандартные обозначения числовых множеств:
N — множество натуральных чисел,
Z — множество целых чисел,
Q — множество рациональных чисел,
R — множество действительных чисел.

Подмножество
Если любой элемент множества A принадлежит также множеству B, то множество A называется подмножеством множества B. Это записывают так: A ⊂ B или B ⊃ A.

В этом случае говорят, что множество A содержится в множестве B или множество B содержит множество A. Если в множестве A найдется хотя бы один элемент, не принадлежащий множеству B, то A не является подмножеством множества B: A ⊄ B.

Из определения подмножества следует, что любое множество является подмножеством самого себя, то есть справедливо A ⊂ A.

Пересечение множеств
Множество, состоящее из всех элементов, принадлежащих и множеству A и множеству B называется пересечением множеств A и B и обозначается A ∩ B.
Объединение множеств
Множество, состоящее из всех элементов, принадлежащих или множеству A, или множеству B, называется объединением множеств A и B и обозначается A ∪ B.

Для конечного множества A через m(A) обозначим число его элементов. Число элементов пустого множества, очевидно, равно нулю. Для любых конечных множеств A и B справедливо равенство: m (A ∪ B) = m(A) + m(B) − m (A ∩ B) (1)

РАЗМЕЩЕНИЯ
Пусть имеется множество, содержащее n-элементов. Каждое его упорядоченное подмножество, состоящее из k-элементов, называется размещением из n-элементов по k-элементов.
В комбинаторных задачах необходимо уметь подсчитать число всех размещений из n-элементов по k-элементов. Для обозначения этого числа применяется специальный символ (читается: «число размещений из n по k» или «A из n по k». = 1.

A — первая буква французского слова «arrangement», что означает «размещение, приведение в порядок».

В общем случае на вопрос о числе размещений из n-элементов по k-элементов дает ответ такая формула:
(1) = n (n − 1) (n − 2) ... (n − k + 1), k > 0,
то есть число размещений из n-элементов по k-элементов равно произведению k последовательных натуральных чисел от n до n − k + 1 включительно.
Формулу (1) удобно записывать в другом виде. Будем для краткости произведение n (n − 1) (n − 2) ... 3 × 2 × 1, то есть произведение всех натуральных чисел от n до единицы, обозначать символом n! (читается «эн факториал»).

Умножим и разделим произведение, стоящее в правой части формулы (1) на (n − k)!. Тогда получим:

= или (2) = = 1, = = 1, если условиться, что 0! = 1.

ПЕРЕСТАНОВКИ
Размещения из n-элементов по n-элементов называются перестановками из n-элементов.

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

Число перестановок из n-элементов обозначают через Pn. P — первая буква французского слова «permutation» — «перестановка».

В общем случае число перестановок из n-элементов Pn = , следовательно, его можно найти по формуле (1) или по формуле (2), предположив в каждой из них k = n.

Действительно, формула (2) дает:

Pn = = = = n!

Из формулы (1) находим:

Pn = = n (n − 1) (n − 2) ... (n − n + 1) = n!

Итак, число перестановок из n-элементов равно n!.

Таким образом, в множестве, содержащем n-элементов, установить определенный порядок последовательности элементов или, как говорят, упорядочить такое множество можно n! способами.
СОЧЕТАНИЯ
Пусть имеется множество, состоящее из n-элементов. Каждое его подмножество, содержащее k-элементов, называется сочетанием из n-элементов по k-элементов. Число всех сочетаний из n-элементов по k-элементов обозначается символом (читается: «число сочетаний из n по k» или «цэ из n по k».

C — первая буква французского слова «combinasion» — «сочетание».

В общем случае число сочетаний из n-элементов определяется следующей формулой:

= (3).

Формулу (3) можно записать в другом, более удобном для вычислений виде. Сократив числитель и знаменатель дроби на (n − k)!, получим = (4), т.е. число сочетаний из n-элементов по k-элементов равно произведению всех натуральных чисел от n до n − k + 1 включительно, деленному на k!.

КОМБИНАТОРНЫЕ ЗАДАЧИ
Решая сложные комбинаторные задачи, часто приходится пользоваться следующими двумя правилами.

1. Если некоторый выбор можно выполнить m разными способами, а для каждого из этих способов некоторый выбор можно выполнить n разными способами, то число способов для выполнения последовательности этих выборов равно произведению mn.

2. Если некоторый выбор можно выполнить m разными способами, а другой выбор n разными способами (отличными от предыдущих), то общее число способов, которыми можно выполнить любой из этих выборов, равен сумме m + n.

Основные правила комбинаторики
Правило суммы
Если объект A может быть выбран m способами, а объект B может быть выбран другими n способами, то выбор одного элемента — или A, или B — может быть осуществлен m + n способами.
Правило произведения
Если объект A может быть выбран m способами и после каждого такого выбора объект B может быть выбран n способами, то выбор пары объектов A и B в указанном порядке может быть осуществлен mn способами.
! Эти правила могут быть распространены на случай выбора из трех и более множеств.

Дивіться також:

  • Непрерывность функции
  • Интегралы
  • Комплексные числа и действия с ними
  • Производная функции
  • Случайная величина. Ожидание. Дисперсия
  • Модуль числа
  • Якщо Ви помітили помилку, виділіть необхідний текст та натисніть Ctrl+Enter

    © 2008-2024. Офіційний сайт Бердянської ЗОШ І-ІІІ ступенів № 2 Запорізької області

     
    [
    ]