login
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
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
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
KEYWORD
nonn
AUTHOR
Stefano Spezia, Nov 02 2021
STATUS
approved