A365315
Number of unordered pairs of distinct positive integers <= n that can be linearly combined using positive coefficients to obtain n.
Original entry on oeis.org
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
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)
For all subsets instead of just pairs we have
A088314, complement
A365322.
The case of nonnegative coefficients is
A365314, for all subsets
A365073.
A004526 counts partitions of length 2, shift right for strict.
A364350 counts combination-free strict partitions.
Cf.
A070880,
A088809,
A326020,
A364534,
A365043,
A365311,
A365312,
A365378,
A365379,
A365380,
A365383.
-
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}]
-
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
A365323
Number of integer partitions with sum < n whose distinct parts cannot be linearly combined using all positive coefficients to obtain n.
Original entry on oeis.org
0, 0, 1, 1, 4, 3, 9, 7, 15, 16, 29, 23, 47, 43, 74, 65, 114, 100, 174, 153, 257, 228, 368, 312, 530, 454, 736, 645, 1025, 902, 1402, 1184, 1909, 1626, 2618, 2184, 3412, 2895, 4551, 3887, 5966, 5055, 7796, 6509, 10244, 8462, 13060, 10881, 16834, 14021, 21471
Offset: 1
The partition y = (3,3,2) has distinct parts {2,3}, and we have 9 = 3*2 + 1*3, so y is not counted under a(9).
The a(3) = 1 through a(10) = 16 partitions:
(2) (3) (2) (4) (2) (3) (2) (3)
(3) (5) (3) (5) (4) (4)
(4) (3,2) (4) (6) (5) (6)
(2,2) (5) (7) (6) (7)
(6) (3,3) (7) (8)
(2,2) (4,3) (8) (9)
(3,3) (5,2) (2,2) (3,3)
(4,2) (4,2) (4,4)
(2,2,2) (4,3) (5,2)
(4,4) (5,3)
(5,3) (5,4)
(6,2) (6,3)
(2,2,2) (7,2)
(4,2,2) (3,3,3)
(2,2,2,2) (4,3,2)
(5,2,2)
For strict partitions we have
A088528, nonnegative coefficients
A365312.
For length-2 subsets we have
A365321 (we use n instead of n-1).
A364350 counts combination-free strict partitions, non-strict
A364915.
A364839 counts combination-full strict partitions, non-strict
A364913.
-
combp[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,1,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[Join@@IntegerPartitions/@Range[n-1],combp[n,Union[#]]=={}&]],{n,10}]
-
from sympy.utilities.iterables import partitions
def A365323(n):
a = {tuple(sorted(set(p))) for p in partitions(n)}
return sum(1 for k in range(1,n) for d in partitions(k) if tuple(sorted(set(d))) not in a) # Chai Wah Wu, Sep 12 2023
A365383
Triangle read by rows where T(n,k) is the number of integer partitions of n that can be linearly combined with nonnegative coefficients to obtain k.
Original entry on oeis.org
1, 2, 1, 3, 2, 2, 5, 3, 4, 3, 7, 5, 6, 6, 6, 11, 7, 9, 8, 9, 7, 15, 11, 13, 13, 14, 13, 14, 22, 15, 19, 17, 20, 17, 20, 16, 30, 22, 26, 26, 27, 26, 28, 26, 27, 42, 30, 37, 34, 39, 33, 40, 34, 39, 34, 56, 42, 50, 49, 52, 50, 54, 51, 54, 53, 53
Offset: 0
Triangle begins:
1
2 1
3 2 2
5 3 4 3
7 5 6 6 6
11 7 9 8 9 7
15 11 13 13 14 13 14
22 15 19 17 20 17 20 16
30 22 26 26 27 26 28 26 27
42 30 37 34 39 33 40 34 39 34
56 42 50 49 52 50 54 51 54 53 53
77 56 68 64 71 63 73 63 71 65 70 62
101 77 91 89 95 90 97 93 97 97 98 94 99
135 101 122 115 127 115 130 114 131 119 130 117 132 116
176 135 159 156 165 157 170 161 167 168 166 165 172 164 166
Row n = 6 counts the following partitions:
(6) (51) (51) (51) (51) (51)
(51) (411) (42) (411) (42) (411)
(42) (321) (411) (33) (411) (321)
(411) (3111) (321) (321) (321) (3111)
(33) (2211) (3111) (3111) (3111) (2211)
(321) (21111) (222) (2211) (222) (21111)
(3111) (111111) (2211) (21111) (2211) (111111)
(222) (21111) (111111) (21111)
(2211) (111111) (111111)
(21111)
(111111)
A364350 counts combination-free strict partitions, non-strict
A364915.
A364839 counts combination-full strict partitions, non-strict
A364913.
-
combu[n_,y_]:=With[{s=Table[{k,i},{k,Union[y]},{i,0,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[IntegerPartitions[n],combu[k,#]!={}&]],{n,0,12},{k,0,n-1}]
Comments