Перманент матрицы

[kthxbye]

Дана матрица $n\times n$ с элементами $a_{i,j}=\min(i,j)$. Пусть также $b(n)$ - перманент данной матрицы.

Задача: написать алгоритм и вычислить первые $500$ значений $b(n)$.

Ограничения: алгоритм должен вычислять вышеуказанное количество членов максимум за минуту.

[zykov]

A204262

[vicvolf]

kthxbye в сообщении #1599718 писал(а):

Ограничения: алгоритм должен вычислять вышеуказанное количество членов максимум за минуту.

Это ограничения не для алгоритма, а для вычислительной программы и производительности компьютера.

[kthxbye]

zykov, все верно, это та самая последовательность. Эффективных алгоритмов там пока нет.

vicvolf, вы правы. Я плохо знаком с нотацией "О" большое, иначе сразу бы указал сложность, соответствующую моему алгоритму. Википедия говорит, что по формуле Райзера лучший результат, который можно достичь это $O(2^n n)$. Тогда решением можно считать вычисление за меньшее время. Если таковое будет найдено, я сразу же поделюсь своим.

[Geen]

Кстати, а сколько цифр в числе $b(500)$?

[mihaild]

У нас $500!$ слагаемых, каждое не меньше чем $1^2 \cdot 2^2 \cdot \ldots 250^2$ и не больше чем $500!$. Чуть больше $2000$ десятичных разрядов выходит.

[kthxbye]

Geen в сообщении #1599785 писал(а):

Кстати, а сколько цифр в числе $b(500)$?

Судя по всему $2172$.

[wrest]

zykov в сообщении #1599730 писал(а):

A204262

Там программа на pari устарела.
Их текст:
a(n)={my(S, z, v=vector(n)); for(i=0, n!-1, v=numtoperm(n, i); z=1; for(j=1, n, z*= n+1-max(j, v[j])); S+=z); return(S)}
"Прямой" текст
b(n)=matpermanent(matrix(n,n,i,j,min(i,j)))
Считает немного быстрее (на несколько порядков), но не так, чтобы удовлетворить запрос ТС о минуте.
Текст из oeis в минуту укладывается максимум $b(10)$; "прямой" текст за минуту считает максимум $b(26)$
Судя по всему, ТС намекает что вычисляться может рекурсивно как-то, раз он просит за минуту вычислить не $b(500)$ а все $b(n)$ от $n=1$ до $n=500$.

[kthxbye]

wrest в сообщении #1599797 писал(а):

b(n)=matpermanent(matrix(n,n,i,j,min(i,j)))

Аналогичный код можно обнаружить в A204256.

wrest в сообщении #1599797 писал(а):

Судя по всему, ТС намекает что вычисляться может рекурсивно как-то, раз он просит за минуту вычислить не $b(500)$ а все $b(n)$ от $n=1$ до $n=500$.

Верное предположение.

Кстати, я тут заглянул в англоязычную Википедию, там оценка чуточку отличается. Следовательно отмечу, что формулу Райзера предлагать не надо, ровно как и любую из формул товарищей Balasubramanian–Bax–Franklin–Glynn.

[wrest]

kthxbye в сообщении #1599808 писал(а):

Следовательно отмечу, что формулу Райзера предлагать не надо,

Ну ясно, именно по ней matpermanent() и считает, за минуту до $b(30)$ там не добраться даже...

[Null]

Пусть $f_{n,l}(x)$ - определитель матрицы $n\times n$

$$c_{i,j}=\begin{cases} \min(i,j),&\text{если $\min(i,j)\le l$;}\\ x,&\text{если $\min(i,j)> l$;}\ \end{cases}$$

Тогда
1.$f_{n,l}(l)=f_{n,l-1}(l)$
2.$f'_{n,l}(x)=(n-l)^2f_{n-1,l}(x)$
3. $f_{n,0}(x)=n!x^n$
4. $f'_{n,n-1}(x)=f_{n-1,n-2}(n-1)$
можно считать многочлены $f_{n,l}(x)$ в явном виде.
$b(n)=f_{n,n-1}(n)$

[maxal]

Null, добавьте плз эту формулу в A204262, а также желательно и b-file с 100 (или 1000) членов.

[wrest]

Null в сообщении #1599814 писал(а):

Пусть $f_{n,l}(x)$ - определитель матрицы $n\times n$

$$c_{i,j}=\begin{cases} \min(i,j),&\text{если $\min(i,j)\le l$;}\\ x,&\text{если $\min(i,j)> l$;}\ \end{cases}$$

Хотелось бы уточнить нотацию.
Допустим, $n=4,l=3,x=4$, тогда соответствующая матрица будет
1 1 1 1
1 2 2 2
1 2 3 3
1 2 3 4
Верно? И её определитель $f_{4,3}(4)=1$
Если я правильно понял нотацию, то $f_{n,n-1}(n) \equiv 1$ т.к. это как раз та матрица, перманент которой считает ТС, а её определитель равен единице всегда...

[kthxbye]

Null, благодарю за комментарий! Вы не могли бы уточнить как вычисляется ваша функция? Ну т.е. каковы формулы для базовых и общего случая. А то я совсем не не совсем понимаю.

[Null]

wrest в сообщении #1599829 писал(а):

И её определитель

Имеется в виду перманент.

-- Вт июл 04, 2023 18:12:07 --

maxal, нужно чтобы кто-нибудь проверил хотя-бы.

-- Вт июл 04, 2023 18:35:10 --

$f_{1,0}(x)=x, f_{1,1}(x)=1$
$f_{2,0}(x)=2x^2, f_{2,1}(x)=x+1, f(2,2)(x)=3$
$f_{3,0}(x)=Prem\left( \begin{array}{ccc} x & x& x\\ x & x &x \\ x & x &x \end{array}\right)=6x^3$
$f_{3,1}(x)=Prem\left( \begin{array}{ccc} 1 & 1& 1\\ 1 & x &x \\ 1 & x &x \end{array}\right)=\int 2^2 f_{2,1}(x)dx+C=2x^2+4x+C$
C учетом $f_{3,1}(1)=f_{3,0}(1)$ получим $C=0$
$f_{3,2}(x)=Prem\left( \begin{array}{ccc} 1 & 1& 1\\ 1 & 2 &2 \\ 1 & 2 &x \end{array}\right)=\int 1^2 f_{2,2}(x)dx+C=3x+C$
C учетом $f_{3,2}(2)=f_{3,1}(2)$ получим $C=10$
$f_{3,3}(x)=Prem\left( \begin{array}{ccc} 1 & 1& 1\\ 1 & 2 &2 \\ 1 & 2 &3 \end{array}\right)=f_{3,2}(3)=19$