Будем требовать, чтобы решение выражало ("J через числа п, k и стандартные операции; такое понимание решения будет зависеть от выбора стандартных операций. Если считать стандартной операцию Паскаля, то формула F. Другое решение этой задачи — при других стандартных операциях — будет приведено в § 8. Положим в тождестве F. Мы получим объявленное в § 3 равенство C. Пусть I, m, n — целые неотрицательные числа. Если к треугольнику Паскаля и биному Ньютона прибавить еще и формулу Кардано, служащую для нахождения корней кубического уравнения — а, как известно, Дж. Кардано, опубликовавший эту формулу, узнал ее от Тартальи, дав клятву не разглашать, — то следует признать, что посмертная судьба Тартальи была несколько несправедлива к его имени. Подсчитаем коэффициент при х1 в каждой из частей этого равенства. Коэффициент в левой части равен левой части соотношения F. Приравнивая эти коэффициенты, и получаем F. Теорема доказана. Следствие. Важное замечание. В этом параграфе мы неоднократно опирались на следующий основной факт теории многочленов действительной переменной: если два многочлена от переменной х тождественно равны, т. Мы использовали этот факт, когда только что приравнивали коэффициенты при х1 в левой и правой частях тождества F. Более того, на этот факт мы опирались при самом определении биномиальных коэффициентов, предполагая, что разложение F. Чтобы обосновать указанный основной факт, достаточно установить его частный случай, когда один из двух многочленов есть просто О, т. Набранное курсивом утверждение равносильно, в свою очередь, следующей лемме. Пусть многочлен имеет хотя бы один ненулевой коэффициент. Тогда существует такое значение переменной, при котором значение многочлена отлично от нуля. Доказательство леммы. Пусть п — наиболь- шее из таких чисел т, что коэффициент при хт отличен от нуля. В самом деле, в силу F. ЧИСЛО ЧАСТЕЙ ДАННОГО МНОЖЕСТВА Всякая совокупность предметов называется в математике множеством. В первом случае рассматриваемый предмет называется элементом рассматриваемого множества. Например, число 3 является элементом множества всех целых чисел и не является элементом множества всех четных чисел. Может случиться, что все элементы некоторого множества Л являются одновременно элементами некоторого другого множества В (так, например, все элементы множества всех четных чисел являются элементами множества всех целых чисел). В таком случае множество А называют частью, или подмножеством, множества В. Очевидно, каждое множество является частью самого себя. Если множество А является частью множества В и множество В является частью множества А, то это значит, что А я В состоят из одних и тех же элементов, т. Конечные множества (а только такими множествами мы будем заниматься в этом параграфе) составляют предмет изучения специальной математической дисциплины — комбинаторики. Среди конечных множеств выделяется одно особое множество, а именно — множество, не содержащее никаких элементов; такое множество называется пустым. Так, не исключена возможность, что, открыв коробку, мы обнаружим, что множество заключенных в ней карандашей пусто. Вот что пишет о пустом множестве П. Александров '): «Пустое множество, по определению, не содержит элементов; число элементов пустого множества есть нуль. Необходимость рассмотрения пустого множества видна из того, что когда мы определяем тем или иным способом множество, то мы можем и не знать заранее, ') Александров П. Введение в теорию множеств и об* щую топологию. Например, ве« роятно, множество страусов, находящихся в данный момент за Полярным кругом, пусто; однако мы не можем этого утверждать с уверенностью, так как, может быть, какой-нибудь капитан и завез какого-нибудь страуса за Полярный круг». Пустое множество считается частью всякого множества. Если множество конечно, то его элементы можно пересчитать, найдя тем самым число элементов множества. Множество, состоящее из п элементов, называется «n-элементным». Множество страниц этой брошюры является, например, 48-элементным множеством, пустое множество является нульэлементным множеством. Рассмотрим множество, состоящее из трех предметов: карандаша, пера и ластика. Найдем все его части. Имеется ровно одна нульэлементная часть — пустое множество. Наконец, имеется ровно одна трехэлементная часть (совпадающая со всем множеством): Всего, таким образом, наше множество имеет восемь частей. Пусть дано множество, состоящее из п элементов. Любая ft-элементная его часть называется сочетанием из заданных п элементов по к. Очевидно, что число сочетаний из заданных п элементов по k не зависит от того, какие именно п элементов заданы, а только от чисел п и k. Поэтому это число называют короче числом сочетаний из п элементов по k и обозначают Иначе говоря, С* — это число /г-элементных частей n-элементного множества. Впрочем, естественно считать, что выражение С\ имеет смысл и при k n и равно в этом случае нулю (так как в этом случае /г-элементных частей нет вовсе). Доказательство. Установим теперь, не вычисляя самих чисел С\, еще три свойства этих чисел. Установление второго и четвертого свойств явится полезным упражнением на усвоение понятий, изложенных в этом параграфе; что же касается третьего свойства, то именно оно — вместе с первым — и ляжет в основу вычисления чисел С«. Второе свойство числа сочетаний: Т\ С ft п — Доказательство. Возьмем какое-нибудь множество М из п элементов. Осуществим мысленно следующую конструкцию. Вырежем из бумаги столько квадратов, a b с d e Пустое множества b e d а с Рис. С„), и на каждом из них изобразим одну из этих частей — так чтобы каждая ^-элементная часть была изображена на каком-то квадрате. Далее, вырежем из бумаги Сп~к кругов и каждую из (п — k) -элементных частей изобразим ровно на одном из этих кругов. Нам теперь достаточно обнаружить, что кругов и квадратов одинаковое количество. Для этого мы выложим все квадраты на стол и на каждый из них положим круг по следующему правилу: если на квадрате изображена некоторая часть множества М, составленная из k элементов, то на этот квадрат должен быть положен круг с изображением части множества М, составленной из остальных п — k элементов, т, е.