login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A143823 Number of subsets {x(1),x(2),...,x(k)} of {1,2,...,n} such that all differences |x(i)-x(j)| are distinct. 62
1, 2, 4, 7, 13, 22, 36, 57, 91, 140, 216, 317, 463, 668, 962, 1359, 1919, 2666, 3694, 5035, 6845, 9188, 12366, 16417, 21787, 28708, 37722, 49083, 63921, 82640, 106722, 136675, 174895, 222558, 283108, 357727, 451575, 567536, 712856, 890405, 1112081, 1382416, 1717540 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

See A143824 for sizes of the largest subsets of {1,2,...,n} with the desired property.

a(n) = A169947(n-1) + n + 1 for n>=2.

a(n) = A054578(n) + 1 for n>0. - Alois P. Heinz, Jan 17 2013

Also the number of subsets of {1..n} such that every orderless pair of (not necessarily distinct) elements has a different sum. - Gus Wiseman, Jun 07 2019

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..60

EXAMPLE

{1,2,4} is a subset of {1,2,3,4}, with distinct differences 2-1=1, 4-1=3, 4-2=2 between pairs of elements, so {1,2,4} is counted as one of the 13 subsets of {1,2,3,4} with the desired property.  Only 2^4-13=3 subsets of {1,2,3,4} do not have this property: {1,2,3}, {2,3,4}, {1,2,3,4}.

From Gus Wiseman, May 17 2019: (Start)

The a(0) = 1 through a(5) = 22 subsets:

  {}  {}   {}     {}     {}       {}

      {1}  {1}    {1}    {1}      {1}

           {2}    {2}    {2}      {2}

           {1,2}  {3}    {3}      {3}

                  {1,2}  {4}      {4}

                  {1,3}  {1,2}    {5}

                  {2,3}  {1,3}    {1,2}

                         {1,4}    {1,3}

                         {2,3}    {1,4}

                         {2,4}    {1,5}

                         {3,4}    {2,3}

                         {1,2,4}  {2,4}

                         {1,3,4}  {2,5}

                                  {3,4}

                                  {3,5}

                                  {4,5}

                                  {1,2,4}

                                  {1,2,5}

                                  {1,3,4}

                                  {1,4,5}

                                  {2,3,5}

                                  {2,4,5}

(End)

MAPLE

b:= proc(n, s) local sn, m;

      if n<1 then 1

    else sn:= [s[], n];

         m:= nops(sn);

         `if`(m*(m-1)/2 = nops(({seq(seq(sn[i]-sn[j],

           j=i+1..m), i=1..m-1)})), b(n-1, sn), 0) +b(n-1, s)

      fi

    end:

a:= proc(n) option remember;

       b(n-1, [n]) +`if`(n=0, 0, a(n-1))

    end:

seq(a(n), n=0..30);  # Alois P. Heinz, Sep 14 2011

MATHEMATICA

b[n_, s_] := Module[{ sn, m}, If[n<1, 1, sn = Append[s, n]; m = Length[sn]; If[m*(m-1)/2 == Length[Table[sn[[i]] - sn[[j]], {i, 1, m-1}, {j, i+1, m}] // Flatten // Union], b[n-1, sn], 0] + b[n-1, s]]]; a[n_] := a[n] = b[n - 1, {n}] + If[n == 0, 0, a[n-1]]; Table [a[n], {n, 0, 30}] (* Jean-Fran├žois Alcover, Nov 08 2015, after Alois P. Heinz *)

Table[Length[Select[Subsets[Range[n]], UnsameQ@@Abs[Subtract@@@Subsets[#, {2}]]&]], {n, 0, 15}] (* Gus Wiseman, May 17 2019 *)

CROSSREFS

First differences are A308251.

Second differences are A169942.

The subset case is A143823 (this sequence).

The maximal case is A325879.

The integer partition case is A325858.

The strict integer partition case is A325876.

Heinz numbers of the counterexamples are given by A325992.

Cf. A143824, A054578, A169947.

Cf. A000079, A108917, A143824, A169942, A308251, A325676, A325677, A325679, A325683, A325860, A325864.

Sequence in context: A061255 A088111 A325864 * A119983 A151897 A192758

Adjacent sequences:  A143820 A143821 A143822 * A143824 A143825 A143826

KEYWORD

nonn

AUTHOR

John W. Layman, Sep 02 2008

EXTENSIONS

a(21)-a(29) and connection to A169947 from Nathaniel Johnston, Nov 12 2010

Corrected a(21)-a(29) and more terms from Alois P. Heinz, Sep 14 2011

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 20 23:38 EDT 2019. Contains 326155 sequences. (Running on oeis4.)