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

Author

Henry Bottomley, Feb 05 2001

Keywords

• easy
• nonn

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

Examples

			a(4) = 124 since the binary sum 11110 + 11101 + 11011 + 10111 + 01111 is 30 + 29 + 27 + 23 + 15.
		

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).

Crossrefs

Cf. A058922.

Programs

Magma

[n*(2^(n+1)-1): n in [0..35]]; // Vincenzo Librandi, Jul 23 2011

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 *)

PARI

a(n) =2*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

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