login
Sum of binary numbers with n 1's and one (possibly leading) 0.
5

%I #58 May 04 2024 11:46:32

%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

%F a(n) = 6*a(n-1) - 13*a(n-2) + 12*a(n-3) - 4*a(n-4). - _Wesley Ivan Hurt_, May 04 2024

%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