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

0, 3, 14, 45, 124, 315, 762, 1785, 4088, 9207, 20470, 45045, 98292, 212979, 458738, 983025, 2097136, 4456431, 9437166, 19922925, 41943020, 88080363, 184549354, 385875945, 805306344, 1677721575, 3489660902, 7247757285, 15032385508

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

Cf. A058922.

Sequence in context: A115005 A058389 A261481 * A302225 A032316 A032225

Adjacent sequences: A059669 A059670 A059671 * A059673 A059674 A059675

Keyword

easy,nonn,changed

Author

Henry Bottomley, Feb 05 2001

Status

approved