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

Links

Table of n, a(n) for n=0..36.

Index entries for linear recurrences with constant coefficients, signature (4, -5, 2).

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

Adjacent sequences: A247185 A247186 A247187 * A247189 A247190 A247191

Keyword

nonn,easy

Author

Derek Orr, Nov 23 2014

Status

approved