Размещения с ограничениями

[Mr. Dred]

Здравствуйте!

Помогите пожалуйста с комбинаторной задачей подсчета всех возможных цифр по n местам со следующими ограничениями:

на накотором j-ом месте может быть размещено любое натуральное число от 1 до k, где k - это максимум среди всех предъидущих размещений на 1,2,...,j-1 местах

например для n=3 имеем 5 таких размещений:
111
112
121
122
123

Получил алгоритм подсчёта, который опишу ниже, но хотелось бы более кл=расивую формулу, если это возможно
Алгоритм:

1)Пусть мы имеем кортеж A(0)=<1>
2)Положим i=1
3)Сформируем кортеж A(i) из кортежа A(i-1) по следующиму правилу:
- Возьмем первый компонент а1 кортежа A(i-1) и дополним им котеж A(i) а1 раз
- Дополним котеж A(i) числом а1+1
- Возьмем следующий компонент а1 кортежа A(i-1) и проделаем тоже самое, и так со всеми компонентами кортежа A(i-1)
4)Положим i=i+1
5)Если i=n, то сумма компонентов полученного кортежа A(i) есть искомое число размещений, иначе идем к п. 3

Приведу пример работы алгоритма
<1>
<2>
<2, 3>
<2, 3, 3, 3, 4>
<2, 3, 3, 3, 4, 3, 3, 4, 3, 3, 4, 4, 4, 4, 5>
и.т.д.

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

[JMH]

С условием задачи у Вас нехорошо - ничего не понять. Тем не менее, чудится мне, что тривиальное правило умножения - то, что надо

[arseniiv]

Mr. Dred в сообщении #459588 писал(а):

на накотором j-ом месте может быть размещено любое натуральное число от 1 до k, где k - это максимум среди всех предъидущих размещений на 1,2,...,j-1 местах

например для n=3 имеем 5 таких размещений:
111
112
121
122
123

Как-то не соответствует! А вот если в описании вместо «максимум» написать «сумма» — вроде то.

-- Вс июн 19, 2011 03:42:41 --

Хотя нет, даже сумма — не то.

-- Вс июн 19, 2011 03:43:26 --

Сумма + 1 подходит.

[Mr. Dred]

Пардон, опечатка

на накотором j-ом месте может быть размещено любое натуральное число от 1 до k+1, где k - это максимум среди всех предъидущих размещений на 1,2,...,j-1 местах

например для n=3 имеем 5 таких размещений:
111
112
121
122
123

для большей наглядности приведу ниже ряд подобных размещений для n=4

1111
1112
1121
1122
1123
1211
1212
1213
1221
1222
1223
1231
1232
1233
1234

[arseniiv]

А, ясно. Правда, написано всё так же не по-русски не очень осмысленно. Попробую подумать над производящей функцией.

-- Вс июн 19, 2011 03:51:38 --

Может, ввесть несколько? $T_k (z)$ — производящая функция кол-ва последовательностей имени Mr. Dredа, содержащих только цифры $\leqslant k$. Вроде, на этом пути есть удача.

Нет, немного не так. Пусть $U_1$ — множество последовательностей из одних единиц. Определим $U_{k+1}$ как множество последовательностей с цифрами $\leqslant k+1$, которые не входят ни в одно из $U_{i = 1}^k$. А $T_k(z)$ будет соответствующей производящей функцией.

-- Вс июн 19, 2011 04:08:22 --

(Искомая $T(z) = \sum_{i=0}^{\infty} T_i(z)$; $T_0(z) = 1$.)

Глядите, что получается: $T_k = zT_{k-1} + kzT_k$.

Теперь осталось всё найти…

-- Вс июн 19, 2011 04:19:54 --

$T_k$ легко выражается через $T_{k-1}$. Далее, по индукции можно получить $T_k(z) = \frac{z^k}{\prod_{i=0}^k (1 - iz)}$. Чему такая функция соответствует, не помню, надо таблицы смотреть и выражать как-нибудь.

А $T$, кстати, имеет очень интересный вид: $1 + \frac z{1-z}\left( 1 + \frac z{1-2z}\left( 1 + \frac z{1-3z} \left( 1 + \ldots \right) \right) \right)$. Правда, для манипуляций такой не лучше просто суммы $T_k$.

-- Вс июн 19, 2011 04:31:00 --

Очевидно, $T_k$ производит свёртку последовательностей $\langle 1^i \rangle_{i = 0}^{\infty}, \langle 2^i \rangle_{i = 0}^{\infty}, \ldots, \langle k^i \rangle_{i = 0}^{\infty}$, сдвинутую на $k$ вправо.

[Mr. Dred]

Спасибо большое, очень помогли с решением!

[arseniiv]

Вы нашли, что в итоге ваши числа оказались числами Белла?

[Mr. Dred]

Нет, дело в том, что комбинаторику я только начинаю осваивать, а с задачей столкнулся в исследованиях в области теоретической информатики

[arseniiv]

А в каких исследованиях? (Интересно.)

[Mr. Dred]

Ну есть одно направление в Омском политехе, разработанное доентом кафедры "Информатика и вычислительная техника" А.С.Гуменюком, Формальный анализ строя знаковой цепи

Это новый подход к анализу знаковых последовательностей. Возьмем например простую цепь знаковую КАРАВАЙ.
Классическая теория вероятности рассматривает частоты отдельных событий а также частоты в парах(тройках) и.т.д.

Анализ строя же ставит своей целью не анализ часот событий, а их взаимного расположения.
Для производится декомпозиция цепи на однородные:
К А Р А В А Й
К - - - - - -
- А - А - А -
- - Р - - - -
- - - - В - -
- - - - - - Й
Далее рассматриваются интервалы (расстояний между событиями). Для первой однородной цепи
К - - - - - -
существует лишь один интервал от начала до К, равный 1
для второй цепи
- А - А - А -А
интервалы будут следующие 2(от начала до 1-ой А), 2(от первой А до второй), 2(от второй А до третьей) для каждой из букв А
и так далее для всех однородных цепей

таким образом вся цепь будет иметь следующую последовательность интервалов
1,2,3,2,5,2,7

На основе полученных интегралов вычисляются интегральные характеристики
Основной является объем строя V равный произведению всех интервалов

Комбинаторная задача появилась на основе абстракции введенной в рамках подхода - строя цепи.

Строй цепи сообщений – это кортеж (упорядоченное множество), в котором каждому компоненту данной цепи в соответствие поставлено натуральное число, причем идентичные по выбранному признаку компоненты отображены одним и тем же числом. Самый первый компонент такого кортежа – единица, а все остальные первые встречные разные натуральные числа (представляющие вместе с единицей алфавит строя) возрастают на единицу
Пример:
КАРАВАЙ
1232425

собственно все возможные строи для цепей с заданной длинной - это и есть последовательности комбинаторной задачки