|
%I #21 Jul 04 2023 11:55:26
%S 0,0,0,3,9,22,49,104,215,438,885,1780,3571,7154,14321,28656,57327,
%T 114670,229357,458732,917483,1834986,3669993,7340008,14680039,
%U 29360102,58720229,117440484,234880995,469762018,939524065,1879048160,3758096351,7516192734,15032385501,30064771036,60129542107
%N 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.
%C 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.
%C a(n) <= A000295(n).
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (4, -5, 2).
%F a(n) = 2^n - n - 1 - 2^(n-3) = A000295(n) - 2^(n-3), for n >= 3.
%F G.f.: x^3*(3-3*x+x^2)/((1-2*x)(1-x)^2). - _Vincenzo Librandi_, Nov 23 2014
%e 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.
%e 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.
%e 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.
%e 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.
%t CoefficientList[Series[x^3 (3 - 3 x + x^2) / ((1 - 2 x) (1 - x)^2), {x, 0, 40}], x] (* _Vincenzo Librandi_, Nov 23 2014 *)
%o (PARI) concat([0,0,0],vector(50,n,2^(n+2)-n-3-2^(n-1)))
%o (Magma) [0,0,0] cat [2^n-n-1-2^(n-3): n in [3..50]]; // _Vincenzo Librandi_, Nov 23 2014
%Y Cf. A000295.
%K nonn,easy
%O 0,4
%A _Derek Orr_, Nov 23 2014
|
