Search: a325679 -id:a325679
|
|
A143823
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
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
|
|
LINKS
|
|
|
FORMULA
|
|
|
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.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|
|
A169942
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
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
|
|
LINKS
|
|
|
FORMULA
|
|
|
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.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|
|
A325683
|
|
Number of maximal Golomb rulers of length n.
|
|
+10
24
|
|
|
1, 1, 1, 2, 2, 4, 2, 6, 8, 18, 16, 24, 20, 28, 42, 76, 100, 138, 168, 204, 194, 272, 276, 450, 588, 808, 992, 1578, 1612, 1998, 2166, 2680, 2732, 3834, 3910, 5716, 6818, 9450, 10524, 15504, 16640, 22268, 23754, 30430, 31498, 40644, 40294, 52442, 56344, 72972, 77184
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
COMMENTS
|
A Golomb ruler of length n is a subset of {0..n} containing 0 and n and such that every pair of distinct terms has a different difference up to sign.
Also the number of minimal (most refined) compositions of n such that every restriction to a subinterval has a different sum.
|
|
LINKS
|
|
|
EXAMPLE
|
The a(1) = 1 through a(8) = 8 maximal Golomb rulers:
{0,1} {0,2} {0,1,3} {0,1,4} {0,1,5} {0,1,4,6} {0,1,3,7} {0,1,3,8}
{0,2,3} {0,3,4} {0,2,5} {0,2,5,6} {0,1,5,7} {0,1,5,8}
{0,3,5} {0,2,3,7} {0,1,6,8}
{0,4,5} {0,2,6,7} {0,2,3,8}
{0,4,5,7} {0,2,7,8}
{0,4,6,7} {0,3,7,8}
{0,5,6,8}
{0,5,7,8}
The a(1) = 1 through a(10) = 16 minimal compositions:
(1) (2) (12) (13) (14) (132) (124) (125) (126) (127)
(21) (31) (23) (231) (142) (143) (135) (136)
(32) (214) (152) (153) (154)
(41) (241) (215) (162) (163)
(412) (251) (216) (172)
(421) (341) (234) (217)
(512) (243) (253)
(521) (261) (271)
(315) (316)
(324) (352)
(342) (361)
(351) (451)
(423) (613)
(432) (631)
(513) (712)
(531) (721)
(612)
(621)
|
|
MATHEMATICA
|
fasmax[y_]:=Complement[y, Union@@(Most[Subsets[#]]&/@y)];
Table[Length[fasmax[Accumulate/@Select[Join@@Permutations/@IntegerPartitions[n], UnsameQ@@ReplaceList[#, {___, s__, ___}:>Plus[s]]&]]], {n, 0, 15}]
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|
|
A325677
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
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.
|
|
LINKS
|
|
|
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}]
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A325678
|
|
Maximum length of a composition of n such that every restriction to a subinterval has a different sum.
|
|
+10
8
|
|
|
0, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
COMMENTS
|
A composition of n is a finite sequence of positive integers summing to n.
Also the maximum number of nonzero marks on a Golomb ruler of length n.
|
|
LINKS
|
|
|
FORMULA
|
|
|
MATHEMATICA
|
Table[Max[Length/@Select[Join@@Permutations/@IntegerPartitions[n], UnsameQ@@ReplaceList[#, {___, s__, ___}:>Plus[s]]&]], {n, 0, 15}]
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A325789
|
|
Number of perfect necklace compositions of n.
|
|
+10
6
|
|
|
1, 1, 2, 1, 1, 1, 3, 1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
A necklace composition of n is a finite sequence of positive integers summing to n that is lexicographically minimal among all of its cyclic rotations. A circular subsequence is a sequence of consecutive terms where the last and first parts are also considered consecutive. A necklace composition of n is perfect if every positive integer from 1 to n is the sum of exactly one distinct circular subsequence.
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
The a(1) = 1 , a(2) = 1, a(3) = 2, a(7) = 3, a(13) = 5, and a(31) = 11 perfect necklace compositions (A = 10, B = 11, C = 12, D = 13, E = 14):
1 11 12 124 1264 12546D
111 142 1327 1274C5
1111111 1462 13278A
1723 13625E
1111111111111 15C472
17324E
1A8723
1D6452
1E4237
1E5263
1111111111111111111111111111111
|
|
MATHEMATICA
|
neckQ[q_]:=Array[OrderedQ[{q, RotateRight[q, #]}]&, Length[q]-1, 1, And];
subalt[q_]:=Union[ReplaceList[q, {___, s__, ___}:>{s}], DeleteCases[ReplaceList[q, {t___, __, u___}:>{u, t}], {}]];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], neckQ[#]&&Sort[Total/@subalt[#]]==Range[n]&]], {n, 10}]
|
|
CROSSREFS
|
Cf. A002033, A008965, A103300, A108917, A126796, A325676, A325679, A325685, A325780, A325782, A325786, A325787, A325789.
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A325681
|
|
Number of necklace compositions of n such that every restriction to a circular subinterval has a different sum.
|
|
+10
3
|
|
|
1, 1, 2, 2, 3, 3, 6, 6, 11, 9, 16, 16, 27, 23, 46, 42, 73, 63, 112, 102
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
A necklace composition of n is a finite sequence of positive integers summing to n that is lexicographically minimal among all of its cyclic rotations.
A circular subinterval is a sequence of consecutive indices where the first and last indices are also considered consecutive.
|
|
LINKS
|
|
|
EXAMPLE
|
The a(1) = 1 through a(10) = 9 necklace compositions (A = 10):
(1) (2) (3) (4) (5) (6) (7) (8) (9) (A)
(12) (13) (14) (15) (16) (17) (18) (19)
(23) (24) (25) (26) (27) (28)
(34) (35) (36) (37)
(124) (125) (45) (46)
(142) (152) (126) (127)
(135) (136)
(153) (163)
(162) (172)
(234)
(243)
|
|
MATHEMATICA
|
neckQ[q_]:=Array[OrderedQ[{q, RotateRight[q, #]}]&, Length[q]-1, 1, And];
suball[q_]:=Join[Take[q, #]&/@Select[Tuples[Range[Length[q]], 2], OrderedQ], Drop[q, #]&/@Select[Tuples[Range[2, Length[q]-1], 2], OrderedQ]];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], neckQ[#]&&UnsameQ@@Total/@suball[#]&]], {n, 15}]
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
Search completed in 0.009 seconds
|