Displaying 1-10 of 15 results found.
Number of subsets {x(1),x(2),...,x(k)} of {1,2,...,n} such that all differences |x(i)-x(j)| are distinct.
+10
70
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
COMMENTS
When the set {x(1),x(2),...,x(k)} satisfies the property that all differences |x(i)-x(j)| are distinct (or alternately, all the sums are distinct), then it is called a Sidon set. So this sequence is basically the number of Sidon subsets of {1,2,...,n}. - Sayan Dutta, Feb 15 2024 See A143824 for sizes of the largest subsets of {1,2,...,n} with the desired property. 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
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}.
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:
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 *)
PROG
(Python)
from itertools import combinations
def is_sidon_set(s):
allsums = []
for i in range(len(s)):
for j in range(i, len(s)):
allsums.append(s[i] + s[j])
if len(allsums)==len(set(allsums)):
return True
return False
def a(n):
sidon_count = 0
for r in range(n + 1):
subsets = combinations(range(1, n + 1), r)
for subset in subsets:
if is_sidon_set(subset):
sidon_count += 1
return sidon_count
print([a(n) for n in range(20)]) # Sayan Dutta, Feb 15 2024 (Python)
from functools import cache
def b(n, s):
if n < 1: return 1
sn = s + [n]
m = len(sn)
return (b(n-1, sn) if m*(m-1)//2 == len(set(sn[i]-sn[j] for i in range(m-1) for j in range(i+1, m))) else 0) + b(n-1, s)
@cache
def a(n): return b(n-1, [n]) + (0 if n==0 else a(n-1))
CROSSREFS
The subset case is A143823 (this sequence). The integer partition case is A325858. The strict integer partition case is A325876. Heinz numbers of the counterexamples are given by A325992. Cf. A000079, A108917, A143824, A169942, A308251, A325676, A325677, A325679, A325683, A325860, A325864, A241688, A241689, A241690.
Length of shortest (or optimal) Golomb ruler with n marks.
(Formerly M2540)
+10
49
1, 3, 6, 11, 17, 25, 34, 44, 55, 72, 85, 106, 127, 151, 177, 199, 216, 246, 283, 333, 356, 372, 425, 480, 492, 553, 585
COMMENTS
a(n) is the least integer such that there is an n-element set of integers between 0 and a(n), the sums of pairs (of not necessarily distinct elements) of which are distinct.
An n-mark Golomb ruler has a unique integer distance between any pair of marks and thus measures n(n-1)/2 distinct integer distances.
An optimal n-mark Golomb ruler has the smallest possible length (distance between the two end marks) for an n-mark ruler.
A perfect n-mark Golomb ruler has length exactly n(n-1)/2 and measures each distance from 1 to n(n-1)/2. (End)
Also the smallest m such that there exists a length-n composition of m for which every restriction to a subinterval has a different sum. Representatives of compositions for the first few terms are:
0: ()
1: (1)
3: (2,1)
6: (2,3,1)
11: (3,1,5,2)
17: (4,2,3,7,1)
Representatives of corresponding Golomb rulers are:
{0}
{0,1}
{0,2,3}
{0,2,5,6}
{0,3,4,9,11}
{0,4,6,9,16,17}
(End)
REFERENCES
CRC Handbook of Combinatorial Designs, 1996, p. 315.
A. K. Dewdney, Computer Recreations, Scientific Amer. 253 (No. 6, Jun), 1985, pp. 16ff; 254 (No. 3, March), 1986, pp. 20ff.
S. W. Golomb, How to number a graph, pp. 23-37 of R. C. Read, editor, Graph Theory and Computing. Academic Press, NY, 1972.
Richard K. Guy, Unsolved Problems in Number Theory (2nd edition), Springer-Verlag (1994), Section C10.
A. Kotzig and P. J. Laufer, Sum triangles of natural numbers having minimum top, Ars. Combin. 21 (1986), 5-13.
Miller, J. C. P., Difference bases. Three problems in additive number theory. Computers in number theory (Proc. Sci. Res. Council Atlas Sympos. No. 2, Oxford, 1969), pp. 299--322. Academic Press, London,1971. MR0316269 (47 #4817)
Rhys Price Jones, Gracelessness, Proc. 10th S.-E. Conf. Combin., Graph Theory and Computing, 1979, pp. 547-552.
Ana Salagean, David Gardner and Raphael Phan, Index Tables of Finite Fields and Modular Golomb Rulers, in Sequences and Their Applications - SETA 2012, Lecture Notes in Computer Science. Volume 7280, 2012, pp. 136-147.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
A. K. Dewdney, Computer Recreations, Scientific Amer. 253 (No. 6, Jun), 1985, pp. 16ff; 254 (No. 3, March), 1986, pp. 20ff. [Annotated scanned copy]
FORMULA
a(n) >= n(n-1)/2, with strict inequality for n >= 5 (Golomb). - David W. Wilson, Aug 18 2007
EXAMPLE
a(5)=11 because 0-1-4-9-11 (0-2-7-10-11) resp. 0-3-4-9-11 (0-2-7-8-11) are shortest: there is no b0-b1-b2-b3-b4 with different distances |bi-bj| and max. |bi-bj| < 11.
MATHEMATICA
Min@@Total/@#&/@GatherBy[Select[Join@@Permutations/@Join@@Table[IntegerPartitions [i], {i, 0, 15}], UnsameQ@@ReplaceList[#, {___, s__, ___}:>Plus[s]]&], Length] (* Gus Wiseman, May 17 2019 *)
CROSSREFS
0-1-4-9-11 corresponds to 1-3-5-2 in A039953: 0+1+3+5+2=11 A row or column of array in A234943.
EXTENSIONS
a(25), a(26) proved by OGR-25 and OGR-26 projects, added by Max Alekseyev, Sep 29 2010
Number of Golomb rulers of length n.
+10
49
1, 1, 3, 3, 5, 7, 13, 15, 27, 25, 45, 59, 89, 103, 163, 187, 281, 313, 469, 533, 835, 873, 1319, 1551, 2093, 2347, 3477, 3881, 5363, 5871, 8267, 9443, 12887, 14069, 19229, 22113, 29359, 32229, 44127, 48659, 64789, 71167, 94625, 105699, 139119, 151145, 199657
COMMENTS
Wanted: a recurrence. Are any of A169940- A169954 related to any other entries in the OEIS? Leading entry in row n of triangle in A169940. Also the number of Sidon sets A with min(A) = 0 and max(A) = n. Odd for all n since {0,n} is the only symmetric Golomb ruler, and reversal preserves the Golomb property. Bounded from above by A032020 since the ruler {0 < r_1 < ... < r_t < n} gives rise to a composition of n: (r_1 - 0, r_2 - r_1, ... , n - r_t) with distinct parts. - Tomas Boothby, May 15 2012 Also the number of compositions of n such that every restriction to a subinterval has a different sum. This is a stronger condition than all distinct consecutive subsequences having a different sum (cf. A325676). - Gus Wiseman, May 16 2019
EXAMPLE
For n=2, there is one Golomb Ruler: {0,2}. For n=3, there are three: {0,3}, {0,1,3}, {0,2,3}. - Tomas Boothby, May 15 2012 The a(1) = 1 through a(8) = 15 compositions such that every restriction to a subinterval has a different sum:
(1) (2) (3) (4) (5) (6) (7) (8)
(12) (13) (14) (15) (16) (17)
(21) (31) (23) (24) (25) (26)
(32) (42) (34) (35)
(41) (51) (43) (53)
(132) (52) (62)
(231) (61) (71)
(124) (125)
(142) (143)
(214) (152)
(241) (215)
(412) (251)
(421) (341)
(512)
(521)
(End)
MATHEMATICA
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], UnsameQ@@ReplaceList[#, {___, s__, ___}:>Plus[s]]&]], {n, 15}] (* Gus Wiseman, May 16 2019 *)
PROG
(Sage)
R = QQ['x']
return sum(1 for c in cartesian_product([[0, 1]]*n) if max(R([1] + list(c) + [1])^2) == 2)
CROSSREFS
Cf. A000079, A103295, A103300, A108917, A143824, A325466, A325545, A325676, A325678, A325679, A325683, A325686.
Size of the largest subset of the numbers [1...n] which does not contain a 3-term arithmetic progression.
(Formerly M0275)
+10
32
0, 1, 2, 2, 3, 4, 4, 4, 4, 5, 5, 6, 6, 7, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 10, 10, 11, 11, 11, 11, 12, 12, 13, 13, 13, 13, 14, 14, 14, 14, 15, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 18, 18, 18, 18, 19, 19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 20, 20, 21, 21, 21, 22, 22, 22, 22
COMMENTS
"Sequences containing no 3-term arithmetic progressions" is another phrase people may be searching for.
a(n) = size of largest subset of [1..n] such that no term is the average of any two others. These are also called non-averaging sets, or 3-free sequences. - N. J. A. Sloane, Mar 01 2012
REFERENCES
H. L. Abbott, On a conjecture of Erdos and Straus on non-averaging sets of integers, Proc. 5th British Combinatorial Conference, 1975, pp. 1-4.
Bloom, T. F. (2014). Quantitative results in arithmetic combinatorics (Doctoral dissertation, University of Bristol).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
E. G. Straus, Nonaveraging sets. In Combinatorics (Proc. Sympos. Pure Math., Vol. XIX, Univ. California, Los Angeles, Calif., 1968), pp. 215-222. Amer. Math. Soc., Providence, R.I., 1971. MR0316255 (47 #4803)
T. Tao and V. Vu, Additive Combinatorics, Problem 10.1.3.
LINKS
Irene Choi, Shreyas Ekanathan, Aidan Gao, Tanya Khovanova, Sylvia Zia Lee, Rajarshi Mandal, Vaibhav Rastogi, Daniel Sheffield, Michael Yang, Angela Zhao, and Corey Zhao, The Struggles of Chessland, arXiv:2212.01468 [math.HO], 2022. P. Erdõs and E. G. Straus, Nonaveraging sets II, In Combinatorial theory and its applications, II (Proc. Colloq., Balatonfüred, 1969), pp. 405-411. North-Holland, Amsterdam, 1970. MR0316256 (47 #4804). N. J. A. Sloane, New Gilbreath Conjectures, Sum and Erase, Dissecting Polygons, and Other New Sequences, Doron Zeilberger's Exper. Math. Seminar, Rutgers, Sep 14 2023: Video, Slides, Updates. (Mentions this sequence.)
EXAMPLE
Examples from Dybizbanski (2012) (includes earlier examples found by other people):
n, a(n), example of an optimal subset:
0, 0, []
1, 1, [1]
2, 2, [1, 2]
4, 3, [1, 2, 4]
5, 4, [1, 2, 4, 5]
9, 5, [1, 2, 4, 8, 9]
11, 6, [1, 2, 4, 5, 10, 11]
13, 7, [1, 2, 4, 5, 10, 11, 13]
14, 8, [1, 2, 4, 5, 10, 11, 13, 14]
20, 9, [1, 2, 6, 7, 9, 14, 15, 18, 20]
24, 10, [1, 2, 5, 7, 11, 16, 18, 19, 23, 24]
26, 11, [1, 2, 5, 7, 11, 16, 18, 19, 23, 24, 26]
30, 12, [1, 3, 4, 8, 9, 11, 20, 22, 23, 27, 28, 30]
32, 13, [1, 2, 4, 8, 9, 11, 19, 22, 23, 26, 28, 31, 32]
36, 14, [1, 2, 4, 8, 9, 13, 21, 23, 26, 27, 30, 32, 35, 36]
40, 15, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 32, 37, 38, 40]
41, 16, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 32, 37, 38, 40, 41]
51, 17, [1, 2, 4, 5, 10, 13, 14, 17, 31, 35, 37, 38, 40, 46, 47, 50, 51]
54, 18, [1, 2, 5, 6, 12, 14, 15, 17, 21, 31, 38, 39, 42, 43, 49, 51, 52, 54]
58, 19, [1, 2, 5, 6, 12, 14, 15, 17, 21, 31, 38, 39, 42, 43, 49, 51, 52, 54, 58]
63, 20, [1, 2, 5, 7, 11, 16, 18, 19, 24, 26, 38, 39, 42, 44, 48, 53, 55, 56, 61, 63]
71, 21, [1, 2, 5, 7, 10, 17, 20, 22, 26, 31, 41, 46, 48, 49, 53, 54, 63, 64, 68, 69, 71]
74, 22, [1, 2, 7, 9, 10, 14, 20, 22, 23, 25, 29, 46, 50, 52, 53, 55, 61, 65, 66, 68, 73, 74]
82, 23, [1, 2, 4, 8, 9, 11, 19, 22, 23, 26, 28, 31, 49, 57, 59, 62, 63, 66, 68, 71, 78, 81, 82]
MATHEMATICA
(* Program not suitable to compute a large number of terms *)
a[n_] := a[n] = For[r = Range[n]; k = n, k >= 1, k--, If[AnyTrue[Subsets[r, {k}], FreeQ[#, {___, a_, ___, b_, ___, c_, ___} /; b - a == c - b] &], Return[k]]];
PROG
(PARI) ap3(v)=for(i=1, #v-2, for(j=i+2, #v, my(t=v[i]+v[j]); if(t%2==0 && setsearch(v, t/2), return(1)))); 0
a(N)=forstep(n=N, 2, -1, forvec(v=vector(n, i, [1, N]), if(!ap3(v), return(n)), 2)); N \\ Charles R Greathouse IV, Apr 22 2022
CROSSREFS
A selection of sequences related to "no three-term arithmetic progression": A003002, A003003, A003278, A004793, A005047, A005487, A033157, A065825, A092482, A093678, A093679, A093680, A093681, A093682, A094870, A101884, A101886, A101888, A140577, A185256, A208746, A229037.
EXTENSIONS
Extended from 53 terms to 80 terms, using a simple brute-force program with some pruning, by Shreevatsa R, Oct 18 2009
Irregular triangle read by rows where T(n,k) is the number of Golomb rulers of length n with k + 1 marks, k > 0.
+10
21
1, 1, 1, 2, 1, 2, 1, 4, 1, 4, 2, 1, 6, 6, 1, 6, 8, 1, 8, 18, 1, 8, 16, 1, 10, 30, 4, 1, 10, 34, 14, 1, 12, 48, 28, 1, 12, 48, 42, 1, 14, 72, 76, 1, 14, 72, 100, 1, 16, 96, 160, 8, 1, 16, 98, 190, 8, 1, 18, 126, 284, 40, 1, 18, 128, 316, 70
COMMENTS
Also the number of length-k compositions of n such that every restriction to a subinterval has a different sum. A composition of n is a finite sequence of positive integers summing to n.
EXAMPLE
Triangle begins:
1
1
1 2
1 2
1 4
1 4 2
1 6 6
1 6 8
1 8 18
1 8 16
1 10 30 4
1 10 34 14
1 12 48 28
1 12 48 42
1 14 72 76
1 14 72 100
1 16 96 160 8
1 16 98 190 8
1 18 126 284 40
1 18 128 316 70
Row n = 8 counts the following rulers:
{0,8} {0,1,8} {0,1,3,8}
{0,2,8} {0,1,5,8}
{0,3,8} {0,1,6,8}
{0,5,8} {0,2,3,8}
{0,6,8} {0,2,7,8}
{0,7,8} {0,3,7,8}
{0,5,6,8}
{0,5,7,8}
and the following compositions:
(8) (17) (125)
(26) (143)
(35) (152)
(53) (215)
(62) (251)
(71) (341)
(512)
(521)
MATHEMATICA
DeleteCases[Table[Length[Select[Join@@Permutations/@IntegerPartitions[n, {k}], UnsameQ@@ReplaceList[#, {___, s__, ___}:>Plus[s]]&]], {n, 15}, {k, n}], 0, {2}]
Number of maximal subsets of {1..n} such that every orderless pair of distinct elements has a different sum.
+10
15
1, 1, 1, 1, 4, 5, 8, 22, 40, 56, 78, 124, 222, 390, 616, 892, 1220, 1620, 2182, 3042, 4392
EXAMPLE
The a(1) = 1 through a(6) = 8 subsets:
{1} {1,2} {1,2,3} {1,2,3} {1,2,4} {1,2,3,5}
{1,2,4} {2,3,4} {1,2,3,6}
{1,3,4} {2,4,5} {1,2,4,6}
{2,3,4} {1,2,3,5} {1,3,4,5}
{1,3,4,5} {1,3,5,6}
{1,4,5,6}
{2,3,4,6}
{2,4,5,6}
MATHEMATICA
fasmax[y_]:=Complement[y, Union@@(Most[Subsets[#]]&/@y)];
Table[Length[fasmax[Select[Subsets[Range[n]], UnsameQ@@Plus@@@Subsets[Union[#], {2}]&]]], {n, 0, 10}]
CROSSREFS
The integer partition case is A325857. The strict integer partition case is A325877. Heinz numbers of the counterexamples are given by A325991.
Number of maximal subsets of {1..n} such that every ordered pair of distinct elements has a different difference.
+10
11
1, 1, 1, 3, 3, 6, 14, 20, 24, 36, 64, 110, 176, 238, 294, 370, 504, 736, 1086, 1592, 2240, 2982, 3788, 4700, 5814, 7322, 9396, 12336, 16552, 22192, 29310, 38046, 48368, 60078, 73722, 89416, 108208, 131310, 160624, 198002, 247408, 310410, 390924, 490818, 613344, 758518
COMMENTS
Also the number of maximal subsets of {1..n} such that every orderless pair of (not necessarily distinct) elements has a different sum.
EXAMPLE
The a(0) = 1 through a(7) = 20 subsets:
{} {1} {1,2} {1,2} {2,3} {1,2,4} {1,2,4} {1,2,4}
{1,3} {1,2,4} {1,2,5} {1,2,5} {1,2,6}
{2,3} {1,3,4} {1,3,4} {1,2,6} {1,3,4}
{1,4,5} {1,3,4} {1,4,5}
{2,3,5} {1,3,6} {1,4,6}
{2,4,5} {1,4,5} {1,5,6}
{1,4,6} {2,3,5}
{1,5,6} {2,3,6}
{2,3,5} {2,3,7}
{2,3,6} {2,4,5}
{2,4,5} {2,4,7}
{2,5,6} {2,5,6}
{3,4,6} {2,6,7}
{3,5,6} {3,4,6}
{3,4,7}
{3,5,6}
{4,5,7}
{4,6,7}
{1,2,5,7}
{1,3,6,7}
MATHEMATICA
fasmax[y_]:=Complement[y, Union@@(Most[Subsets[#]]&/@y)];
Table[Length[fasmax[Select[Subsets[Range[n]], UnsameQ@@Subtract@@@Subsets[Union[#], {2}]&]]], {n, 0, 10}]
CROSSREFS
The integer partition case is A325858. The strict integer partition case is A325876. Heinz numbers of the counterexamples are given by A325992.
Number of maximal primitive subsets of {1..n}.
+10
11
1, 1, 2, 2, 3, 3, 4, 4, 6, 7, 11, 11, 13, 13, 23, 24, 36, 36, 48, 48, 64, 66, 126, 126, 150, 151, 295, 363, 507, 507, 595, 595, 895, 903, 1787, 1788, 2076, 2076, 4132, 4148, 5396, 5396, 6644, 6644, 9740, 11172, 22300, 22300, 26140, 26141, 40733, 40773, 60333, 60333, 80781, 80783
COMMENTS
a(n) is the number of maximal primitive subsets of {1, ..., n}. Here primitive means that no element of the subset divides any other and maximal means that no element can be added to the subset while maintaining the property of being pairwise indivisible. - Nathan McNew, Aug 10 2020
EXAMPLE
The a(0) = 1 through a(9) = 7 sets:
{} {1} {1} {1} {1} {1} {1} {1} {1} {1}
{2} {23} {23} {235} {235} {2357} {2357} {2357}
{34} {345} {345} {3457} {3457} {2579}
{456} {4567} {3578} {3457}
{4567} {3578}
{5678} {45679}
{56789}
MATHEMATICA
stableQ[u_, Q_]:=!Apply[Or, Outer[#1=!=#2&&Q[#1, #2]&, u, u, 1], {0, 1}];
fasmax[y_]:=Complement[y, Union@@(Most[Subsets[#]]&/@y)];
Table[Length[fasmax[Select[Subsets[Range[n]], stableQ[#, Divisible]&]]], {n, 0, 10}]
PROG
(PARI)
divset(n)={sumdiv(n, d, if(d<n, 1 << d))}
a(n)={my(p=vector(n, k, divset(k)), d=0); for(i=1, #p, d=bitor(d, p[i]));
my(ismax(b)=my(e=0); forstep(k=#p, 1, -1, if(bittest(b, k), e=bitor(e, p[k]), if(!bittest(e, k) && !bitand(p[k], b), return(0)) )); 1);
((k, b)->if(k>#p, ismax(b), my(f=!bitand(p[k], b)); if(!f || bittest(d, k), self()(k+1, b)) + if(f, self()(k+1, b+(1<<k)))))(1, 0)} \\ Andrew Howroyd, Aug 30 2019
CROSSREFS
Cf. A001055, A051026 (all primitive subsets), A067992, A096827, A143824, A285572, A285573, A303362, A305148, A305149, A316476, A325861, A326023, A326082.
Number of maximal subsets of {1..n} containing n such that every subset has a different sum.
+10
9
1, 1, 2, 2, 4, 8, 10, 12, 17, 34, 45, 77, 99, 136, 166, 200, 238, 328, 402, 660, 674, 1166, 1331, 1966, 2335, 3286, 3527, 4762, 5383, 6900, 7543, 9087, 10149, 12239, 13569, 16452, 17867, 22869, 23977, 33881, 33820, 43423, 48090, 68683, 67347, 95176, 97917, 131666, 136205
COMMENTS
These are maximal strict knapsack partitions ( A275972, A326015) organized by maximum rather than sum.
EXAMPLE
The a(1) = 1 through a(8) = 12 subsets:
{1} {1,2} {1,3} {1,2,4} {1,2,5} {1,2,6} {1,2,7} {1,3,8}
{2,3} {2,3,4} {1,3,5} {1,3,6} {1,3,7} {1,5,8}
{2,4,5} {1,4,6} {1,4,7} {5,7,8}
{3,4,5} {2,3,6} {1,5,7} {1,2,4,8}
{2,5,6} {2,3,7} {1,4,6,8}
{3,4,6} {2,4,7} {2,3,4,8}
{3,5,6} {2,6,7} {2,4,5,8}
{4,5,6} {4,5,7} {2,4,7,8}
{4,6,7} {3,4,6,8}
{3,5,6,7} {3,6,7,8}
{4,5,6,8}
{4,6,7,8}
MATHEMATICA
fasmax[y_]:=Complement[y, Union@@(Most[Subsets[#]]&)/@y];
Table[Length[fasmax[Select[Subsets[Range[n]], MemberQ[#, n]&&UnsameQ@@Plus@@@Subsets[#]&]]], {n, 15}]
PROG
(Python)
def f(p0, n, m, cm):
full, t, p = True, 0, p0
while p<n:
sm = m<<p
if (m & sm) == 0:
t += f(p+1, n, m|sm, cm|(1<<p))
full=False
p+=1
if full:
for k in range(1, p0):
if ((cm>>k)&1)==0 and ((m<<k)&m)==0:
full=False
break
return 1 if full else t
def a325867(n):
return f(1, n, (1<<n)+1, 0)
Number of maximal subsets of {1..n} containing n such that every ordered pair of distinct elements has a different difference.
+10
9
1, 1, 2, 2, 4, 8, 8, 10, 18, 34, 50, 70, 78, 89, 120, 181, 277, 401, 561, 728, 867, 1031, 1219, 1537
COMMENTS
Also the number of maximal subsets of {1..n} containing n such that every orderless pair of (not necessarily distinct) elements has a different sum.
EXAMPLE
The a(2) = 1 through a(9) = 18 subsets:
{1,2} {1,3} {1,2,4} {1,2,5} {1,2,6} {2,3,7} {3,5,8} {4,6,9}
{2,3} {1,3,4} {1,4,5} {1,3,6} {2,4,7} {4,5,8} {5,6,9}
{2,3,5} {1,4,6} {2,6,7} {1,2,4,8} {1,2,4,9}
{2,4,5} {1,5,6} {3,4,7} {1,2,6,8} {1,2,6,9}
{2,3,6} {4,5,7} {1,3,4,8} {1,2,7,9}
{2,5,6} {4,6,7} {1,3,7,8} {1,3,4,9}
{3,4,6} {1,2,5,7} {1,5,6,8} {1,3,8,9}
{3,5,6} {1,3,6,7} {1,5,7,8} {1,4,8,9}
{2,3,6,8} {1,6,7,9}
{2,4,7,8} {1,6,8,9}
{2,3,5,9}
{2,3,7,9}
{2,4,5,9}
{2,4,8,9}
{2,6,7,9}
{2,6,8,9}
{3,4,7,9}
{3,5,8,9}
MATHEMATICA
fasmax[y_]:=Complement[y, Union@@(Most[Subsets[#]]&/@y)];
Table[Length[fasmax[Select[Subsets[Range[n]], MemberQ[#, n]&&UnsameQ@@Subtract@@@Subsets[Union[#], {2}]&]]], {n, 0, 10}]
Search completed in 0.019 seconds
| 
