login
A247188
a(0) = 0. a(n) is the number of repeating sums in the collection of all sums of any k elements in [a(0), ... a(n-1)] chosen without replacement for 2 <= k <= n.
0
0, 0, 0, 3, 9, 22, 49, 104, 215, 438, 885, 1780, 3571, 7154, 14321, 28656, 57327, 114670, 229357, 458732, 917483, 1834986, 3669993, 7340008, 14680039, 29360102, 58720229, 117440484, 234880995, 469762018, 939524065, 1879048160, 3758096351, 7516192734, 15032385501, 30064771036, 60129542107
OFFSET
0,4
COMMENTS
Without replacement means that a(i)+a(i) is not a valid sum to include. However, if a(i) = a(j), a(i)+a(j) is still a valid sum to include because they have different indices.
a(n) <= A000295(n).
FORMULA
a(n) = 2^n - n - 1 - 2^(n-3) = A000295(n) - 2^(n-3), for n >= 3.
G.f.: x^3*(3-3*x+x^2)/((1-2*x)(1-x)^2). - Vincenzo Librandi, Nov 23 2014
EXAMPLE
a(1) gives the number of repeating sums in the collection of all possible sums of two elements in [0]. There are no sums between two elements here, so a(1) = 0.
a(2) gives the number of repeating sums in the collection of all possible sums of the two elements in [0,0]. There is only one sum, 0, thus there are no repeats. So a(2) = 0.
a(3) gives the number of repeating sums in the collection of all possible sums of any number of elements in [0,0,0]. The possible sums are 0+0, 0+0, 0+0, or 0+0+0, thus there are 3 repeats. So a(3) = 3.
a(4) gives the number of repeating sums in the collection of all possible sums of any number of elements in [0,0,0,3]. The possible sums are 0+0, 0+0, 0+3, 0+0, 0+3, 0+3, 0+0+0, 0+0+3, 0+0+3, 0+0+3, and 0+0+0+3. There are 9 repeating sums. So a(4) = 9.
MATHEMATICA
CoefficientList[Series[x^3 (3 - 3 x + x^2) / ((1 - 2 x) (1 - x)^2), {x, 0, 40}], x] (* Vincenzo Librandi, Nov 23 2014 *)
PROG
(PARI) concat([0, 0, 0], vector(50, n, 2^(n+2)-n-3-2^(n-1)))
(Magma) [0, 0, 0] cat [2^n-n-1-2^(n-3): n in [3..50]]; // Vincenzo Librandi, Nov 23 2014
CROSSREFS
Cf. A000295.
Sequence in context: A187053 A001937 A086817 * A000715 A260545 A034505
KEYWORD
nonn,easy
AUTHOR
Derek Orr, Nov 23 2014
STATUS
approved