cp's OEIS Frontend

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

%I A348864 #11 Mar 06 2022 08:33:16
%S A348864 0,4,12,32,70,162,350,800,1746,3950,8602,19164,41392,90846,194490,
%T A348864 421568,895594,1922022,4057298,8638580,18140640,38378054,80244562,
%U A348864 168877272,351827100,737208082,1531123830,3196464740,6621247636,13779365430,28477354354,59102191488,121898268954
%N A348864 a(n) is the number of multiplications required to compute the permanent of general n X n matrices using trellis method with normalization.
%H A348864 Han Mao Kiah, Alexander Vardy and Hanwen Yao, <a href="https://arxiv.org/abs/2107.07377">Computing Permanents on a Trellis</a>, arXiv:2107.07377 [cs.IT], 2021.
%F A348864 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.).
%F A348864 a(n) = A001787(n) - A100071(n) + A002378(n-1).
%F A348864 O.g.f.: x*(1/(1 - 2*x)^2 + 2*x/(1 - x)^3 - 1/((1 - 2*x)*sqrt(1 - 4*x^2))).
%F A348864 E.g.f.: exp(x)*x*(exp(x) + x) - (1 + x)*BesselI(1, 2*x) - x*BesselI(2, 2*x).
%F A348864 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
%t A348864 a[n_]:=n 2^(n-1)-Ceiling[n/2]Binomial[n,Floor[n/2]]+n^2-n; Array[a,33]
%o A348864 (PARI) a(n) = n*2^(n-1) - ceil(n/2)*binomial(n, floor(n/2)) + n^2 - n; \\ _Michel Marcus_, Nov 03 2021
%Y A348864 Cf. A001787, A002378, A058877, A100071.
%K A348864 nonn
%O A348864 1,2
%A A348864 _Stefano Spezia_, Nov 02 2021