A348621 The number of additions required to compute the permanent of general n X n matrices using Ryser's formula without Gray code ordering.

0, 4, 21, 82, 275, 836, 2373, 6406, 16647, 41992, 103433, 249866, 593931, 1392652, 3227661, 7405582, 16842767, 38010896, 85196817, 189792274, 420478995, 926941204, 2034237461, 4445962262, 9680453655, 21005074456, 45432700953, 97978941466, 210721832987, 452045307932

Offset: 1

Author

Stefano Spezia, Oct 25 2021

Keywords

• nonn
• easy

References

• Herbert John Ryser, Combinatorial Mathematics, volume 14 of Carus Mathematical Monographs. American Mathematical Soc., (1963), pp. 24-28.

Links

• Han Mao Kiah, Alexander Vardy and Hanwen Yao, Computing Permanents on a Trellis, arXiv:2107.07377 [cs.IT], 2021. See Table 1 p. 3.
• Index entries for linear recurrences with constant coefficients, signature (8,-25,38,-28,8).

Crossrefs

Cf. A000079, A000337, A059672, A160457.

Programs

Mathematica

LinearRecurrence[{8,-25,38,-28,8},{0,4,21,82,275},30]

Formula

a(n) = (n^2 - 2*n + 2)*2^(n-1) + n - 2.

a(n) = n*A000337(n-1) + A000079(n) - 2.

a(n) = 8*a(n-1) - 25*a(n-2) + 38*a(n-3) - 28*a(n-4) + 8*a(n-5) for n > 5.

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

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