login
A365320
Number of pairs of distinct positive integers <= n that cannot be linearly combined with nonnegative coefficients to obtain n.
14
0, 0, 0, 0, 0, 2, 1, 7, 5, 12, 12, 27, 14, 42, 36, 47, 47, 83, 58, 109, 80, 116, 126, 172, 111, 195, 192, 219, 202, 294, 210, 342, 286, 354, 369, 409, 324, 509, 480, 523, 452, 640, 507, 711, 622, 675, 747, 865, 654, 916, 842, 964, 922, 1124, 940, 1147, 1029
OFFSET
0,6
COMMENTS
Are there only two cases of nonzero adjacent equal parts, at positions n = 9, 15?
EXAMPLE
The pair p = (3,6) cannot be linearly combined to obtain 8 or 10, so p is counted under a(8) and a(10), but we have 9 = 1*3 + 1*6 or 9 = 3*3 + 0*6, so p not counted under a(9).
The a(5) = 2 through a(10) = 12 pairs:
(2,4) (4,5) (2,4) (3,6) (2,4) (3,6)
(3,4) (2,6) (3,7) (2,6) (3,8)
(3,5) (5,6) (2,8) (3,9)
(3,6) (5,7) (4,6) (4,7)
(4,5) (6,7) (4,7) (4,8)
(4,6) (4,8) (4,9)
(5,6) (5,6) (6,7)
(5,7) (6,8)
(5,8) (6,9)
(6,7) (7,8)
(6,8) (7,9)
(7,8) (8,9)
MATHEMATICA
combs[n_, y_]:=With[{s=Table[{k, i}, {k, y}, {i, 0, Floor[n/k]}]}, Select[Tuples[s], Total[Times@@@#]==n&]];
Table[Length[Select[Subsets[Range[n], {2}], combs[n, #]=={}&]], {n, 0, 30}]
PROG
(Python)
from itertools import count
from sympy import divisors
def A365320(n):
a = set()
for i in range(1, n+1):
if not n%i:
a.update(tuple(sorted((i, j))) for j in range(1, n+1) if j!=i)
else:
for j in count(0, i):
if j > n:
break
k = n-j
for d in divisors(k):
if d>=i:
break
a.add((d, i))
return (n*(n-1)>>1)-len(a) # Chai Wah Wu, Sep 13 2023
CROSSREFS
The unrestricted version is A000217, ranks A001358.
For strict partitions we have A365312, complement A365311.
The (binary) complement is A365314, positive A365315.
The case of positive coefficients is A365321, for all subsets A365322.
For partitions we have A365378, complement A365379.
For all subsets instead of just pairs we have A365380, complement A365073.
A004526 counts partitions of length 2, shift right for strict.
A007865 counts sum-free subsets, complement A093971.
A179822 and A326080 count sum-closed subsets.
A326083 and A124506 appear to count combination-free subsets.
A364350 counts combination-free strict partitions.
A364914 and A365046 count combination-full subsets.
Sequence in context: A299238 A344960 A342747 * A356732 A077230 A244238
KEYWORD
nonn
AUTHOR
Gus Wiseman, Sep 06 2023
STATUS
approved