login
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
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
Han Mao Kiah, Alexander Vardy and Hanwen Yao, Computing Permanents on a Trellis, arXiv:2107.07377 [cs.IT], 2021. See Table 1 p. 3.
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
KEYWORD
nonn,easy
AUTHOR
Stefano Spezia, Oct 25 2021
STATUS
approved