OFFSET
0,2
COMMENTS
a(n-1) is also the number of multiplications required to compute the permanent of general n X n matrices using Ryser's formula (see Kiah et al.). - Stefano Spezia, Oct 25 2021
REFERENCES
Herbert John Ryser, Combinatorial Mathematics, volume 14 of Carus Mathematical Monographs. American Mathematical Soc., (1963), pp. 24-28.
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..1000
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 (6,-13,12,-4).
FORMULA
a(n) = n*(2^(n+1)-1) = A058922(n+1) - n.
G.f.: x*(3-4*x)/((1-x)^2*(1-2*x)^2). - Colin Barker, Mar 21 2012
a(n) = Sum_{k=0..n} Sum_{i=0..n} C(n+1,i) - C(k,i). - Wesley Ivan Hurt, Sep 21 2017
E.g.f.: x*exp(x)*(4*exp(x) - 1). - Stefano Spezia, Oct 25 2021
a(n) = 6*a(n-1) - 13*a(n-2) + 12*a(n-3) - 4*a(n-4). - Wesley Ivan Hurt, May 04 2024
EXAMPLE
a(4) = 124 since the binary sum 11110 + 11101 + 11011 + 10111 + 01111 is 30 + 29 + 27 + 23 + 15.
MATHEMATICA
A059672[n_Integer] := n*(2^(n + 1) - 1); Table[A059672[n], {n, 0, 40}] (* Vladimir Joseph Stephan Orlovsky, Jul 22 2011 *)
LinearRecurrence[{6, -13, 12, -4}, {0, 3, 14, 45}, 40] (* Harvey P. Dale, Aug 30 2016 *)
PROG
(Magma) [n*(2^(n+1)-1): n in [0..35]]; // Vincenzo Librandi, Jul 23 2011
(PARI) a(n) =2*n<<n-n \\ Charles R Greathouse IV, Mar 21 2012
(PARI) x='x+O('x^99); concat(0, Vec(x*(3-4*x)/((1-x)^2*(1-2*x)^2))) \\ Altug Alkan, Apr 09 2016
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Henry Bottomley, Feb 05 2001
STATUS
approved