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,2

Links

Table of n, a(n) for n=1..33.

Han Mao Kiah, Alexander Vardy and Hanwen Yao, Computing Permanents on a Trellis, arXiv:2107.07377 [cs.IT], 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

Mathematica

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

Prog

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

Crossrefs

Cf. A001787, A002378, A058877, A100071.

Sequence in context: A066150 A233458 A335687 * A133212 A233447 A127811

Adjacent sequences: A348861 A348862 A348863 * A348865 A348866 A348867

Keyword

nonn

Author

Stefano Spezia, Nov 02 2021

Status

approved