A196721 Number of subsets of {1..n} (including empty set) such that the pairwise LCMs of elements are all distinct.

1, 2, 4, 8, 14, 28, 42, 84, 132, 236, 352, 704, 920, 1840, 2736, 3816, 5700, 11400, 15384, 30768, 39552, 54656, 81672, 163344, 196176, 362656, 542304, 930352, 1195168, 2390336, 2914304, 5828608, 8513920, 11674848, 17490432, 23484224, 28058816, 56117632, 84100800

Offset

0,2

Links

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..50

Example

a(4) = 14: {}, {1}, {2}, {3}, {4}, {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}, {1,2,3}, {1,3,4}, {2,3,4}.

Maple

b:= proc(n, s) local sn, m;
      m:= nops(s);
      sn:= [s[], n];
      `if`(n<1, 1, b(n-1, s) +`if`(m*(m+1)/2 = nops(({seq(seq(
       ilcm(sn[i], sn[j]), j=i+1..m+1), i=1..m)})), b(n-1, sn), 0))
    end:
a:= proc(n) option remember;
      b(n-1, [n]) +`if`(n=0, 0, a(n-1))
    end:
seq(a(n), n=0..10);

Mathematica

b[n_, s_] := b[n, s] = Module[{sn, m}, m = Length[s]; sn = Append[s, n]; If[n < 1, 1, b[n - 1, s] + If[m*(m + 1)/2 == Length @ Union @ Flatten @ Table[LCM [sn[[i]], sn[[j]]], {i, 1, m}, {j, i+1, m+1}], b[n-1, sn], 0]]]; a[n_] := a[n] = b[n-1, {n}] + If[n == 0, 0, a[n-1]]; Table[ Print["a(", n, ") = ", a[n]]; a[n], {n, 0, 30}] (* Jean-François Alcover, Feb 02 2017, translated from Maple *)

Crossrefs

Cf. A143823, A196719, A196720, A196722, A196723, A196724.

Sequence in context: A321402 A210669 A122026 * A118034 A096590 A068912

Adjacent sequences: A196718 A196719 A196720 * A196722 A196723 A196724

Keyword

nonn

Author

Alois P. Heinz, Oct 05 2011

Extensions

Terms a(31) and beyond from Fausto A. C. Cariboni, Oct 18 2020

Status

approved