Формула для суммы всех комбинаций перемножения

Я занимаюсь олимпиадным программированием и освоением математики. И в один прекрасный день нашел задачу: "Найти сумму всех комбинаций перемножения натурального ряда от 1 до N". И в данной статье я расскажу свое решение.

Решение за O(n^2) вы можете найти на GeeksForGeeks, где автор использует модернизированный Brute Force.

Мое же решение лежало через математику, а точнее через индукцию.

Доказательство

ВАЖНО: Заметим что ответ на задачу не меняется, если начинаем мы с 0. Поскольку все комбинации включающие 0, просто на сумме не отразятся.

База индукции

Здесь мы просто рассматриваем как работают комбинации на маленьких N. И грубо говоря: "пытаемся заметить закономерность".

Доказательство для n

• n! - 1 Это сумма произведений входящих до n - 1. _{(зеленная рамка)}

• n * (n!-1) Формула, которая образуется если во все предыдущие комбинации добавить наше n. В таком случае мы получим новые комбинации, которые не встречались ранее._{(красная рамка)}

• n Это оставшееся единичное подмножество из самого n. _{(синяя рамка)}

  В итоге просуммировав эти комбинации получаем:

Давайте сократим получившуюся формулу:

Итог

Именно так выглядит одно из доказательств для вышеприведенной формулы. Но главное к чему вся эта математика была проделана?

1) Для ускорения. Очевидно что итоговый ответ в виде кода будет работать за O(n). Понятно, что при больших N наш факториал будет замедляться. Но это точно лучше, чем обходить комбинации за квадрат.

2) Чтобы получить красивую формулу, которая будет легче писаться чем куча строк непростого кода.

Подарок

Предлагаю решить одну задачку и заметить кое-что интересное в ответе.

Условие: На доске выписаны числа 1, 2, ..., 20. Разрешается стереть любые два числа a и b и заменить их на число  ab + a + b.
Вопрос: Какое число может остаться на доске после 19 таких операций?