Пин код телефона

@Игорь Черкашенко, может и есть способ проще, а я пошёл "в лоб" :)

Конечно, крайним случаем будет пин-код 6789. То есть, если мы первой цифрой выберем 6-ку, то код будет 1. Если первой цифрой будет 5-ка, то второй может быть 6-ка или 7-ка, для 6-ки же ещё два ветвления — за ней может следовать 7-ка и 8-ка, а за 7 ещё две цифры — 8-ка или 9-ка. Таким образом, общее количество ветвлений от цифры 5 (если она стоит первой) будет равно 3 + 1 (3 ветвления, если второй стоит 6-ка и 1 ветвление, если второй стоит 7-ка). Действительно, вариантов с первой пятёркой всего четыре: 5678, 5679, 5689, 5789.

Продолжая эти рассуждения, приходим к тому, что, если первой стоит 4-ка, общее кол-во подходящих результатов будет 6 + 3 + 1. А если первой стоит 3-ка, всего результатов 10 + 6 + 3 + 1. И т. д. И для стоящего первым нолика это будет 28 + 21 + 15 + 10 + 6 + 3 + 1. Знакомые числа! Ведь каждое из этих слагаемых является суммой первых n натуральных чисел (1 = 1, 3 = 1 + 2, … 28 = 1 + … + 7). Вот тут уже можно немного сжульничать, начав использовать алгебраические суммы :)

Ведь общее кол-во результатов будет равно 1 + (1 + 3) + … + (1 + … + 28). А это соответствует вот таким вот вложенным суммам:

Самая "вложенная" из сумм была высчитана ещё Гауссом и имеет общий вид b(b + 1)/2. Дальше начинается череда манипуляций. Используя законы сложения, можно получить:

Первая из двух вложенных сумм тоже достаточно просто находится, но я не буду тратить место здесь, чтобы это расписывать. Огромное спасибо Якобу Бернулли за его труд, что говорится :)

Получаем следующее разложение:

Снова используем законы сложения:

И эти суммы, собственно, также представимы в виде многочленов. Да и сумма кубов есть ни что иное как квадрат суммы первых степеней для суммы первых n членов натурального ряда, так что всё очень даже красиво сводится к числу 210. Наверное, метод не самый оптимальный, но мне очень даже нравится его глобальность что ли? :)