1.1    Перестановки, сочетания, полиномиальная теорема

Рассмотрим конечное множество М = {а\,... ,ап}, содержащее п эле­ментов. Сочетание - подмножество М, т.е. некоторая неупорядоченная выборка различных элементов из М. Обозначим через С\ (или через (^)) число всех сочетаний, содержащих к элементов. Другими словами, С* -число всех ^-элементных подмножеств п-элементного множества М.

Утверждение 1. Г//;' =

Доказательство проведем индукцией по числу п > к.

Если п = к, то С| = 1 = ^|у. Предположим истинность нашей формулы для п-элементных множеств. Докажем ее справедливость для множества А = {а|...., ап, а,,-\}. содержащего (// +1) элементов. Каждое А*-элементноеподмножество А либо содержит ап+1, либо не содержит ап+\. Число под­множеств первого типа равно О*'-1, тж. каждое такое подмножество одно­значно определяется сочетанием из [к — 1) элемента в {а\,..., ап}. Число подмножеств второго типа равно, очевидно, С\. Следовательно, С*+1 =

ГУк  I _      та!       ,__та! _ та!        г!   ,       1    ] _     (п+1)! П^п_

°та 1" — *!(п-А:)! ^ (й-1)!(п-ДЛ-1)! ~~ (*-1)!(п-*)! 1* ^ п-к+11 ~~ *!(п+1-*)!'

значим, далее, через Рп число всех упорядоченных гг-ок ..., щп); щ.. £ М,щв ф а^} множества М. Такие гг-ки мы будем называть перестановка­ми. Докажем, что Р„ = п\. Воспользуемся методом математической ин­дукции. Если п = 1, то Р\ = 1 = 1!. Предположим истинность искомого равенства для гг-элементных множеств и докажем его справедливость для (п + 1)-э.цементного множества А = {а\,... ,ап+1}. Множество всех пере­становок элементов А можно разбить на (п + 1) непересекающихся классов С\,... ,Сп+\. Именно, отнесем в класс С{ те (и только те) перестановки, которые содержат ап+\ на /-м месте

Ясно, что \С{\ = п\ и Рп+1 = \С\ \ + |Сг| Н-----1- |Сп+1| = (п + 1) • п\ = (п + 1)!.

Обозначим через Р^ число всех упорядоченных выборок, содержащих г различных элементов множества М (иногда это число обозначается как Р(п,г),Агп или пРг). Число всех г-элементных подмножеств М равно С'п и каждое такое подмножество порождает г! упорядоченных искомых вы­борок, т.е. /''' = С'и - г! = ^2гу_ • Подсчитаем число всех упорядоченных г-множеств {(аг,..., аг); щ £ М}. Каждая координата (независимо) пробе­гает все множество М. Поэтому число всех таких г-выборок равно пг.

Замечание. Из предыдущего следует, что число всех подмножеств //-множества (т.е. п-элементного множества) равно (С^ + С^Н-----Ь С). Не­упорядоченная совокупность из г элементов {а\, аг, ■ ■ ■, аг} множества М (не обязательно различных) называется г-выборкой из М. Две г-выборки равны, если каждый элемент входит в обе выборки одинаковое число раз. г-выборка, содержащая каждый элемент один раз является /--подмножествомили г-сочетанием.

Утверждение 2. Число г-выборок из п-множества равно C^+r_v ДОКАЗАТЕЛЬСТВО.

Пусть М = {1, 2,..., п} и М* = {1, 2,..., п, п + 1,..., п + г - 1}. Соответ­ствие {ai, Д2, • • • • flr} ^—> {а 1+0. a-2+1 • • • •, ar+(r—1)}, где а\ < а-> < ■ ■ ■ < а,--

является биективным соответствием между множеством всех

r-выборок из М и r-сочетаний из М*. По утверждению 1, искомое число

равно С,'tl_j._ | •

Подсчитаем число различных перестановок символов

а>1 ■ -j 1 o>ji b,. .j , 6,..., с,. ^., с ,

где ^    = гг. Число всех перестановок символов

г=1

$ъ • • • 1 aai, b\,..., 6a2,..., С\,..., cak

равно п\. Отождествляя а\ = • • • = aai = а, мы уменьшаем это число в о>\\ раз; отождествляя, далее, Ъ\ = • • • = Ъа2 = 6, мы уменьшаем предыдущее число еще в «г! раз и т.д. Поэтому искомым числом будет

Рп(аь...,ак) =

а\\а2\... а*!

Утверждение 3 (полиномиальная теорема). Справедливо следующее равенство многочленов

- :Ж11Ж22 • • • Хик.

щ!. .. аь\

«Н-----Ьак=п

ДОКАЗАТЕЛЬСТВО. Рассмотрим левую часть равенства х\-\-----1- хи)п = {х\ Н-----\- хи) ■ ■ ■ (х\ Н-----\- х^

п

= А(а1,...,ак)х?---х%",

aiH-----Vau=nгде коэффициент А(а\}..., о&) равен числу всех таких наборов

(п |..... п/,). что о | Н-----Ь п/, = г/. Подсчитаем это число. Переменную х\

можно выбрать в а\ множителях (из п возможных!), т.е. С"1 способами.

Переменную Х2 можно (независимо) выбрать в 02 в оставшихся (71 — 0:1)

множителях и т.д. Таким образом,

Л(оь ..., ак) = С*1 ■ С%1а1      С^Ч{а1+...+ак_1} =

_       та!       _      (71-0:1)!      _ _ _ _ (та^(аН-----\-ак-1))\ _ та!

та

В частности, (х\ + ж-))" = *£2 ^,х\х2^к ~ классическая формула бинома Ньютона.

ЗАДАЧИ

1) . Число всех подмножеств тг-множества равно 2п. УКАЗАНИЕ. Воспользоваться равенством

та

(1 + 1)" = £с*

к=0

2) . Доказать, что

Ста + Ста + Ста + ' ' ' =       +       +       + ' ' ' •

УКАЗАНИЕ. Рассмотреть бином (1 - 1)" = 0.

таг

3) . Доказать равенство С'/.'1.. = ^ СггС™~%'. УКАЗАНИЕ 1. Рассмотреть тождество

(1 + ж)г(1 + ж)* = (1 + ж)г+*.

УКАЗАНИЕ 2. Рассмотреть число способов выбора комиссии из т че­ловек в группе, состоящей из г женщин и в мужчин.

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

ОТВЕТ: З5.

5) . Сколько различных семизначных чисел можно составить из цифр

2,2,3,3,3,0,4?

ОТВЕТ: 2Ш - 2§т = 360.

6) . В оранжерее имеются цвета 10 наименований. Сколькими способами можно составить букет из 20 цветов?

ОТВЕТ: С$+20-1 = 10015005.

7) . Из группы, состоящей из 7 мужщин и 4 женщин, надо выбрать

6 человек так, чтобы среди них было не менее 2-х женщин. Сколькими способами это можно сделать?

ОТВЕТ: С\ ■ С] + С| • С| + С\ ■ С= = 371.

8) . Найти число всех натуральных делителей числа п = р"1 где р\,..., р8 - различные простые числа.

ОТВЕТ: («1 + 1) • • • (а8 + Г

9). Доказать, что ^ С* • к = 2 п—1

П.

к=1

УКАЗАНИЕ. Рассмотреть /(;/;) = (1 + •''.')" и ее производную $'{х

10). Доказать равенство

4 • ^ сп = 2П + 21+1

к

УКАЗАНИЕ. Рассмотреть равенство

7ТП

сов—. 4

■2\п  ,  (Л _|_ лте _|_ Ц _|_ _ л   \ П^к

11). Из колоды, содержащей 52 карты, вынули 10 карт. В скольких случаях среди этих карт окажется:

а) хотя бы один туз;

б) ровно один туз;

в) не менее 2-х тузов;

г) ровно 2 туза. ОТВЕТ:

а) С\ ■ С|8 + С\ ■ С|8 + С\ С|8 + С\ ■ С|8;    б) С\ ■ С|8 и т.д.