A348864 a(n) is the number of multiplications required to compute the permanent of general n X n matrices using trellis method with normalization.

0, 4, 12, 32, 70, 162, 350, 800, 1746, 3950, 8602, 19164, 41392, 90846, 194490, 421568, 895594, 1922022, 4057298, 8638580, 18140640, 38378054, 80244562, 168877272, 351827100, 737208082, 1531123830, 3196464740, 6621247636, 13779365430, 28477354354, 59102191488, 121898268954

Offset: 1

Author

Stefano Spezia, Nov 02 2021

Keywords

• nonn

Links

• Han Mao Kiah, Alexander Vardy and Hanwen Yao, Computing Permanents on a Trellis, arXiv:2107.07377 [cs.IT], 2021.

Crossrefs

Cf. A001787, A002378, A058877, A100071.

Programs

Mathematica

a[n_]:=n 2^(n-1)-Ceiling[n/2]Binomial[n,Floor[n/2]]+n^2-n; Array[a,33]

PARI

a(n) = n*2^(n-1) - ceil(n/2)*binomial(n, floor(n/2)) + n^2 - n; \\ Michel Marcus, Nov 03 2021

Formula

a(n) = n*2^(n-1) - ceiling(n/2)*binomial(n, floor(n/2)) + n^2 - n (see Theorem 6, p. 11 in Kiah et al.).

a(n) = A001787(n) - A100071(n) + A002378(n-1).

O.g.f.: x*(1/(1 - 2*x)^2 + 2*x/(1 - x)^3 - 1/((1 - 2*x)*sqrt(1 - 4*x^2))).

E.g.f.: exp(x)*x*(exp(x) + x) - (1 + x)*BesselI(1, 2*x) - x*BesselI(2, 2*x).

D-finite with recurrence (n-1)*(n-2)*(n-4)*(3*n-23)*a(n) -3*(n -2)*(3*n^3-34*n^2+91*n-20)*a(n-1) -2*(n-1)*(n-3)*(3*n^2 -47*n+164)*a(n-2) +12*(3*n-22)*(n-1)*(n-2)*(n-4)*a(n-3) -8*(3*n-20)*(n-1)*(n-2)*(n-3)*a(n-4)=0. - R. J. Mathar, Mar 06 2022