cp's OEIS Frontend

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

%I A196724 #24 Oct 07 2020 12:42:24
%S A196724 1,2,4,8,16,32,58,116,212,416,720,1440,2340,4680,7920,13024,23328,
%T A196724 46656,74168,148336,229856,371424,615304,1230608,1780224,3401568,
%U A196724 5589360,9468504,14397744,28795488,40312128,80624256,131388480,206363168,335814288,521401536
%N A196724 Number of subsets of {1..n} (including empty set) such that the pairwise products of distinct elements are all distinct.
%C A196724 The number of subsets of {1..n} such that every orderless pair of (not necessarily distinct) elements has a different product is A325860(n). - _Gus Wiseman_, Jun 03 2019
%H A196724 Fausto A. C. Cariboni, <a href="/A196724/b196724.txt">Table of n, a(n) for n = 0..50</a>
%e A196724 a(6) = 58: from the 2^6=64 subsets of {1,2,3,4,5,6} only 6 do not have all the pairwise products of elements distinct: {1,2,3,6}, {2,3,4,6}, {1,2,3,4,6}, {1,2,3,5,6}, {2,3,4,5,6}, {1,2,3,4,5,6}.
%p A196724 b:= proc(n, s) local sn, m;
%p A196724       m:= nops(s);
%p A196724       sn:= [s[], n];
%p A196724       `if`(n<1, 1, b(n-1, s) +`if`(m*(m+1)/2 = nops(({seq(seq(
%p A196724        sn[i]*sn[j], j=i+1..m+1), i=1..m)})), b(n-1, sn), 0))
%p A196724     end:
%p A196724 a:= proc(n) option remember;
%p A196724       b(n-1, [n]) +`if`(n=0, 0, a(n-1))
%p A196724     end:
%p A196724 seq(a(n), n=0..20);
%t A196724 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[ 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[a[n], {n, 0, 20}] (* _Jean-François Alcover_, Jan 31 2017, translated from Maple *)
%t A196724 Table[Length[Select[Subsets[Range[n]],UnsameQ@@Times@@@Subsets[#,{2}]&]],{n,0,10}] (* _Gus Wiseman_, Jun 03 2019 *)
%Y A196724 Cf. A143823, A196719, A196720, A196721, A196722, A196723.
%Y A196724 The subset case is A196724 (this sequence).
%Y A196724 The maximal case is A325859.
%Y A196724 The integer partition case is A325856.
%Y A196724 The strict integer partition case is A325855.
%Y A196724 Heinz numbers of the counterexamples are given by A325993.
%Y A196724 Cf. A292886, A293627, A325860, A325861.
%K A196724 nonn
%O A196724 0,2
%A A196724 _Alois P. Heinz_, Oct 06 2011
%E A196724 Name edited by _Gus Wiseman_, Jun 03 2019
%E A196724 a(33)-a(35) from _Fausto A. C. Cariboni_, Oct 05 2020