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

Элементы комбинаторики Введем обозначение; 1 • 2 • 3•• п = /!((читается «п-факториал»). Из определения ясно; п! = (я-1)!-и. Например, 5!=Ь2-3'4-5 = 4!-5. Очевидно, величина О! не определена, однако во многих формулах обще­ го вида эта величина встречается и значение ей удобно придавать, равное еди­ нице, т.е. 0!=1. Мы также примем это соглашение, которое нас не будет приво­ дить к неверным результатам. Пусть даны два множества A=:{ai, Ог,--, а„} и B = {bi, bi,..., b „]. Биек- цию, отображающую А на В, назовем перестановкой, а число всех возможных перестановок обозначим р„. Содержательный смысл: если а,, Й2,..., я,, - различные шары (занумеро­ ванные шары), а Ьи bi,..., b „ - лунки, то р„ - число способов, которыми шары можно расположить в лунках, помещая в каждую лунку лишь один шар. Докажем, что р„=п\. Сделаем это с помощью математической индукции. Очевидно, р, =1 = 1! Полагая р„=п1 доказанным, добавим еще один шар и одну лунку. Ясно, что имеет п + 1 вариант попадания в лунку и на каждый из этих вариантов приходится р„ вариантов для остальных шаров, следовательно, Рп+1 •(" + !) = (" + !)!, что и требовалось. В качестве упражнения проведите это доказательство на языке отобралсений. Пусть теперь А=^ {oi, ai,а,,,}, В = {bi, Ьг, •••, Ь„] чт<п. Инъекцию т А ь В назовем размещением, а число всех возможных раз­ мещений обозначим А"„'. Содержательный смысл; если а|, ai,..., а„, - занумерованные (различи­ мые) шары, а bi, bi,..., b „ - лунки, то А^' - это число способов, которыми эти шары можно расположить в лунках, помещая в лунку лишь один шар. При этом, если поменять в каком-либо варианте местами любые два шара, получим новый вариант. Докажем, что а: =п{п-\)(п-2)...{п-{т~\)). (2.2) Доказательство проведем с ПОМОЩЬКА индукции по переменной т. Оче­ видно а !, = ;i = и - (1-1). 21