A365320 Number of pairs of distinct positive integers <= n that cannot be linearly combined with nonnegative coefficients to obtain n.

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?

Links

Table of n, a(n) for n=0..56.

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.

Cf. A070880, A088314, A088809, A151897, A326020, A364839.

Sequence in context: A299238 A344960 A342747 * A356732 A077230 A244238

Adjacent sequences: A365317 A365318 A365319 * A365321 A365322 A365323

Keyword

nonn

Author

Gus Wiseman, Sep 06 2023

Status

approved