A367220
Number of strict integer partitions of n whose length (number of parts) can be written as a nonnegative linear combination of the parts.
Original entry on oeis.org
1, 1, 0, 1, 1, 2, 3, 3, 4, 5, 7, 7, 10, 11, 15, 17, 22, 25, 32, 37, 46, 53, 65, 75, 90, 105, 124, 143, 168, 193, 224, 258, 297, 340, 390, 446, 509, 580, 660, 751, 852, 967, 1095, 1240, 1401, 1584, 1786, 2015, 2269, 2554, 2869, 3226, 3617, 4056, 4541, 5084
Offset: 0
The a(3) = 1 through a(10) = 7 strict partitions:
(2,1) (3,1) (3,2) (4,2) (5,2) (6,2) (7,2) (8,2)
(4,1) (5,1) (6,1) (7,1) (8,1) (9,1)
(3,2,1) (4,2,1) (4,3,1) (4,3,2) (5,3,2)
(5,2,1) (5,3,1) (5,4,1)
(6,2,1) (6,3,1)
(7,2,1)
(4,3,2,1)
The following sequences count and rank integer partitions and finite sets according to whether their length is a subset-sum or linear combination of the parts. The current sequence is starred.
sum-full sum-free comb-full comb-free
-------------------------------------------
A240855 counts strict partitions whose length is a part, complement
A240861.
Cf.
A008289,
A088314,
A116861,
A124506,
A363225,
A364346,
A364350,
A364916,
A365073,
A365311,
A365312.
-
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], UnsameQ@@#&&combs[Length[#], Union[#]]!={}&]], {n,0,15}]
A367221
Number of strict integer partitions of n whose length (number of parts) cannot be written as a nonnegative linear combination of the parts.
Original entry on oeis.org
0, 0, 1, 1, 1, 1, 1, 2, 2, 3, 3, 5, 5, 7, 7, 10, 10, 13, 14, 17, 18, 23, 24, 29, 32, 37, 41, 49, 54, 63, 72, 82, 93, 108, 122, 139, 159, 180, 204, 231, 261, 293, 331, 370, 415, 464, 518, 575, 641, 710, 789, 871, 965, 1064, 1177, 1294, 1428, 1569, 1729, 1897
Offset: 0
The a(2) = 1 through a(16) = 10 strict partitions (A..G = 10..16):
2 3 4 5 6 7 8 9 A B C D E F G
43 53 54 64 65 75 76 86 87 97
63 73 74 84 85 95 96 A6
83 93 94 A4 A5 B5
542 642 A3 B3 B4 C4
652 752 C3 D3
742 842 654 754
762 862
852 952
942 A42
The following sequences count and rank integer partitions and finite sets according to whether their length is a subset-sum or linear combination of the parts. The current sequence is starred.
sum-full sum-free comb-full comb-free
-------------------------------------------
A124506 appears to count combination-free subsets, differences of
A326083.
A240855 counts strict partitions whose length is a part, complement
A240861.
Triangles:
A046663 counts partitions of n without a subset-sum k, strict
A365663.
A365541 counts subsets containing two distinct elements summing to 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], UnsameQ@@#&&combs[Length[#], Union[#]]=={}&]], {n,0,30}]
A367222
Number of subsets of {1..n} whose cardinality can be written as a nonnegative linear combination of the elements.
Original entry on oeis.org
1, 2, 3, 6, 12, 24, 49, 101, 207, 422, 859, 1747, 3548, 7194, 14565, 29452, 59496, 120086, 242185, 488035, 982672, 1977166, 3975508, 7989147, 16047464, 32221270, 64674453, 129775774, 260337978, 522124197, 1046911594, 2098709858, 4206361369, 8429033614, 16887728757, 33829251009, 67755866536, 135687781793, 271693909435
Offset: 0
The set {1,2,4} has 3 = (2)+(1) or 3 = (1+1+1) so is counted under a(4).
The a(0) = 1 through a(4) = 12 subsets:
{} {} {} {} {}
{1} {1} {1} {1}
{1,2} {1,2} {1,2}
{1,3} {1,3}
{2,3} {1,4}
{1,2,3} {2,3}
{2,4}
{1,2,3}
{1,2,4}
{1,3,4}
{2,3,4}
{1,2,3,4}
The following sequences count and rank integer partitions and finite sets according to whether their length is a subset-sum or linear combination of the parts. The current sequence is starred.
sum-full sum-free comb-full comb-free
-------------------------------------------
A124506 appears to count combination-free subsets, differences of
A326083.
Triangles:
A365541 counts subsets containing two distinct elements summing to k.
Cf.
A068911,
A088314,
A103580,
A116861,
A326080,
A364350,
A365073,
A365311,
A365376,
A365380,
A365544.
-
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]], combs[Length[#], Union[#]]!={}&]], {n,0,10}]
-
from itertools import combinations
from sympy.utilities.iterables import partitions
def A367222(n):
c, mlist = 1, []
for m in range(1,n+1):
t = set()
for p in partitions(m):
t.add(tuple(sorted(p.keys())))
mlist.append([set(d) for d in t])
for k in range(1,n+1):
for w in combinations(range(1,n+1),k):
ws = set(w)
for s in mlist[k-1]:
if s <= ws:
c += 1
break
return c # Chai Wah Wu, Nov 16 2023
A367227
Numbers m whose prime indices have no nonnegative linear combination equal to bigomega(m).
Original entry on oeis.org
3, 5, 7, 11, 13, 17, 19, 23, 25, 27, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 63, 65, 67, 71, 73, 77, 79, 83, 85, 89, 91, 95, 97, 99, 101, 103, 107, 109, 113, 115, 117, 119, 121, 127, 131, 133, 137, 139, 143, 145, 147, 149, 151, 153, 155, 157, 161, 163
Offset: 1
The prime indices of 24 are {1,1,1,2} with (1+1+1+1) = 4 or (1+1)+(2) = 4 or (2+2) = 4, so 24 is not in the sequence.
The terms together with their prime indices begin:
3: {2} 43: {14} 85: {3,7}
5: {3} 47: {15} 89: {24}
7: {4} 49: {4,4} 91: {4,6}
11: {5} 53: {16} 95: {3,8}
13: {6} 55: {3,5} 97: {25}
17: {7} 59: {17} 99: {2,2,5}
19: {8} 61: {18} 101: {26}
23: {9} 63: {2,2,4} 103: {27}
25: {3,3} 65: {3,6} 107: {28}
27: {2,2,2} 67: {19} 109: {29}
29: {10} 71: {20} 113: {30}
31: {11} 73: {21} 115: {3,9}
35: {3,4} 77: {4,5} 117: {2,2,6}
37: {12} 79: {22} 119: {4,7}
41: {13} 83: {23} 121: {5,5}
The following sequences count and rank integer partitions and finite sets according to whether their length is a subset-sum or linear combination of the parts. The current sequence is starred.
sum-full sum-free comb-full comb-free
-------------------------------------------
A124506 appears to count combination-free subsets, differences of
A326083.
Cf.
A000720,
A046663,
A088314,
A106529,
A116861,
A236912,
A364345,
A364346,
A364347,
A364350,
A365073,
A365312.
-
prix[n_]:=If[n==1,{}, Flatten[Cases[FactorInteger[n], {p_,k_}:>Table[PrimePi[p], {k}]]]];
combs[n_,y_]:=With[{s=Table[{k,i}, {k,y}, {i,0,Floor[n/k]}]}, Select[Tuples[s], Total[Times@@@#]==n&]];
Select[Range[100], combs[PrimeOmega[#], Union[prix[#]]]=={}&]
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
A364463
Number of subsets of {1..n} with elements disjoint from first differences of elements.
Original entry on oeis.org
1, 2, 3, 6, 10, 18, 30, 54, 92, 167, 290, 525, 935, 1704, 3082, 5664, 10386, 19249, 35701, 66702, 124855, 234969, 443174, 839254, 1592925, 3032757, 5786153, 11066413, 21204855, 40712426, 78294085, 150815154, 290922900, 561968268, 1086879052, 2104570243
Offset: 0
The a(0) = 1 through a(5) = 18 subsets:
{} {} {} {} {} {}
{1} {1} {1} {1} {1}
{2} {2} {2} {2}
{3} {3} {3}
{1,3} {4} {4}
{2,3} {1,3} {5}
{1,4} {1,3}
{2,3} {1,4}
{3,4} {1,5}
{2,3,4} {2,3}
{2,5}
{3,4}
{3,5}
{4,5}
{1,3,5}
{2,3,4}
{3,4,5}
{2,3,4,5}
For all differences of pairs of elements we have
A007865.
The complement is counted by
A364466.
A364465 counts subsets with distinct first differences, partitions
A325325.
Cf.
A011782,
A025065,
A229816,
A236912,
A237113,
A237667,
A240861,
A320347,
A323092,
A326083,
A364347.
-
Table[Length[Select[Subsets[Range[n]],Intersection[#,Differences[#]]=={}&]],{n,0,10}]
-
from itertools import combinations
def A364463(n): return sum(1 for l in range(n+1) for c in combinations(range(1,n+1),l) if set(c).isdisjoint({c[i+1]-c[i] for i in range(l-1)})) # Chai Wah Wu, Sep 26 2023
A364464
Number of strict integer partitions of n where no part is the difference of two consecutive parts.
Original entry on oeis.org
1, 1, 1, 1, 2, 3, 2, 4, 4, 6, 5, 8, 9, 12, 13, 16, 16, 21, 23, 29, 34, 38, 41, 49, 57, 64, 73, 86, 95, 110, 120, 135, 160, 171, 197, 219, 247, 277, 312, 342, 386, 431, 476, 527, 598, 640, 727, 796, 893, 966, 1097, 1178, 1327, 1435, 1602, 1740, 1945, 2084, 2337
Offset: 0
The strict partition y = (9,5,3,1) has differences (4,2,2), and these are disjoint from the parts, so y is counted under a(18).
The a(1) = 1 through a(9) = 6 strict partitions:
(1) (2) (3) (4) (5) (6) (7) (8) (9)
(3,1) (3,2) (5,1) (4,3) (5,3) (5,4)
(4,1) (5,2) (6,2) (7,2)
(6,1) (7,1) (8,1)
(4,3,2)
(5,3,1)
For length instead of differences we have
A240861, non-strict
A229816.
For all differences of pairs of elements we have
A364346, for subsets
A007865.
For subsets instead of strict partitions we have
A364463, complement
A364466.
A320347 counts strict partitions w/ distinct differences, non-strict
A325325.
-
Table[Length[Select[IntegerPartitions[n],UnsameQ@@#&&Intersection[#,-Differences[#]]=={}&]],{n,0,15}]
-
from collections import Counter
from sympy.utilities.iterables import partitions
def A364464(n): return sum(1 for s,p in map(lambda x: (x[0],tuple(sorted(Counter(x[1]).elements()))), filter(lambda p:max(p[1].values(),default=1)==1,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
A364467
Number of integer partitions of n where some part is the difference of two consecutive parts.
Original entry on oeis.org
0, 0, 0, 1, 1, 2, 4, 5, 9, 13, 21, 28, 42, 55, 78, 106, 144, 187, 255, 325, 429, 554, 717, 906, 1165, 1460, 1853, 2308, 2899, 3582, 4468, 5489, 6779, 8291, 10173, 12363, 15079, 18247, 22124, 26645, 32147, 38555, 46285, 55310, 66093, 78684, 93674, 111104
Offset: 0
The a(3) = 1 through a(9) = 13 partitions:
(21) (211) (221) (42) (421) (422) (63)
(2111) (321) (2221) (431) (621)
(2211) (3211) (521) (3321)
(21111) (22111) (3221) (4221)
(211111) (4211) (4311)
(22211) (5211)
(32111) (22221)
(221111) (32211)
(2111111) (42111)
(222111)
(321111)
(2211111)
(21111111)
For all differences of pairs parts we have
A363225, complement
A364345.
The complement is counted by
A363260.
These partitions have ranks
A364537.
A325325 counts partitions with distinct first differences.
Cf.
A002865,
A025065,
A093971,
A108917,
A196723,
A229816,
A236912,
A237113,
A237667,
A320347,
A326083.
-
Table[Length[Select[IntegerPartitions[n],Intersection[#,-Differences[#]]!={}&]],{n,0,30}]
-
from collections import Counter
from sympy.utilities.iterables import partitions
def A364467(n): return sum(1 for s,p in map(lambda x: (x[0],tuple(sorted(Counter(x[1]).elements()))), partitions(n,size=True)) if not set(p).isdisjoint({p[i+1]-p[i] for i in range(s-1)})) # Chai Wah Wu, Sep 26 2023
A364536
Number of strict integer partitions of n where some part is a difference of two consecutive parts.
Original entry on oeis.org
0, 0, 0, 1, 0, 0, 2, 1, 2, 2, 5, 4, 6, 6, 9, 11, 16, 17, 23, 25, 30, 38, 48, 55, 65, 78, 92, 106, 127, 146, 176, 205, 230, 277, 315, 366, 421, 483, 552, 640, 727, 829, 950, 1083, 1218, 1408, 1577, 1794, 2017, 2298, 2561, 2919, 3255, 3685, 4116, 4638, 5163
Offset: 0
The a(3) = 1 through a(15) = 11 partitions (A = 10, B = 11, C = 12):
21 . . 42 421 431 63 532 542 84 742 743 A5
321 521 621 541 632 642 841 752 843
631 821 651 A21 761 942
721 5321 921 5431 842 C21
4321 5421 6421 B21 6432
6321 7321 6431 6531
6521 7431
7421 7521
8321 8421
9321
54321
A325325 counts partitions with distinct first-differences, strict
A320347.
-
Table[Length[Select[IntegerPartitions[n],UnsameQ@@#&&Intersection[#,-Differences[#]]!={}&]],{n,0,30}]
-
from collections import Counter
from sympy.utilities.iterables import partitions
def A364536(n): return sum(1 for s,p in map(lambda x: (x[0],tuple(sorted(Counter(x[1]).elements()))), filter(lambda p:max(p[1].values(),default=1)==1,partitions(n,size=True))) if not set(p).isdisjoint({p[i+1]-p[i] for i in range(s-1)})) # Chai Wah Wu, Sep 26 2023
A364537
Heinz numbers of integer partitions where some part is the difference of two consecutive parts.
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, 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, 258
Offset: 1
The partition {3,4,5,7} with Heinz number 6545 has first differences (1,1,2) so is not in the sequence.
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}
78: {1,2,6}
84: {1,1,2,4}
90: {1,2,2,3}
96: {1,1,1,1,1,2}
For all differences of pairs the complement is
A364347, counted by
A364345.
Subsets of {1..n} of this type are counted by
A364466, complement
A364463.
A325325 counts partitions with distinct first differences.
Cf.
A002865,
A025065,
A093971,
A108917,
A196723,
A229816,
A236912,
A237113,
A237667,
A320347,
A326083.
-
prix[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100],Intersection[prix[#],Differences[prix[#]]]!={}&]
Comments