@OneDeus

Сколько чисел в шестеричной системе счисления, которые не имеют одинаковых цифр?

Сколько чисел в шестеричной системе счисления, которые не имеют одинаковых цифр?
  • Вопрос задан
  • 35 просмотров
Решения вопроса 1
wataru
@wataru
Разработчик на С++, гуглер, экс-олимпиадник.
Ответ:
sum(i=0..15) 15!*15/i!

Очевидно, длина не может быть больше 16 символов.

Дальше, переберем длину числа. Пусть это L. Должны быть L разных цифр. Но есть проблема - первая цифра не может быть 0. Подсчитаем отдельно варианты, где 0 вообще нет, и где 0 есть. В первом случае есть 15!/(15-L)!/L! вариантов выбрать L цифр из 1-15. И надо домножить на L!, ведь их можно перемешивать как угодно. Во втором варианте мы берем 0 и L-1 цифр из 1-15 - это 15!/(15-(L-1))!/(L-1)! вариантов. Надо домножить на (L-1) возможных позиций 0 и (L-1)! возможных перестановок всех остальных цифр. Поскольку без 0 можно получить, только если длина меньше 16, случай с L=16 выделим отдельно.

Итого - ответ:
sum(L=1..15) {15!/(15-L)! + 15!/(16-L)!*(L-1)} + 15!*15

Немного посокращав можно упростить того, что я привел в начале:
sum(i=0..15) 15!*15/i!

В общем виде для N-чной системы счисления надо вместо 15 записать N-1.

Можете проверить, что формула работает для N=2: 1!*1(1/0!+1/1!) = 1*2 = 2 ("10" и "1").
И N=3: 2!*2*(1/0!+1/1!+1/2!) = 4*(1+1+1/2) = 10 ("1", "2", "10", "20", "12", "21", "120", "210", "102", "201")
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
OCTAGRAM
@OCTAGRAM
Используйте формулу включений-исключений
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы