2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Двумерная последовательность, связанная с разбиениями
Сообщение18.07.2008, 23:04 
Хочу предложить вашему вниманию одну двумерную последовательность.
Подскажите, как её найти в Энциклопедии целочисленных последовательностей? У меня не получилось. :?

Определим $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)$ связана с подсчётом и порождением разбиений множеств и чем-то похожа на треугольник Белла и на числа Стирлинга второго рода.

 
 
 
 
Сообщение19.07.2008, 00:56 
Экспоненциальная производящая функция простая: $$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}.  $$

 
 
 
 
Сообщение19.07.2008, 19:24 
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!}$.

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

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

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

Да.

 
 
 
 
Сообщение20.07.2008, 23:48 
Нашлась, родимая! A108087

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

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

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

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

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

 
 
 
 
Сообщение21.07.2008, 17:37 
Gafield писал(а):
И явной формулы через числа Белла нет.

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

 
 
 
 
Сообщение21.07.2008, 20:33 
Аватара пользователя
Егор писал(а):
Нашлась, родимая! 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).

 
 
 
 
Сообщение21.07.2008, 20:54 
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, да?

 
 
 
 
Сообщение21.07.2008, 21:27 
Цитата:
Да. Gafield, как я понимаю, эти пробелы Вам придётся заполнять. :)

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

 
 
 [ Сообщений: 11 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group