Искусство философствования   ::   Рассел Бертран

Правило таково: умножь число рассматриваемых целых чисел на число, которое больше его на единицу, полученный результат подели пополам, а полученное число возведи в квадрат. Вы легко сможете убедиться в том, что эта формула верна с помощью так называемой «математической индукции». Это значит:

нужно предположить, что ваша формула верна для определенного числа, и доказать, что в этом случае она верна и для следующего числа. Докажем, что наша формула верна для 1. Следовательно, она верна для 2, и для 3, и т. д. Это весьма эффективный метод, с помощью которого были доказаны большинство свойств целых чисел. И часто, как и в приведенном выше примере, это позволяет вам сформулировать предположение в виде теоремы.

Рассмотрим другой вид задач, а именно задач «комбинаций и перестановок». Довольно часто они приобретают значимость, но мы начнем с простых примеров. Предположим, хозяйка хочет организовать вечер с ужином, на который она хотела бы пригласить 20 человек, но одновременно она может пригласить только 10. Каковы же варианты выбора? Очевидно, что существует 20 вариантов выбора первого гостя; когда он выбран, остается 19 вариантов выбрать второго и т. д. Когда выбрано 9 гостей, остается 11 вариантов, следовательно, последний гость может быть выбран, исходя из 11-ти вариантов. Итак, полное число вариантов равно

20 х 19 х 18 х 17 х 16 х 15 х 14 х 13 х 12 х 11.

Это довольно большое число; просто удивительно, почему хозяйки не путаются. Мы можем упростить ответ, используя так называемые «факториалы».

Факториал 2 обозначает произведение всех чисел до 2, т. е.