Задача 15

Все перестановки 7 чисел упорядочены в лексикографическом порядке. Какой по счету идет перестановка 3714652?

Решение

Найдем число перестановок, предшествующих данной.

Этой перестановке предшествуют перестановки, начинающиеся с цифры, меньшей 3, т.е. перестановки вида 2* и 1*, где * обозначает перестановку из 6 оставшихся цифр. Примеры таких перестановок: 2165437 и 1576342.

Число перестановок, начинающихся с 2, равно 6!; столько же перестановок начинается с 1. Цифр меньших, чем 3, есть 3-1 = 2.

Получаем, что число перестановок, начинающихся с цифры, меньшей 3, равно

Далее, исходной перестановке предшествуют все перестановки, начинающиеся с 3, вторая цифра которых меньше 7. Вторую цифру, меньше 7 можно выбрать 7-1-1=5 способами. Эта запись означает, что мы исключили саму цифру 7, а также уже использованную цифру 3. Для каждого выбора первых двух цифр существует 5! различных перестановок.

Таким образом, число перестановок, начинающихся с 3, вторая цифра которых меньше 7, равно

Продолжая далее, получаем формулу для числа перестановок, предшествующих данной перестановке

Номер самой перестановки на 1 больше

.

Если использовать коэффициенты при факториалах как цифры числа, то получаем так называемую факториальную запись числа. В нашем случае

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

Проверка

Делим число 2051 на 1, затем полученное частное на 2, затем новое частное на 3 и т.д. до получения нулевого частного.

2051	1
2051	2051	2
0	2050	1025	3
	1	1023	341	4
		2	340	85	5
			1	85	17	6
				0	12	2	7
					5	0	0
						2

Прочитав остатки в обратном порядке (снизу вверх), получим факториальную запись числа . Видим, что она совпадает с записью исходного числа.

Ответ: 2052.