A241688 Number of Sidon subsets of {1,...,n} of size 4.

0, 0, 0, 0, 0, 0, 2, 10, 26, 60, 110, 190, 304, 466, 676, 958, 1312, 1762, 2310, 2984, 3786, 4750, 5874, 7196, 8720, 10484, 12488, 14780, 17360, 20276, 23530, 27174, 31210, 35696, 40630, 46074, 52032, 58566, 65676, 73434, 81840, 90966, 100814, 111460, 122906

Offset: 1

Author

Carl Najafi, Apr 27 2014

Keywords

• nonn

Comments

A Sidon set is a set of natural numbers A={a_1,a_2,...}, finite or infinite, such that all pairwise sums a_i+a_j (i <= j) are different.

Examples

			a(7)=2 since the only subsets of {1,...,7} satisfying the required conditions are {1,2,5,7} and {1,3,6,7}.
		

Links

• Index entries for linear recurrences with constant coefficients, signature (2, 0, -1, 0, -2, 2, 0, 1, 0, -2, 1).

Crossrefs

Column k=4 of A381476.

Cf. A054578.

Programs

Mathematica

SidonQ[l__] := If[Length[Join[Plus @@@ Subsets[l, {2}], 2 l]] == Length[Union[Join[Plus @@@ Subsets[l, {2}], 2 l]]], True, False]
Table[Length@Select[Subsets[Range[n], {4}], SidonQ[#] &], {n, 1, 30}]

Formula

It appears to be the case that G.f.: 2*x^7*(1+3*x+3*x^2+5*x^3)/((1-x)^5*(1+x)^2*(1+x^2)*(1+x+x^2)), corrected by Vaclav Kotesovec, May 03 2014

a(n) ~ 1/24*n^4 (deduced from g.f.). - Ralf Stephan, Apr 29 2014

a(n) = a(n-11)+a(n-8)-a(n-3)+2*(a(n-6)+a(n-1)-a(n-10)-a(n-5)). - Fung Lam, May 02 2014

Explicit formula (derived from g.f.): a(n) = n^4/24 - 7*n^3/12 + 29*n^2/12 - 15*n/8 - floor(n/4) - 4/3*floor(n/3) + (n/2-9/4)*floor(n/2) - floor((n+1)/4) - 2/3*floor((n+1)/3). - Vaclav Kotesovec, May 03 2014