A364915
Number of integer partitions of n such that no distinct part can be written as a nonnegative linear combination of other distinct parts.
Original entry on oeis.org
1, 1, 2, 2, 3, 3, 4, 5, 6, 7, 8, 12, 10, 16, 16, 19, 21, 29, 25, 37, 35, 44, 46, 60, 55, 75, 71, 90, 90, 114, 110, 140, 138, 167, 163, 217, 201, 248, 241, 298, 303, 359, 355, 425, 422, 520, 496, 594, 603, 715, 706, 834, 826, 968, 972, 1153, 1147, 1334, 1315, 1530
Offset: 0
The a(1) = 1 through a(10) = 8 partitions (A=10):
1 2 3 4 5 6 7 8 9 A
11 111 22 32 33 43 44 54 55
1111 11111 222 52 53 72 64
111111 322 332 333 73
1111111 2222 522 433
11111111 3222 3322
111111111 22222
1111111111
The partition (5,4,3) has no part that can be written as a nonnegative linear combination of the others, so is counted under a(12).
The partition (6,4,3,2) has 6=4+2, or 6=3+3, or 6=2+2+2, or 4=2+2, so is not counted under a(15).
For subsets instead of partitions we have
A326083, complement
A364914.
A007865 counts binary sum-free sets w/ re-usable parts, complement
A093971.
A364912 counts linear combinations of partitions of k.
-
combs[n_,y_]:=With[{s=Table[{k,i},{k,y}, {i,0,Floor[n/k]}]}, Select[Tuples[s], Total[Times@@@#]==n&]];
Table[Length[Select[IntegerPartitions[n], Function[ptn,!Or@@Table[combs[ptn[[k]],Delete[ptn,k]]!={}, {k,Length[ptn]}]]@*Union]], {n,0,15}]
-
from sympy.utilities.iterables import partitions
def A364915(n):
if n <= 1: return 1
alist, c = [set(tuple(sorted(set(p))) for p in partitions(i)) for i in range(n)], 1
for p in partitions(n,k=n-1):
s = set(p)
if not any(set(t).issubset(s-{q}) for q in s for t in alist[q]):
c += 1
return c # Chai Wah Wu, Sep 23 2023
A363260
Number of integer partitions of n with parts disjoint from first differences of parts, meaning no part is the difference of two consecutive parts.
Original entry on oeis.org
1, 1, 2, 2, 4, 5, 7, 10, 13, 17, 21, 28, 35, 46, 57, 70, 87, 110, 130, 165, 198, 238, 285, 349, 410, 498, 583, 702, 819, 983, 1136, 1353, 1570, 1852, 2137, 2520, 2898, 3390, 3891, 4540, 5191, 6028, 6889, 7951, 9082, 10450, 11884, 13650, 15508, 17728, 20113
Offset: 0
The a(1) = 1 through a(8) = 13 partitions:
(1) (2) (3) (4) (5) (6) (7) (8)
(11) (111) (22) (32) (33) (43) (44)
(31) (41) (51) (52) (53)
(1111) (311) (222) (61) (62)
(11111) (411) (322) (71)
(3111) (331) (332)
(111111) (511) (611)
(4111) (2222)
(31111) (3311)
(1111111) (5111)
(41111)
(311111)
(11111111)
For all differences of pairs parts we have
A364345.
For subsets of {1..n} instead of partitions we have
A364463.
A325325 counts partitions with distinct first-differences.
-
Table[Length[Select[IntegerPartitions[n],Intersection[#,-Differences[#]]=={}&]],{n,0,30}]
-
from collections import Counter
from sympy.utilities.iterables import partitions
def A363260(n): return sum(1 for s,p in map(lambda x: (x[0],tuple(sorted(Counter(x[1]).elements()))), partitions(n,size=True)) if set(p).isdisjoint({p[i+1]-p[i] for i in range(s-1)})) # Chai Wah Wu, Sep 26 2023
A365376
Number of subsets of {1..n} with a subset summing to n.
Original entry on oeis.org
1, 1, 2, 5, 10, 23, 47, 102, 207, 440, 890, 1847, 3730, 7648, 15400, 31332, 62922, 127234, 255374, 514269, 1030809, 2071344, 4148707, 8321937, 16660755, 33384685, 66812942, 133789638, 267685113, 535784667, 1071878216, 2144762139, 4290261840, 8583175092, 17168208940, 34342860713
Offset: 0
The a(1) = 1 through a(4) = 10 sets:
{1} {2} {3} {4}
{1,2} {1,2} {1,3}
{1,3} {1,4}
{2,3} {2,4}
{1,2,3} {3,4}
{1,2,3}
{1,2,4}
{1,3,4}
{2,3,4}
{1,2,3,4}
The case containing n is counted by
A131577.
The version with re-usable parts is
A365073.
The complement is counted by
A365377.
The complement w/ re-usable parts is
A365380.
A000124 counts distinct possible sums of subsets of {1..n}.
A124506 appears to count combination-free subsets, differences of
A326083.
A364350 counts combination-free strict partitions, complement
A364839.
-
Table[Length[Select[Subsets[Range[n]],MemberQ[Total/@Subsets[#],n]&]],{n,0,10}]
-
isok(s, n) = forsubset(#s, ss, if (vecsum(vector(#ss, k, s[ss[k]])) == n, return(1)));
a(n) = my(nb=0); forsubset(n, s, if (isok(s, n), nb++)); nb; \\ Michel Marcus, Sep 09 2023
-
from itertools import combinations, chain
from sympy.utilities.iterables import partitions
def A365376(n):
if n == 0: return 1
nset = set(range(1,n+1))
s, c = [set(p) for p in partitions(n,m=n,k=n) if max(p.values(),default=1) == 1], 1
for a in chain.from_iterable(combinations(nset,m) for m in range(2,n+1)):
if sum(a) >= n:
aset = set(a)
for p in s:
if p.issubset(aset):
c += 1
break
return c # Chai Wah Wu, Sep 09 2023
A366320
Irregular triangle read by rows where T(n,k) is the number of subsets of {1..n} without a subset summing to k.
Original entry on oeis.org
1, 2, 2, 3, 4, 4, 3, 6, 6, 7, 8, 8, 6, 6, 9, 11, 11, 14, 14, 15, 16, 16, 12, 12, 9, 17, 17, 20, 20, 24, 27, 27, 30, 30, 31, 32, 32, 24, 24, 18, 17, 26, 31, 29, 35, 36, 43, 47, 50, 51, 56, 59, 59, 62, 62, 63
Offset: 1
Triangle begins:
1
2 2 3
4 4 3 6 6 7
8 8 6 6 9 11 11 14 14 15
16 16 12 12 9 17 17 20 20 24 27 27 30 30 31
32 32 24 24 18 17 26 31 29 35 36 43 47 50 51 56 59 59 62 62 63
Row n = 3 counts the following subsets:
{} {} {} {} {} {}
{2} {1} {1} {1} {1} {1}
{3} {3} {2} {2} {2} {2}
{2,3} {1,3} {3} {3} {3}
{1,2} {1,2} {1,2}
{2,3} {1,3} {1,3}
{2,3}
The complement is counted by
A365381.
A000009 counts subsets summing to n.
A000124 counts distinct possible sums of subsets of {1..n}.
-
Table[Length[Select[Subsets[Range[n]],FreeQ[Total/@Subsets[#],k]&]],{n,8},{k,n*(n+1)/2}]
A308546
Number of double-closed subsets of {1..n}.
Original entry on oeis.org
1, 2, 3, 6, 8, 16, 24, 48, 60, 120, 180, 360, 480, 960, 1440, 2880, 3456, 6912, 10368, 20736, 27648, 55296, 82944, 165888, 207360, 414720, 622080, 1244160, 1658880, 3317760, 4976640, 9953280, 11612160, 23224320, 34836480, 69672960, 92897280
Offset: 0
The a(6) = 24 subsets:
{} {4} {2,4} {1,2,4} {1,2,4,5} {1,2,3,4,6} {1,2,3,4,5,6}
{5} {3,6} {2,4,5} {1,2,4,6} {1,2,4,5,6}
{6} {4,5} {2,4,6} {2,3,4,6} {2,3,4,5,6}
{4,6} {3,4,6} {2,4,5,6}
{5,6} {3,5,6} {3,4,5,6}
{4,5,6}
Cf.
A007865,
A050291,
A103580,
A120641,
A320340,
A323092,
A325864,
A326020,
A326076,
A326083,
A326115.
-
Table[Length[Select[Subsets[Range[n]],SubsetQ[#,Select[2*#,#<=n&]]&]],{n,0,10}]
A364461
Positive integers such that if prime(a)*prime(b) is a divisor, prime(a+b) is not.
Original entry on oeis.org
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 28, 29, 31, 32, 33, 34, 35, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 61, 62, 64, 65, 66, 67, 68, 69, 71, 73, 74, 75, 76
Offset: 1
The prime indices of 198 are {1,2,2,5}, which is sum-free even though it is not knapsack (A299702, A299729), so 198 is in the sequence.
Subsets of this type are counted by
A085489, with re-usable parts
A007865.
Subsets not of this type are counted by
A093971, w/ re-usable parts
A088809.
Partitions of this type are counted by
A236912.
The complement allowing parts to be re-used is
A364348, counted by
A363225.
The non-binary version allowing re-used parts is counted by
A364350.
-
prix[n_]:=If[n==1,{}, Flatten[Cases[FactorInteger[n], {p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100],Intersection[prix[#], Total/@Subsets[prix[#],{2}]]=={}&]
A364462
Positive integers having a divisor of the form prime(a)*prime(b) such that prime(a+b) is also a divisor.
Original entry on oeis.org
12, 24, 30, 36, 48, 60, 63, 70, 72, 84, 90, 96, 108, 120, 126, 132, 140, 144, 150, 154, 156, 165, 168, 180, 189, 192, 204, 210, 216, 228, 240, 252, 264, 270, 273, 276, 280, 286, 288, 300, 308, 312, 315, 324, 325, 330, 336, 348, 350, 360, 372, 378, 384, 390
Offset: 1
The terms together with their prime indices begin:
12: {1,1,2}
24: {1,1,1,2}
30: {1,2,3}
36: {1,1,2,2}
48: {1,1,1,1,2}
60: {1,1,2,3}
63: {2,2,4}
70: {1,3,4}
72: {1,1,1,2,2}
84: {1,1,2,4}
90: {1,2,2,3}
96: {1,1,1,1,1,2}
108: {1,1,2,2,2}
120: {1,1,1,2,3}
126: {1,2,2,4}
132: {1,1,2,5}
140: {1,1,3,4}
144: {1,1,1,1,2,2}
Subsets not of this type are counted by
A085489, w/ re-usable parts
A007865.
Subsets of this type are counted by
A088809, with re-usable parts
A093971.
Partitions not of this type are counted by
A236912.
Partitions of this type are counted by
A237113.
-
filter:= proc(n) local F, i,j,m;
F:= map(t -> `if`(t[2]>=2, numtheory:-pi(t[1])$2, numtheory:-pi(t[1])), ifactors(n)[2]);
for i from 1 to nops(F)-1 do for j from 1 to i-1 do
if member(F[i]+F[j],F) then return true fi
od od;
false
end proc:
select(filter, [$1..1000]); # Robert Israel, Aug 30 2023
-
prix[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100],Intersection[prix[#], Total/@Subsets[prix[#],{2}]]!={}&]
A365043
Number of subsets of {1..n} whose greatest element can be written as a (strictly) positive linear combination of the others.
Original entry on oeis.org
0, 0, 1, 3, 7, 12, 21, 32, 49, 70, 99, 135, 185, 245, 323, 418, 541, 688, 873, 1094, 1368, 1693, 2092, 2564, 3138, 3810, 4620, 5565, 6696, 8012, 9569, 11381, 13518, 15980, 18872, 22194, 26075, 30535, 35711, 41627, 48473, 56290, 65283, 75533, 87298, 100631, 115911, 133219
Offset: 0
The subset S = {3,4,9} has 9 = 3*3 + 0*4, but this is not strictly positive, so S is not counted under a(9).
The subset S = {3,4,10} has 10 = 2*3 + 1*4, so S is counted under a(10).
The a(0) = 0 through a(5) = 12 subsets:
. . {1,2} {1,2} {1,2} {1,2}
{1,3} {1,3} {1,3}
{1,2,3} {1,4} {1,4}
{2,4} {1,5}
{1,2,3} {2,4}
{1,2,4} {1,2,3}
{1,3,4} {1,2,4}
{1,2,5}
{1,3,4}
{1,3,5}
{1,4,5}
{2,3,5}
A085489 and
A364755 count subsets with no sum of two distinct elements.
A088809 and
A364756 count subsets with some sum of two distinct elements.
A364350 counts combination-free strict partitions, complement
A364839.
A364913 counts combination-full partitions.
-
combp[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,1,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[Rest[Subsets[Range[n]]],combp[Last[#],Union[Most[#]]]!={}&]],{n,0,10}]
-
from itertools import combinations
from sympy.utilities.iterables import partitions
def A365043(n):
mlist = tuple({tuple(sorted(p.keys())) for p in partitions(m,k=m-1)} for m in range(1,n+1))
return sum(1 for k in range(2,n+1) for w in combinations(range(1,n+1),k) if w[:-1] in mlist[w[-1]-1]) # Chai Wah Wu, Nov 20 2023
A364348
Numbers with two possibly equal divisors prime(a) and prime(b) such that prime(a+b) is also a divisor.
Original entry on oeis.org
6, 12, 18, 21, 24, 30, 36, 42, 48, 54, 60, 63, 65, 66, 70, 72, 78, 84, 90, 96, 102, 105, 108, 114, 120, 126, 130, 132, 133, 138, 140, 144, 147, 150, 154, 156, 162, 165, 168, 174, 180, 186, 189, 192, 195, 198, 204, 210, 216, 222, 228, 231, 234, 240, 246, 252
Offset: 1
We have 6 because prime(1) and prime(1) are both divisors of 6, and prime(1+1) is also.
The terms together with their prime indices begin:
6: {1,2}
12: {1,1,2}
18: {1,2,2}
21: {2,4}
24: {1,1,1,2}
30: {1,2,3}
36: {1,1,2,2}
42: {1,2,4}
48: {1,1,1,1,2}
54: {1,2,2,2}
60: {1,1,2,3}
63: {2,2,4}
65: {3,6}
66: {1,2,5}
70: {1,3,4}
72: {1,1,1,2,2}
-
prix[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100],Intersection[prix[#],Total/@Tuples[prix[#],2]]!={}&]
A364533
Number of strict integer partitions of n containing the sum of no pair of distinct parts. A variation of sum-free strict partitions.
Original entry on oeis.org
1, 1, 1, 2, 2, 3, 3, 5, 5, 8, 7, 11, 11, 15, 15, 21, 22, 28, 32, 38, 40, 51, 55, 65, 74, 83, 94, 111, 119, 136, 160, 174, 196, 222, 252, 273, 315, 341, 391, 425, 477, 518, 602, 636, 719, 782, 886, 944, 1073, 1140, 1302, 1380, 1553, 1651, 1888, 1995, 2224, 2370
Offset: 0
The a(1) = 1 through a(12) = 11 partitions (A..C = 10..12):
1 2 3 4 5 6 7 8 9 A B C
21 31 32 42 43 53 54 64 65 75
41 51 52 62 63 73 74 84
61 71 72 82 83 93
421 521 81 91 92 A2
432 631 A1 B1
531 721 542 543
621 632 732
641 741
731 831
821 921
Allowing re-used parts gives
A364346.
The linear combination-free version is
A364350.
The complement in strict partitions is
A364670, w/ re-used parts
A363226.
-
Table[Length[Select[IntegerPartitions[n], UnsameQ@@#&&Intersection[#, Total/@Subsets[#,{2}]] == {}&]],{n,0,30}]
Comments