разделяй-и-властвуй разбиения прямоугольников

[arseniiv]

Не нашёл в OEIS (по-всякому: и части строк, и части антидиагоналей) двумерной последовательности чисел разбиений типа «разделяй и властвуй» прямоугольника $m\times n$ на целочисленной сетке на другие целочисленные прямоугольники. Это такие разбиения, которые можно получить, деля прямоугольники на две части. (Если совсем непонятно выразился, по просьбе нарисую.)

Рекуррентная формула этой последовательности такая:

$$p(m,n) = 1 + \sum_{i=1}^{m-1} p(i,n)p(m-i,n) + \sum_{i=1}^{n-1} p(m,i)p(m,n-i).$$

(Не знаю, какими лучше выбрать $p(n,0) = p(0,n)$. Может, единицы подойдут. Во всяком случае, $p(0, 0)$ уж точно следует выбрать единичным, да и с формулой это согласуется.)

Если эта последовательность там есть — пожалуйста, покажите! А если нет — не знаю, стоит ли мне регистрироваться или попросить кого-нибудь внести запись о ней (вроде, тема для таких просьб была здесь, но не смог найти). Если кто-то захочет, приведу немного дополнительных данных:

$p(a,b) = p(b,a)$;

Возможный код на Mathematica 8 (по-моему, должен работать и на 5 и более ранних; пока не видел в OEIS рекомендаций к версии, для которой указывается код):

a[m_, n_] := a[m, n] = If[m == 0 || n == 0, 0, Sum[a[i, n] a[m - i, n], {i, 1, m - 1}] + Sum[a[m, i] a[m, n - i], {i, 1, n - 1}]] + 1

Насколько знаю, код рекомендуется делать однострочным — сделал такой.

Начальные значения по антидиагоналям, начиная с $(0, 0)$:

1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 5, 9, 5, 1, 1, 15, 62, 62, 15, 1, 1, 51, 555, 1241, 555, 51, 1, 1, 188, 5938, 32905, 32905, 5938, 188, 1, 1, 731, 72931, 1088611, 2590351, 1088611, 72931, 731, 1, 1, 2950, 1001790, 43928468, 260533247, 260533247, 43928468, 1001790, 2950, 1, 1, 12235, 15066756, 2120559635, 33610060775, 79005470861, 33610060775, 2120559635, 15066756, 12235, 1, 1, 51822, 243629094, 119331258310, 5571806117201, 31382601829332, 31382601829332, 5571806117201, 119331258310, 243629094, 51822, 1, 1, 223191, 4171672883, 7598537855507, 1159378522657088, 17101224492478097, 37263998546837813, 17101224492478097, 1159378522657088, 7598537855507, 4171672883, 223191, 1, 1, 974427, 74732630906, 532490554273634, 289819040450725021, 12793117887565507798, 62203992154002217892, 62203992154002217892, 12793117887565507798, 289819040450725021, 532490554273634, 74732630906, 974427, 1, 1, 4302645, 1387678909465, 40157801725561967, 83182468866007697165, 12411807868185761887593, 157366409203190062251932, 297673204380311095417269, 157366409203190062251932, 12411807868185761887593, 83182468866007697165, 40157801725561967, 1387678909465, 4302645, 1, 1, 19181100, 26521428609262, 3205249839869263865, 26450536817074978611723, 14541879534095833366436302, 576297828182920595865664612, 2254065837160963454876132166, 2254065837160963454876132166, 576297828182920595865664612, 14541879534095833366436302, 26450536817074978611723, 3205249839869263865, 26521428609262, 19181100, 1, 1, 86211885, 518970524638009, 267524468054653186977, 9087177675503249635663481, 19481637344176959935333146441, 2733341425184031032735013038617, 28900405064550035285587964919965, 44876774577264353544114141934177, 28900405064550035285587964919965, 2733341425184031032735013038617, 19481637344176959935333146441, 9087177675503249635663481, 267524468054653186977, 518970524638009, 86211885, 1

Сужение $n\mapsto p(1,n)$ — это A007317.

А разбиения такого вида не считаются:

Вложение:

not-a-div-and-conq-partition.png

-- Вт май 28, 2013 23:25:32 --

Пожалуйста, проверьте эти данные и посоветуйте, что ещё можно было бы добавить к записи.

-- Вт май 28, 2013 23:26:37 --

…и ещё как лучше описать считаемые разбиения.

-- Вт май 28, 2013 23:27:21 --

И если всё будет хорошо, можно потом кубы бить!

[maxal]

Лучше вообще не определять для нулевых индексов (т.к. естественным образом в формуле они не возникают), но если уж определять, то должно выполняться $p(n,0)=p(n,1)$ в соответствие с рекуррентной формулой.

[arseniiv]

maxal, а как вы считаете, насколько осмысленно выделить отдельно, например, последовательность $n\mapsto p(n,n)$?

[maxal]

arseniiv в сообщении #729710 писал(а):

maxal, а как вы считаете, насколько осмысленно выделить отдельно, например, последовательность $n\mapsto p(n,n)$?

Да, имеет смысл.

[arseniiv]

Ну вот. Формула не соотносится с этими разбиениями 1:1, она даёт числа не меньше. Например, есть всего 4 разбиения прямоугольника $3\times1$, а не 5.

Ясно, почему числа, возможно, не нашлись. Стоит ли теперь эту последовательность предлагать? Может, у неё какие-то интересные свойства есть? (Как жаль. Я уже почти всё оформил. Завтра, значит, посмотрим…)

[maxal]

arseniiv в сообщении #729829 писал(а):

Ну вот. Формула не соотносится с этими разбиениями 1:1, она даёт числа не меньше. Например, есть всего 4 разбиения прямоугольника $3\times1$, а не 5.

Ну да, должно быть $p(n,1) = 2^{n-1}$, т.е. количество всех композиций числа $n$.

Вот PARI/GP код, вычисляющий правильные значения более точные верхние оценки для $m,n=1..5$:

? ph(m,n) = local(s); 1 + sum(k=2,m, s=0; forvec(v=vector(k-1,i,[1,m-1]), s += ph(n,v[1])*ph(n,m-v[k-1])*prod(i=1,k-2,ph(n,v[i+1]-v[i])), 2); s);
? p(m,n) = ph(m,n) + ph(n,m) - 1;
? matrix(5,5,m,n,p(m,n))
%1 = 
[ 1    2      4        8        16]
[ 2    9     45      234      1233]
[ 4   45    593     8098    111247]
[ 8  234   8098   286985  10157914]
[16 1233 111247 10157914 920259357]

В OEIS она тоже отсутствует.

[arseniiv]

А что возвращает vector(k-1,i,[1,m-1])?

К сожалению, у вас тоже неправильный алгоритм. Разбиений $2\times2$ всего 8. Вот первые числа, найденные перебором:

1,      2,       4,       8,      16,     32,      64
2,      8,      34,     148,     650,   2864,   12634
4,     34,     320,    3118,   30752, 304618, 3022112
8,    148,    3118,   68480, 1525558
16,   650,   30752, 1525558
32,  2864,  304618
64, 12634, 3022112

Находится A116694, в которой количества всех разбиений. Этой пока нет. Оформлю статью без алгоритмов и формул пока что. Нужно ли к такой добавить ключевые слова uned или new?

UPD: Если что, вот пока непроверенная запись: https://oeis.org/draft/A222659 (если что, все изменения кроме замены «Array» на «Table» — автоматические).

Думаю, для последовательности чисел на диагонали ещё мало членов. Для вычисления $p(5, 5)$ перебором у меня не хватает памяти.

[maxal]

arseniiv в сообщении #729997 писал(а):

А что возвращает vector(k-1,i,[1,m-1])?

К сожалению, у вас тоже неправильный алгоритм. Разбиений $2\times2$ всего 8.

Ну да, у меня тоже верхняя оценка, только чуть более точная.
vector(k-1,i,[1,m-1]) выдает вектор размера k-1, каждый элемент которого есть вектор [1,m-1].

Последовательность A222659 немного отредактировал и утвердил.

[arseniiv]

Спасибо! И за редактирование тоже. И разбиение квадрата теперь более понятно.