A365315 Number of unordered pairs of distinct positive integers <= n that can be linearly combined using positive coefficients to obtain n.

0, 0, 0, 1, 2, 4, 5, 8, 10, 12, 15, 18, 20, 24, 28, 28, 35, 37, 42, 44, 49, 49, 60, 59, 66, 65, 79, 74, 85, 84, 93, 93, 107, 100, 120, 104, 126, 121, 142, 129, 145, 140, 160, 150, 173, 154, 189, 170, 196, 176, 208, 193, 223, 202, 238, 203, 241, 227, 267, 235

Offset: 0

Author

Gus Wiseman, Sep 06 2023

Keywords

• nonn

Comments

We consider (for example) that 2x + y + 3z is a positive linear combination of (x,y,z), but 2x + y is not, as the coefficient of z is 0.

Examples

			We have 19 = 4*3 + 1*7, so the pair (3,7) is counted under a(19).
For the pair p = (2,3), we have 4 = 2*2 + 0*3, so p is counted under A365314(4), but it is not possible to write 4 as a positive linear combination of 2 and 3, so p is not counted under a(4).
The a(3) = 1 through a(10) = 15 pairs:
  (1,2)  (1,2)  (1,2)  (1,2)  (1,2)  (1,2)  (1,2)  (1,2)
         (1,3)  (1,3)  (1,3)  (1,3)  (1,3)  (1,3)  (1,3)
                (1,4)  (1,4)  (1,4)  (1,4)  (1,4)  (1,4)
                (2,3)  (1,5)  (1,5)  (1,5)  (1,5)  (1,5)
                       (2,4)  (1,6)  (1,6)  (1,6)  (1,6)
                              (2,3)  (1,7)  (1,7)  (1,7)
                              (2,5)  (2,3)  (1,8)  (1,8)
                              (3,4)  (2,4)  (2,3)  (1,9)
                                     (2,6)  (2,5)  (2,3)
                                     (3,5)  (2,7)  (2,4)
                                            (3,6)  (2,6)
                                            (4,5)  (2,8)
                                                   (3,4)
                                                   (3,7)
                                                   (4,6)
		

Links

• Chai Wah Wu, Table of n, a(n) for n = 0..10000

Crossrefs

The unrestricted version is A000217, ranks A001358.

For all subsets instead of just pairs we have A088314, complement A365322.

For strict partitions we have A088571, complement A088528.

The case of nonnegative coefficients is A365314, for all subsets A365073.

The (binary) complement is A365321, nonnegative A365320.

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, A088809, A326020, A364534, A365043, A365311, A365312, A365378, A365379, A365380, A365383.

Programs

Mathematica

combp[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,1,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[Subsets[Range[n],{2}],combp[n,#]!={}&]],{n,0,30}]

Python

from itertools import count
from sympy import divisors
def A365315(n):
    a = set()
    for i in range(1,n+1):
        for j in count(i,i):
            if j >= n:
                break
            for d in divisors(n-j):
                if d>=i:
                    break
                a.add((d,i))
    return len(a) # Chai Wah Wu, Sep 13 2023