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
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
KEYWORD
nonn,easy
AUTHOR
Derek Orr, Nov 23 2014
STATUS
approved