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

References

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

Links

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

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).

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).

Mathematica

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

Crossrefs

Cf. A000079, A000337, A059672, A160457.

Sequence in context: A280434 A163697 A134424 * A277794 A292126 A174797

Adjacent sequences: A348618 A348619 A348620 * A348622 A348623 A348624

Keyword

nonn,easy

Author

Stefano Spezia, Oct 25 2021

Status

approved