Глава 10 м18. Число возможных барабанов шифрмашины "Хагелин"

Это число совпадает с

количеством возможных представлений числа 27 в виде суммы шести неотрицательных целых чисел

Это эквивалентно количеству способов представления числа 27 в виде суммы неотрицательных целых чисел, каждое из которых не превосходит 6. (Элементарное доказательство этого факта можно найти в [10.1].)

Данное значение, в свою очередь, равно коэффициенту при x²⁷ в разложении по степеням x функции

.

Его можно подсчитать либо вручную (с большим трудом!), либо с помощью компьютерной программы. Оно оказывается равным 811.

Если мы потребуем (что было бы вполне логично), чтобы напротив каждого колеса стоял хотя бы один выступ, то нужное нам значение представляет собой коэффициент при x²¹ из упомянутого выше разложения, поскольку мы сначала выставим по одному выступу напротив каждого колеса, а оставшиеся 21 можно распределить без каких-либо ограничений. Это значение оказывается равным 331.

Эти примеры принадлежат к классу задач, которые относятся к разделу математики, именуемому комбинаторикой. Вот еще несколько подобных примеров.

Допустим, задано положительное целое число N:

1. Сколькими способами можно представить N в виде суммы положительных целых чисел, без учета порядка слагаемых? Это число обозначается p(N) и называется числом разбиений числа N. Например:

4:=4=3+1=2+2=2+1+1=1+1+1+1,

поэтому p(4)=5.

Для значения p(N) не существует никакой простой формулы. Подробное изложение этого вопроса можно найти в [10.1].

(2) Сколькими способами можно представить N в виде суммы (любого числа) положительных целых чисел, с учетом порядка слагаемых? Это число обозначается c(N) и называется числом комбинаций числа N. Например:

4:=4=3+1=1+3=2+2=2+1+1=1+2+1=1+1+2=1+1+1+1,

поэтому c(4)=8. На самом деле можно показать, что

c(N)=2^N-1.

Доказательство этого факта см. в [10.2].

3. Сколькими способами можно представить N в виде суммы (фиксированного числа) k положительных целых чисел, с учетом порядка слагаемых?

Поскольку всего слагаемых k штук, и каждое из них больше или равно единице, то это значение равно коэффициенту при X^N в разложении по степеням X функции

X^k(1-X)^-k

или, что то же самое, коэффициенту при X^(N-k) в разложении функции

(1-X)^-k

Этот коэффициент равен

.

Данная формула также используется при решении задачи 4.2 (при N=9 и k=3, в результате получаем 28).