Глухов М. М. Алгебра том 1, страница 7

Докажем формулу (6). Для этого заметим, что, осуществляя всевозможные перестановки элементов в любом сочетании из п по й, мы получим из него й! различных размещений. При этом размещения, получаемые из разных сочетаний, будут различными, и таким образом могут быть получены все размещения из п по й. Следовательно, число размещений из п по й в й! раз больше числа сочетаний из п по й, т.

е. Ай = С„' й!. Подставляя сюда значения Ай из формулы (4), получим формулу (6). П 3 а м е ч а н и е 1. В целях общности и в соответствии с содержательным смыслом числа А~„',Сй определяются также и для й = 0 при любом п, включая п = О, А именно, при п = 0 или й = 0 они считаются равными 1. "Физический" смысл этого соглашения понятен. Существует ровно одно сочетание и одно размещение из элементов пустого множества. Легко видеть, что формулы (4) — (6) остаются в силе и для этих значений п, Й. Числа Сй обладают рядом интересных и широко используемых в математике свойств.

Так, непосредственной проверкой с учетом формулы (б) доказывается С л е д с т в и е. Для любых чисел й,п б Яо, удовлетворяющих условиям Й < п или 1 ( Й ( п, выполняютпся соотпветпстпвенно равенстпва: Т е о р е м а 3. Для любого натпурального числа п и любых чисел а, 6 справедливо равенстпво: + д)п С оп + С1птт — 1Ь+ + ~са~ "6 +...

+ С„6 (9) П Доказательство проведем методом полной математической индукции по числу п. При п = 1 равенство (9) очевидно. Допустим, что оно верно для всех п ( т, где т б 1'!, и докажем его справедливость для и = т+ 1. Используя предположение индукции, получим (а+6)тп~т (а+ 6)(а+ 6) (а+ 6)(~С а + С1 а~-тд+ + ~сд ) Перемножив выражения в правой части последнего равенства и воспользовавшись равенством (8) б) для чисел С„, будем иметь: й + д)тп+1 Со тп+ + (С~ + Со )п~д+ (("'~с + С1 )п~ (~ й + Сй-1)тт +1 йЬй +...

+ (С™ + С ~)ад + С™6 тп+1 Отсюда видно, что формула (9) справедлива и для п = т+ 1. П 3 а м е ч а н и е 2. Формула (9) носит название формулы бинома Ньютона. Она позволяет находить в явном виде все натуральные степени двучлена, или бинома а+ 6. В связи с этим числа С„называют й биномиальными коэффициентпами. С л е д с т в и е 1. Для любого п б Я выполняются соотношения: в) Со+С +...+С'"=2'".

г) Со — С1 + С2 —... + ( — 1)" С„" = О; д) Со+ С'+Сс+... = Сс+С~+Сс+... = 2"-'. П Равенства в), г) получаются из формулы (9) соответственно при а = 1,6 = 1 и а = 1,6 = — 1. Равенство д) следует непосредственно из в), г). П з = (з1,г,~) зг), з' = ~з1,2,г, зг), (1,2,3,...,и) 36 37 Если учесть, что С„есть число й-элементных подмножеств п-элей ментного множества, то из в) получим С л е д с т в и е 2. Число всех подмножеств и-элементного множества равно 2".

~ 3. Перестановки и их классификация Рассмотрим всевозможные перестановки множества 1, и. О п р е д е л е н и е 7. Говорят, что числа г~), г~ в перестановке з = (~1, гг,... г„) образуют инверсию (или беспорядок), если большее из них расположено левее меньшего, т. е. гг > гь и 8 ( Й или г~ > ге и Й ( 8. Число инверсий в заданной перестановке з е Р(1, п) можно найти, например, следующим образом. Сначала найдем, сколько чисел образуют инверсии с единицей, т. е. расположены в з левее единицы, затем— сколько чисел, отличных от 1, образуют инверсии с двойкой, т. е расположены в з левее двойки, и т.

д. Сумма полученных чисел и будет искомым числом инверсий. П р и м е р 1. В перестановке (3, 2, 5, 1, 7, 4, 6) инверсии образуют следующие пары чисел: (3, Ц) (2) Ц) (5, Ц, (3) 2)) (5) 4)) (7) 4)) (7) 6). Следовательно, в ней 7 инверсий. О п р е д е л е н и е 8. Перестановку называют четной, если она содержит четное число инверсий, и нечетной в противном случае. Легко видеть, что при любом и > 1 среди всех перестановок из Р(1, и) имеются как четные, так и нечетные.

Например, перестановка имеет О инверсий и, значит, является четной. Переставив в ней 1 и 2, мы получим перестановку с одной инверсией, то есть нечетную пере- становку. О п р е д е л е н и е 9. Преобразование перестановки, заключающееся в перемене местами каких-либо двух ее элементов, называется транснозицией. Т е о р е м а 4. Если перестановка з' получена из перестановки з с помощью одной транснозиции, то з и з' являются перестановками разной четности. О Рассмотрим два случая. 1.

Элементы г, ~, меняющиеся местами при транспозиции, находятся в перестановке з рядом. Тогда условно перестановки з и з' можно записать в виде: где з1 и зг — перестановки чисел, расположенных в з соответственно левее г и правее у. Пусть (а,6) — любая пара чисел из перестановки з. Если (а,6) ф ф (г,Д, то, очевидно, числа а,6 образуют или не образуют инверсии одновременно как в з, так и в з'. Если же (а,6) = (г, Я, то ясно, что в одной из перестановок з, з' числа а, 6 образуют инверсию, а в другой— нет.

Значит, число инверсий в перестановке з' отличается от числа инверсий в перестановке з ровно на 1 (в ту или другую сторону), и поэтому перестановки з, з' имеют разную четкость. 2. Элементы г,~, меняющиеся местами при транспозиции, не находятся в перестановке з рядом, т. е. В этом случае транспозицию чисел г,~ можно осуществить следующим образом. Сначала г поменяем последовательно местами с г1, гг,... ...,гь, а затем ~ поменяем местами последовательно с г, г~,...,гг,г1. При этом будет произведено 2й+ 1 транспозиций соседних элементов, и по доказанному в случае 1, четность при переходе от з к з' изменится 2Й+ 1 раз. Так как число 2Й+ 1 нечетное, то отсюда и следует, что перестановки з и з' имеют разную четкость. П С л е д с т в и е. Если п > 1, то число четнмх перестановок множества 1, п равно числу нечетнмх перестановок этого множество и равно и!/2.

П Пусть Ао, А1 — соответственно множества всех четных и всех нечетных перестановок из Р(1, и). Зафиксируем различные числа й, 8 б б 1, и и в каждой перестановке з б Р(1, и) поменяем местами элементы, расположенные на й-м и 8-м местах. Этим задается отображение ст: Р(1, и) ~ Р(1, и). Заметим, что ст разные перестановки з и з' переводит в разные. Действительно, если в з и з' на месте с номером т были разные элементы и т ф (й,8) то на т-м месте будут разными элементы и в перестановках ст(з), ст(з').

Если же т = й или т = 8, то в перестановках ст(з), ст(з') разными будут элементы соответственно на 8-м и й-м местах. Следовательно, отображение ст инъективно, и так как (1, и)— конечное множество, то ст биективно. Из теоремы 4 следует, что ст переводит Ао в А1 и А1 в Ао.

Значит !Ао~ ( !А1~, !А1~ ( !Ао~, и поэтому !Ао~ = !А1~ = и!/2. П Введем на множестве Р(1, и) функцию четности 6( ) ( 1)У(з) где 1" (з) — число инверсий в перестановке з. Укажем некоторые свойства функции 6(з). У т в е р ж д е н и е 1. Если (г1,гг,...,г„) — перестпановка мно- жестпва (1, и) и тпаблица А = ! "~ ~~ ' ' ' ~4~! получена из таблицы ~,1 2 ... п~ Г1 2 ... п~ В = ~.. ''' . ) перестановкой столбцов, то ~г1 гг ..

г„) 6О1 12, 1„) = 6(г1,гг,,г„). (10) П С любой таблицей вида: т1 тг ° ° ° тп в которой верхняя и нижняя строки являются перестановками множе- ства Р(1,п), сопоставим число Ь(С) = 6(т1, тг,..., т ) ° 6(~1, Ь,..., ~ ). Пусть таблица т1 тг ' '* получена из С перестановкой двух столбцов. Тогда перестановка (т', т',..., т„') получена из перестановки (т1, тг,..., т„) с помощью одной транспозиции, и поэтому числа У(т1, тг,..., т„), У(т1, тг,..., т„') имеют разную четкость.

По этой же причине числа У(11, 12,..., 1„), У(11~, 1~2,... ...,1'„) также имеют разную четкость. Отсюда следует, что Ь(С) = = Ь(С'). Так как таблицу В можно получить из таблицы А с помощью последовательности транспозиций столбцов то Ь(А) = Ь(В), или 6(~'„12,...,1„) 6(1,2,...,и) = 6(1,2,...,п) 6(г1,гг,...,г„). Отсюда следует равенство (10). П 3 а м е ч а н и е 3. Точно так же, как для перестановок чисел 1,2,...,п, можно определить понятия инверсии, транспозиции, четности и нечетности, функции четности для перестановки из любых попарно различных чисел а1, аг,..., а„.

Ниже при необходимости мы будем без оговорок пользоваться этими понятиями. У т в е р ж д е н и е 2. Если з = (г1,..., г„) б Р(1, п) и к б 1, и, то 6(з) = 6(г1,..., ц,)6(г1,» 1,..., г,„)( — 1)", (и) где т = 1'1 +... + ц — (1 +... + Й). П Из определения функции четности имеем равенство: 6(з) = 6(г1, ...,г1,)6(г1,»1, ..., г„)( — 1)", где т — число инверсий, которые образуют числа из множества М1 —— = (г1, ...,г~), с числами из множества Мг = (г1,+1, ...,г„).