Двумерная последовательность, связанная с разбиениями

[Егор]

Хочу предложить вашему вниманию одну двумерную последовательность.
Подскажите, как её найти в Энциклопедии целочисленных последовательностей? У меня не получилось.

Определим $X(n,b)$ как число целочисленных кортежей длины $n$ вида $(c_1,\ldots,c_n)$, где

$$ 1\le c_1 \le b+1,\qquad 1\le c_i \le \max(b,c_1,\ldots,c_{i-1})+1\quad\text{при}\quad 2\le i\le n. $$

Например, $X(2,1)=5$, так как имеется 5 кортежей нужного вида:
(1,1), (1,2), (2,1), (2,2), (2,3).

Легко вывести для $X(n,b)$ рекуррентное соотношение и начальные условия:

$$ X(0,b) = 1,\qquad X(n,b) = b\cdot X(n-1,b)+X(n-1,b+1). $$

Вот таблица первых значений $X(n,b)$:

$$ \begin{array}{c||r|r|r|r|r|r|r|r|} & b=0 & b=1 & b=2 & b=3 & b=4 & b=5 \\ \hline\hline n=0 & 1 & 1 & 1 & 1 & 1 & 1 \\ n=1 & 1 & 2 & 3 & 4 & 5 \\ n=2 & 2 & 5 & 10 & 17 \\ n=3 & 5 & 15 & 37 \\ n=4 & 15 & 52 \\ n=5 & 52 \\ \end{array} $$

Левые два столбца заняты числами Белла (значит, на замкнутую формулу для $X(n,b)$ рассчитывать не приходится). Последовательность $X(n,b)$ связана с подсчётом и порождением разбиений множеств и чем-то похожа на треугольник Белла и на числа Стирлинга второго рода.

[Gafield]

Экспоненциальная производящая функция простая:

$$G(x,y)=e^{e^x (y+1)-1}$$

. Учитывая, что $\partial_y^m G(x,0)=e^{e^x+mx-1}$, отсюда можно получить явную формулу, выражающую $X(n,b)$ через числа Белла:

$$ X(n,b)= \sum _{k=0}^n \left( \begin{array}{c} n \\ k \end{array} \right) B_k b^{n-k}. $$

[Егор]

Gafield, спасибо!

Проверил численно Вашу последнюю формулу (которая выражает $X(n,b)$ через $B(n)$), теперь тщетно пытаюсь понять, как Вы нашли ЭПФ.
ЭПФ понимаю как $G(x,b)=\sum_{n=0}^\infty \frac{X(n,b) x^n}{n!}$, то есть $b$ считаю параметром.

Для ЭПФ получил уравнение $G'(x,b)=b G(x,b)+G(x,b+1)$. Решением служит функция $G(x,b)=e^{e^x+bx-1}$, что немножко отличается от Вашего решения.

ЭФП $G(x,b)=e^{e^x+bx-1}$ согласуется с Вашей последней формулой: раз $X(n,b)$ есть "биноминальная свёртка" чисел $B(n)$ и $b^n$, то $G(x,b)$ есть произведение соответствующих ЭПФ $e^{e^x-1}$ и $e^{bx}$.

Добавление: кажется, дошло. Похоже, что Вы составляете ЭПФ как $\displaystyle G(x,y)=\sum_{n,b=0}^\infty \frac{X(n,b) x^n y^b}{n!\,b!}$.

[maxal]

Егор, если ваша двумерная последовательность отсутствует в OEIS - добавьте ее туда, плз. Только, наверное, имеет смысл считать ее прямоугольной, а не треугольной (ничто не мешает продлить каждый столбец до бесконечности).

По поводу того, как добавлять двумерные последовательности - см. http://oeis.org/hints.html
Кроме того, рекомендую найти все последовательности строк и столбцов присутствующие в OEIS и дать на них ссылки. В качестве примера - A119269

[Gafield]

Егор писал(а):

Добавление: кажется, дошло. Похоже, что Вы составляете ЭПФ как $\displaystyle G(x,y)=\sum_{n,b=0}^\infty \frac{X(n,b) x^n y^b}{n!\,b!}$.

Да.

[Егор]

Нашлась, родимая! A108087

maxal, спасибо за ответ! Только после Вашего примера я понял, что элементы прямоугольных таблиц нужно перечислять по антидиагоналям снизу вверх.

Кстати, в этой статье я не увидел формул для экспоненциальных производящих функций. Ни для всей таблицы, ни для произвольного фиксированного столбца. Хотя для первых столбцов эпф приведены, и обобщение совершенно очевидно.

Frank Ruskey в книге "Combinatorial Generation" даёт такое описание, как в моём первом сообщении, и пишет, что эти числа иногда называют "restricted tail coefficients".

[Gafield]

Цитата:

Кстати, в этой статье я не увидел формул для экспоненциальных производящих функций. Ни для всей таблицы, ни для произвольного фиксированного столбца. Хотя для первых столбцов эпф приведены, и обобщение совершенно очевидно.

И явной формулы через числа Белла нет.

[Егор]

Gafield писал(а):

И явной формулы через числа Белла нет.

Да. Gafield, как я понимаю, эти пробелы Вам придётся заполнять.

[maxal]

Егор писал(а):

Нашлась, родимая! A108087

maxal, спасибо за ответ! Только после Вашего примера я понял, что элементы прямоугольных таблиц нужно перечислять по антидиагоналям снизу вверх.

Кстати, в этой статье я не увидел формул для экспоненциальных производящих функций. Ни для всей таблицы, ни для произвольного фиксированного столбца.

для столбцов там egf указана:

%F A108087 For n> 1, A(n, k) = k^n + sum_{i=0..n-2} A086659(n, i)*k^i. (A086659 is set partitions of n containing k-1 blocks of length 1, with e.g.f: exp(x*y)*(exp(exp(x)-1-x)-1).

[Егор]

maxal писал(а):

для столбцов там egf указана:

%F A108087 For n> 1, A(n, k) = k^n + sum_{i=0..n-2} A086659(n, i)*k^i. (A086659 is set partitions of n containing k-1 blocks of length 1, with e.g.f: exp(x*y)*(exp(exp(x)-1-x)-1).

Вроде бы, там написана egf для другой последовательности A086659, а не для столбцов обсуждаемой A108087, да?

[Gafield]

Цитата:

Да. Gafield, как я понимаю, эти пробелы Вам придётся заполнять.

Оставляю эту работу желающим