|
|
A059672
|
|
Sum of binary numbers with n 1's and one (possibly leading) 0.
|
|
5
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
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
|
LinearRecurrence[{6, -13, 12, -4}, {0, 3, 14, 45}, 40] (* Harvey P. Dale, Aug 30 2016 *)
|
|
PROG
|
(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,changed
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|