Сообщение от 12121
Если у нас 45 чисел то это можно представить как 45 ричная система счисления. Если 2 ячейки то это будет 45 во 2 степени. Если 3 то 45 в 3.
Может я конечно не прав. Подумал что по анологии с 16 и 2 системой счисления очень похоже.
В 16 системе можем в 1 ячейку записать 16 чисел от 0 до 15. Если 2 ячейки будет 256 вариантов.
|
Из получившейся формулы (n^k) надо вычесть повторные комбинации (вида ХХ, где Х - цифра: 11,22..). все го их будет: n - для двух позиций, для трёх - три раза по n (сочетания типа XX* Х*Х *ХХ: 11*,1*1,*11) и ещё раз n (XXX:111), т.е. n*4, т.о.
для n=2: n^2-n
n=3: n^3-4*n
далее уже придёться учесть все возможные миграции повторяющихся групп цифр длиной 2,3,.. В общем жесть.
Исчерпание же цифр (размещение без повторений) объясняется (в зависимости от специфики класса - изучается\додумывается в ходе решения самостяельно) ещё в школе: допустим, есть
W цифр - составить все возможные из них числа (каждая цифра используется
только один раз). Процесс конструирования числа можно представить как последовательный выбор цифр из некоего запасника, т.о. первую цифру мы можем выбрать
W способами (берём одну любую цифру из
W), после этого вторую цифру можно выбрать уже (
W-1) способами, и т.д. - на
W-ом шаге, останется одна (ещё не встречавшаяся цифра). Значит всего решений:
Q=
W*(
W-1)*(
W-2)*(
W-3)*..*1=
W! для
W позиций (алфавит в данном случае тоже из
W символов).
Если у нас есть, к примеру, 2 ячейки, а цифр 10, то продолжая расширять указанное выше решение, прийдём к следующему: две цифры из 10 (в двух ячейках) можно разместить 10*9 (всего 100 вариаций минус 10 ХХ сочеатний:00,11,22..99) раз способами, т.е. решением будет
N первых множителей выражения для
Q, где
N - число ячеек. "Выкинуть" из
Q "хвост" можно единтсвенным образом (обратным его "наращиванию") - делением, т.е.
Q необходимо поделить на (
W-
N)*(
W-
N-1)*(
W-
N-2)*..*1 (для рассматриваемой задачи - (10-2)*(10-2-1)*(10-2-2)*..*1=8*7*6*..*1 - какраз-таки "хвост"). Очевидно делим мы на факториал (
W-
N). Значит всего решений:
Z=
W!/(
W-
N)!
Собственно, данная формула и указана в учебниках.
Наблюдательный читатель, обратит внимание, что формулу можно переписать с использованием биномиального коэффициента (который должен быть знаком ещё по "формулам сокращённого умножения", люди которые долго пытались [как я, перебиваясь с удовл на хор] зазубрить в школе эти безумные формулы, могли заметить, что коэффициенты в формуле по сути и задают все возможные перестановки для слагаемых [подобно тому, как это требуется в решаемой задаче] - это ощущение захлопывающейся полноты системы взглядов и интерепретаций сложно с чем-то спутать).