Соединения

Группы, составленные из каких-либо элементов, называются соединениями. Различают три основных вида соединений: размещения, перестановки, сочетания.

Если из множества предметов выбирается некоторое подмножество, то его называют выборкой. Выборки бывают упорядоченные и неупорядоченные.

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

Пример. Из цифр 1, 2, 3, 4, 5 можно составить следующие трехзначные числа 123, 431, 524,...и т.д. Это упорядоченные трехэлементные выборки, так как 123 и 132 - разные числа.

Пример. Из 20 учащихся класса выбрать двух дежурных. Любая пара дежурных представляет собой неупорядоченную двухэлементную выборку, так как порядок их выбора не важен.

Определение. Размещениями из n элементов по m элементов (m < n) называются комбинации, составленные из данных n элементов по m элементов, которые отличаются либо самими элементами, либо порядком элементов.

Число размещений без повторений из n по m (n различных элементов) вычисляется по формуле:

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

Число размещений с повторениями вычисляется по формуле:

Пример. Возьмем буквы Б, А, Р. Какие размещения из этих букв, взятых по две, можно получить? Сколько таких наборов получиться, если: 1) буквы в наборе не повторяются; 2) буквы могут повторяться?

Решение.

1. Получатся следующие наборы: БА, БР, АР, АБ, РБ, РА.

По формуле числа размещений без повторений получаем:

наборов.

2. Получатся наборы: ББ, БА, БР, АА, АБ, АР, РР, РБ, РА.

По формуле числа размещений с повторениями получаем: наборов.

Пример. Вдоль дороги стоят 6 светофоров. Сколько может быть различных комбинаций их сигналов, если каждый светофор имеет 3 состояния: "красный", "желтый", "зеленый"?

Решение. Выпишем несколько комбинаций: КККЖЗЗ, ЗЗЗЗЗЗ, КЖЗКЖЗ... Мы видим, что состав выборки меняется и порядок элементов существенен (ведь если, например, в выборке КЖЗКЖЗ поменять местами К и Ж, ситуация на дороге будет другой). Поэтому применяем формулу размещений с повторениями и вычисляем число размещений с повторениями из 3 по 6, получаем комбинаций.

Определение. Перестановками из n элементов называются размещения из этих n элементов по n (Перестановки - частный случай размещений).

Число перестановок без повторений (n различных элементов) вычисляется по формуле:

Число перестановок c повторениями (k различных элементов, где элементы могут повторяться m₁, m₂, …, m_k раз и m₁ + m₂ +… + m_k = n, где n - общее количество элементов) вычисляется по формуле:

Пример. Возьмем буквы Б, А, Р. Какие перестановки из этих букв можно получить? Сколько таких наборов получится, если: 1) буквы в наборе не повторяются; 2) буква А повторяется два раза?

Решение.

1) Получатся наборы: БАР, БРА, АРБ, АБР, РАБ, РБА.

По формуле числа перестановок без повторений получаем: наборов.

2) Получатся наборы: БАРА, БРАА, БААР, ААРБ, ААБР, АБАР, АРАБ, АРБА, АБРА, РАБА, РААБ, РБАА.

По формуле числа перестановок с повторениями получаем: наборов.

Пример. Сколько шестизначных чисел можно составить из цифр 0, 1, 2, 3, 4, 5 так, чтобы цифры в числе не повторялись?

Решение. Из данных шести цифр можно составить Р₆ = 6! = 720 перестановок. Но числа, начинающиеся на нуль, не являются шестизначными. Такие числа отличаются друг от друга перестановкой пяти остальных цифр, значит, их будет Р₅ = 120. Поэтому шестизначных чисел будет 720 - 120 = 600 чисел.

Пример. Сколькими способами можно расставить белые фигуры (2 ладьи, 2 коня, 2 слона, ферзь и король) на первой линии шахматной доски?

Решение. Первая линия шахматной доски представляет собой 8 клеток, на которых и надо расположить эти 8 фигур. Различные варианты расположения будут отличаться только порядком фигур, значит, это будут перестановки с повторениями Р₈ (2,2,2).

По формуле (3.4) получаем: способов.

Определение. Сочетаниями из n элементов по m элементов называются комбинации, составленные из данных n элементов по m элементов, которые различаются хотя бы одним элементом (отличие сочетаний от размещений в том, что в сочетаниях не учитывается порядок элементов).

Число сочетаний без повторений (n различных элементов, взятых по m) вычисляется по формуле:

Свойства сочетаний:

Число сочетаний c повторениями (n элементов, взятых по m, где элементы в наборе могут повторяться) вычисляется по формуле:

Пример. Возьмем буквы Б, А, Р. Какие сочетания из этих букв, взятых по две, можно получить? Сколько таких наборов получится, если: 1) буквы в наборе не повторяются; 2) можно брать по две одинаковые буквы.

Решение.

1. Получатся наборы: БА (БА и АБ - один и тот же набор), АР и РБ

По формуле числа сочетаний без повторений получаем:

набора.

2. Получатся наборы: ББ, БА, БР, АА, АР, РР.

По формуле числа сочетаний с повторениями получаем:

наборов.

Пример. Из 20 учащихся надо выбрать двух дежурных. Сколькими способами это можно сделать?

Решение. Надо выбрать двух человек из 20. Ясно, что от порядка выбора ничего не зависит, то есть Иванов-Петров или Петров-Иванов - это одна и та же пара дежурных. Следовательно, это будут сочетания из 20 по 2.

По формуле числа сочетаний без повторений получаем: способов.

Пример. В хлебном отделе имеются булки белого и черного хлеба. Сколькими способами можно купить 6 булок хлеба?

Решение. Обозначая булки белого и черного хлеба буквами Б и Ч, составим несколько выборок: ББББББ, ББЧЧББ, ЧЧЧЧЧБ,... Состав меняется от выборки к выборке, порядок элементов несущественен, значит это - сочетания с повторениями из 2 по 6. По формуле числа сочетаний с повторениями получаем способов.

Сделаем проверку и выпишем все варианты покупки: ББББББ, БББББЧ, ББББЧЧ, БББЧЧЧ, ББЧЧЧЧ, БЧЧЧЧЧ, ЧЧЧЧЧЧ. Их действительно 7.