|
%I #56 Sep 08 2022 08:45:03
%S 0,3,14,45,124,315,762,1785,4088,9207,20470,45045,98292,212979,458738,
%T 983025,2097136,4456431,9437166,19922925,41943020,88080363,184549354,
%U 385875945,805306344,1677721575,3489660902,7247757285,15032385508
%N Sum of binary numbers with n 1's and one (possibly leading) 0.
%C 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
%D Herbert John Ryser, Combinatorial Mathematics, volume 14 of Carus Mathematical Monographs. American Mathematical Soc., (1963), pp. 24-28.
%H Vincenzo Librandi, <a href="/A059672/b059672.txt">Table of n, a(n) for n = 0..1000</a>
%H 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. See Table 1 p. 3.
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (6,-13,12,-4).
%F a(n) = n*(2^(n+1)-1) = A058922(n+1) - n.
%F G.f.: x*(3-4*x)/((1-x)^2*(1-2*x)^2). - _Colin Barker_, Mar 21 2012
%F a(n) = Sum_{k=0..n} Sum_{i=0..n} C(n+1,i) - C(k,i). - _Wesley Ivan Hurt_, Sep 21 2017
%F E.g.f.: x*exp(x)*(4*exp(x) - 1). - _Stefano Spezia_, Oct 25 2021
%e a(4)=124 since the binary sum 11110+11101+11011+10111+01111 is 30+29+27+23+15.
%t A059672[n_Integer] := n*(2^(n + 1) - 1); Table[A059672[n], {n,0,40}] (* _Vladimir Joseph Stephan Orlovsky_, Jul 22 2011 *)
%t LinearRecurrence[{6,-13,12,-4},{0,3,14,45},40] (* _Harvey P. Dale_, Aug 30 2016 *)
%o (Magma) [n*(2^(n+1)-1): n in [0..35]]; // _Vincenzo Librandi_, Jul 23 2011
%o (PARI) a(n) =2*n<<n-n \\ _Charles R Greathouse IV_, Mar 21 2012
%o (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
%Y Cf. A058922.
%K easy,nonn
%O 0,2
%A _Henry Bottomley_, Feb 05 2001
|
