Изменения

|proof=

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

он изменяется в <tex>\frac{w_{\alpha_k}}{n+k-1}</tex> раз. На каждом шаге <tex>k</tex>-й символ <tex>\alpha</tex> будет иметь вес <tex>\alpha_k</tex> (каждый раз больший на <tex>1</tex>, потому что алгоритм адаптивный).

Значит, на каждом шаге суммарный вес символов будет увеличиваться на <tex>1</tex>, т.е. на шаге <tex>k</tex> суммарный вес символов будет равен <tex>n+k-1</tex>

Соответственно, формула примет вид:

<tex>

L_{min} = \prod_{i=1}^l \frac{1}{n+i-1} = \frac{1}{\frac{(n+l-1)!}{(n-1)!}} = \frac{(n-1)!}{(n+l-1)!}

Можно записать, используя формулы комбинаторики:

L_{min} = \frac{1}{{\binom{l}{n+l-1}}l!} = \frac{1}{C_{n+l-1}^{l}l!}

Для того, чтобы максимизировать произведение, необходимо увеличить числитель каждого члена произведения. Этого можно достичь, если передать на вход алгоритму строку, состоящую из одинаковых символов. В таком случае, на каждом из шагов <tex>k=1, 2, \dots, l</tex> вес символа будет равен k, а значение кода будет изменяться в <tex>\frac{k}{n+k-1}</tex> раз.

Соответственно, формула будет иметь следующий вид:

<tex>

L_{max} = \prod_{i=1}^l \frac{i}{n+i-1} = \frac{l!(n-1)!}{(n+l-1)!}

Можно записать, используя формулы комбинаторики:

L_{max} = \frac{1}{\binom{n+l-1}{l}} = \frac{1}{C_{n+l-1}^{l}}

}}