СОЕДИНЕНИЯ И БИНОМ НЬЮТОНА

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

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

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

СОЕДИНЕНИЯ И БИНОМ НЬЮТОНА

§ 1. Размещения

Имеется т элементов (т. е. предметов* букв, цифр, чисел и т, д.).
Выберем из них какие-нибудь k элементов ( k ^ m ) и расположим
эти k элементов в каком-нибудь порядке, т. е. так, чтобы было известно,
какой элемент находится на первом месте, какой — на втором
и т. д.
Оп р е д е л ен и е . Расположенная совокупность k элементов, взятых
из данных т элементов, называется размещением из т элементов
по k.
По определению, два размещения из т элементов по k являются
различными, если они отличаются или самими элементами, или порядком
их расположения.
Число всевозможных размещений из т элементов по k обозначается
знаком где т показывает число всех элементов, a k —
число элементов, входящих в каждое размещение. Задача состоит
в отыскании общей формулы для подсчета Акт• Решение задачи разобьем
на две части. В первой части рассмотрим несколько частных
случаев с тем, чтобы на основе их построить гипотезу для общего
случая. Во второй части проверим гипотезу методом математической
индукции.
Случай 1. А=1 . Пусть т — Ъ, т. е. имеется 5 элементов: аь
а<ь а*, я4, аъ. В каждое размещение по одному элементу входит либо
аи либо аъ либо а3, либо а4, либо аъ. Таким образом, А\ = 5. Очевидно,
что и при всяком т
Ат — т.
Случай 2. £ = 2. Пусть т = 4, т. е.имеется 4 элемента: аь аъ я3,
а4. Для того чтобы составить все размещения из этих элементов по
2, выпишем сначала все размещения по 2, у которых на первом месте
находится элемент ах. Получим строку
U\t Ux, Ufa
содержащую три размещения. Выпишем теперь все размещения по 2,
у которых на первом месте находится элемент а2. Получим строку
#2, ах\ #4,

412 СОЕДИНЕНИЯ И БИНОМ НЬЮТОНА. Кабинет Математики.

содержащую еще три размещения. Далее имеем строку
О-Ь а й a ‘ii a i\ й8, а 4
и, наконец, строку
?4, Яд, Яз-
Всего имеем 4 строки, в каждой из которых содержится три размещения
из 4 элементов по 2. Таким образом,
А1 — 4- 3.
Если бы т = 10, то, поступая таким же образом, мы получили
бы 10 строк, в каждой из которых содержалось бы по 9 размещений
из 10 элементов по 2:
Яц аи аз> аь ai> ai> as> аь ай\
Яд» Я17, Яд, Я§, аь Ад, Яд, Ajg
и т. д. Таким образом,
Л ? о = 1 0 .9 .
Все это наводит на гипотезу, что при всяком т.
Ат = т (т— 1).
Рассматривая, если потребуется, еще и другие примеры, можно
заметить, что Ат равно произведению к последовательных целых чисел,
наибольшее из которых т, т. е. при любом т. и при любом k
(конечно, k ^ t r i )
Акт — т(пг— \ ) (т — 2)… [т — (k — 1)]. (1)
Рассуждения, которые были проведены, не являются доказательством
того, что формула (1) верна. Эти рассуждения дали лишь возможность
построить гипотезу. Нужно еще доказать, что гипотеза
эта верна.
Те о р ема . Число размещений из гп элементов по k может,
быть вычислено по формуле
K i — m{m — 1)(т — 2 )… (от — k — \ — 1).
Д о к а з а т е л ь с т в о . Доказательство проводится методом математической
индукции, причем индукция ведется по к.
При k = 1 утверждение справедливо, так как непосредственно
видно, что А1т = т и по формуле (1) А т ~ т.
Допустим, что утверждение справедливо при k = n, где п< ^т ,т. е.
Ат — т {т— 1 ){т — 2 )… (т— я — f- 1).
Докажем, что тогда утверждение должно быть справедливым и при
k = n — \ — 1, т. е.
х = т {т— 1 ) , , . (яг— я -]- 1 ){т — я).

413 СОЕДИНЕНИЯ И БИНОМ НЬЮТОНА. Кабинет Математики.

Для получения размещений из т элементов по д -{ -1 возьмем
все размещения из т элементов по д и к каждому из них на (д + 1)-е
место припишем каждый из остальных т — д элементов. Таким путем
получим (т — п)Ат размещений.
Если мы теперь докажем, что ни одно размещение из т элементов
по д -f-l нами не пропущено и ни одно из этих размещений
не выписано дважды, теорема будет доказана.
Возьмем произвольное размещение А из т элементов по п — \ — 1.
Пусть в размещении А на (д-{ -1)-м месте находится эЛемент Отбросим
этот элемент, получим размещение из т элементов по д.
Так как мы брали все размещения из т элементов по д, взято и
размещение Av К этому размещению на (д + 1)-е место мы приписывали
каждый из остальных элементов, значит, приписали и эле^
мент as. Выходит, что ни одно размещение из т элементов по д -{-1
нами не пропущено. . 4
Допустим теперь, что размещение Л из т элементов по д -f-l
нами получено дважды. Вычеркнем в каждом из этих размещений
элемент, находящийся на последнем месте. Подучим одно и же,
размещение Ах из т элементов по д. Выходит, что к одному и тому
же размещению Ах два раза в конце был приписан один и тот же
элемент. Это противоречит способу, посредством которого составляв
лись размещения из /д элементов по д — { — Ь
Итак,
Л»+1 = ( / я — и )Л “ ,
НО
А% = т (т— 1)… (т— д -f-l).
Значит,. ,
Ат* 1 — т (т — 1). . . {т — д -j- 1)(/д — д).
Утверждение справедливо при & = 1, и из справедливости его
при k — n следует его справедливость при Л = д -f-l.
Теорема доказана.
Пример . Л?2= 12* 11 • 10 = 1320.
Пример . Сколько различных двузначных чисел можно записать
при помощи цифр 1, 2, 3 и 4, если ни одна цифра не входит
в изображение числа дважды?
Решение. Искомое число равно А\ = 4 • 3 = 12.

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

Околоadmin