§ 2. Перестановки

ЧАСТЬ II. ГЛАВА 8
СОЕДИНЕНИЯ И БИНОМ НЬЮТОНА

На главную страницу Алгебра. Д.К. Фаддев, И.С. Соминский.
Скачать оригинал Алгебра. Д.К. Фадеев, И.С. Соминский на странице Сборники Математики.
Ниже можете посмотреть тексты для быстрого ознакомления (формулы отображаются не корректно).

Похожие статьи: Алгебра в школе. ВЕКТОРЫ. Библиотека учителя. Школьная математика.

Перестановки

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

414 СОЕДИНЕНИЯ И БИНОМ НЬЮТОНА. Перестановки.  Кабинет Математики.

Опр е д е л ение . Расположенная совокупность т элементов называется
перестановкой из т элементов.
Число всевозможных различных перестановок из т элементов
обозначается знаком Рт. По определению,
Pm — AZ = m (tn— 1)(/я — 2) . .. 2 • 1.
Произведение 1 *2 . . . /я первых т натуральных чисел обозначается
ml (читается: т факториал). Таким образом, Рт = т\
Пример. Сколько четырехзначных чисел можно записать при
помощи цифр Л, 2, 3, 4, если каждая цифра дходит в изображение
числа только один раз?
Решение. Искомое число равно числу всевозможных перестановок
из четырех элементов
/>4 = 4 . 3 — 2 * 1 = 24.

§ 3. Сочетания

Опр е д е л ение . Сочетанием из т элементов по k называется
совокупность, образованная любыми k элементами из данных т. Два
сочетания из т элементов по k считаются различными тогда й только
тогда, когда они отличаются по крайней мере одним элементом.,
В отличие от размещений, где. существенное значение имеет, порядок,
в котором расположены элементы, в сочетаниях порядок расположения
элементов не имеет значения.
Число всевозможных сочетаний из т элементов по k обозначается
знаком Cm-
Теорема . Число всевозможных сочетаний из т элементов
по k может быть вычислено по формуле
г,k т (т — 1 )…(/н — k + 1)
Ст — Т Т 2 ~ Ъ •
Д о к а з а т е л ь с т в о . Предположим, что мы составили таблицу
всех сочетаний из m элементов по k. Назовем ее-таблицей 1. Возьмем
каждое из сочетаний таблицы 1 и всеми возможными способами
переставим в нем элементы. Получим всего PkCm размещений,
которые и запишем в таблицу 2. Покажем, что в таблице 2 содержатся
все размещения из m элементов по k и при этом ни одно
размещение не содержится дважды.
Пусть А — произвольное размещение из m элементов по k. Если
не обращать внимания на порядок расположения элементов, то А
представляет собой некоторое сочетание С из m элементов по k.
Так как в. таблице 1 содержатся все сочетания из m элементов
по k, в ней содержится-и это сочетание С. В сочетании С мы переставляли
элементы всеми возможными способами* Следовательно,
размещение А содержится в таблице 2.

415 СОЕДИНЕНИЯ И БИНОМ НЬЮТОНА. Перестановки.  Кабинет Математики.

Возьмем теперь два каких-нибудь размещения из таблицы 2.
Если они получены из разных сочетаний, то они отличаются друг,
от друга элементами. Если они происходят от одного сочетания, они
отличаются порядком расположения элементов. В обоих случаях эти
размещения различны.
Отсюда вытекает, что
Ат — Рк ‘С кт
т. е.
rM ___ Ат а т (т — 1 ) … (т — k — f 1)
т ~ Pk ‘ 1 — 2 . . . *
Формула для Cm может быть преобразована. Умножим числитель
и знаменатель на (т — k)\ Получим
Q k т\
т k \(m — k)l •
Пример. В классе 30 учащихся. Сколькими способами можно
назначить двух дежурных из них?
Решение . Искомое число равно числу сочетаний из 30 элементов
по 2.
Сл* | )__=30 • 20 iop* т 7Т = 435.
Ответ. 435.
Теор е м а . Ckm = Cm
Д о к а з а т е л ь с т в о .
г ь т (т — 1 } … (т —- k + 1 )
я*- 1 • 2 .. . k 9
Cm — k _
, ™ — 1 — 2 . ..(да — k)
Разделим почленно
Cm [т(т— 1). ..(/я — k + 1)] [(т—k ) . . .2- 1] т\ __-
[ 1 — 2 . . . *][<*+! ) . . . (да-1)да] “ да! “ u
Эту теорему можно доказать и иначе.
Выбирая какие-нибудь k элементов из данных ту мы составляем
некоторое сочетание из т элементов по k. Остальные т — k элементов
образуют сочетание из т элементов по т — k.
Таким образом, каждому сочетанию из т элементов по k соответствует
одно сочетание из т элементов по т — k и наоборот.
Значит число сочетаний из т элементов по k равно числу сочетаний
из т элементов по т — k.
Пример. Сюо = С!оо.
Упражнения
/71! 1. Пользуясь формулой С ^ = jfcj щ , показать, что =
2. Нужно распределить преподавание в шести классах между тремя преподавателями.
Сколькими способами можно производить это распределение,
если каждый должен получить два класса?

416 СОЕДИНЕНИЯ И БИНОМ НЬЮТОНА. Перестановки.  Кабинет Математики.

Околоadmin