A088314
Cardinality of set of sets of parts of all partitions of n.
Original entry on oeis.org
1, 1, 2, 3, 5, 6, 10, 12, 18, 22, 30, 37, 51, 61, 79, 96, 124, 148, 186, 222, 275, 326, 400, 473, 575, 673, 811, 946, 1132, 1317, 1558, 1813, 2138, 2463, 2893, 3323, 3882, 4461, 5177, 5917, 6847, 7818, 8994, 10251, 11766, 13334, 15281, 17309, 19732, 22307
Offset: 0
The 7 partitions of 5 and their sets of parts are
[ #] partition set of parts
[ 1] [ 1 1 1 1 1 ] {1}
[ 2] [ 2 1 1 1 ] {1, 2}
[ 3] [ 2 2 1 ] {1, 2} (same as before)
[ 4] [ 3 1 1 ] {1, 3}
[ 5] [ 3 2 ] {2, 3}
[ 6] [ 4 1 ] {1, 4}
[ 7] [ 5 ] {5}
so we have a(5) = |{{1}, {1, 2}, {1, 3}, {2, 3}, {1, 4}, {5}}| = 6.
-
a066186 = sum . concat . ps 1 where
ps _ 0 = [[]]
ps i j = [t:ts | t <- [i..j], ts <- ps t (j - t)]
-- Reinhard Zumkeller, Jul 13 2013
-
list2set := L -> {op(L)};
a:= N -> list2set(map( list2set, combinat[partition](N) ));
seq(nops(a(n)), n=0..30);
# Yogy Namara (yogy.namara(AT)gmail.com), Jan 13 2010
b:= proc(n, i) option remember; `if`(n=0, {{}}, `if`(i<1, {},
{b(n, i-1)[], seq(map(x->{x[],i}, b(n-i*j, i-1))[], j=1..n/i)}))
end:
a:= n-> nops(b(n, n)):
seq(a(n), n=0..40);
# Alois P. Heinz, Aug 09 2012
-
Table[Length[Union[Map[Union,IntegerPartitions[n]]]],{n,1,30}] (* Geoffrey Critzer, Feb 19 2013 *)
(* Second program: *)
b[n_, i_] := b[n, i] = If[n == 0, {{}}, If[i < 1, {},
Union@Flatten@{b[n, i - 1], Table[If[Head[#] == List,
Append[#, i]]& /@ b[n - i*j, i - 1], {j, 1, n/i}]}]];
a[n_] := Length[b[n, n]];
a /@ Range[0, 40] (* Jean-François Alcover, Jun 04 2021, after Alois P. Heinz *)
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@@Array[IntegerPartitions,n], UnsameQ@@#&&combp[n,#]!={}&]], {n,0,15}] (* Gus Wiseman, Sep 11 2023 *)
-
from sympy.utilities.iterables import partitions
def A088314(n): return len({tuple(sorted(set(p))) for p in partitions(n)}) # Chai Wah Wu, Sep 10 2023
A367215
Number of strict integer partitions of n whose length (number of parts) is not equal to the sum of any subset.
Original entry on oeis.org
0, 0, 1, 1, 2, 2, 2, 3, 3, 4, 5, 7, 8, 10, 12, 15, 18, 21, 25, 29, 34, 40, 46, 53, 62, 71, 82, 95, 109, 124, 143, 162, 185, 210, 240, 270, 308, 347, 393, 443, 500, 562, 634, 711, 798, 895, 1002, 1120, 1252, 1397, 1558, 1735, 1930, 2146, 2383, 2644, 2930, 3245
Offset: 0
The a(2) = 1 through a(11) = 7 strict partitions:
(2) (3) (4) (5) (6) (7) (8) (9) (10) (11)
(3,1) (4,1) (5,1) (4,3) (5,3) (5,4) (6,4) (6,5)
(6,1) (7,1) (6,3) (7,3) (7,4)
(8,1) (9,1) (8,3)
(5,4,1) (10,1)
(5,4,2)
(6,4,1)
The a(2) = 1 through a(15) = 15 strict partitions (A..F = 10..15):
2 3 4 5 6 7 8 9 A B C D E F
31 41 51 43 53 54 64 65 75 76 86 87
61 71 63 73 74 84 85 95 96
81 91 83 93 94 A4 A5
541 A1 B1 A3 B3 B4
542 642 C1 D1 C3
641 651 652 752 E1
741 742 761 654
751 842 762
841 851 852
941 861
6521 942
951
A41
7521
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.
A240861 counts strict partitions with length not a part, complement
A240855.
Triangles:
A365661 counts strict partitions with a subset-sum k, non-strict
A365543.
A365663 counts strict partitions without a subset-sum k, non-strict
A046663.
-
Table[Length[Select[IntegerPartitions[n], UnsameQ@@#&&FreeQ[Total/@Subsets[#], Length[#]]&]], {n,0,30}]
A367219
Number of integer partitions of n whose length cannot be written as a nonnegative linear combination of the distinct parts.
Original entry on oeis.org
0, 0, 1, 1, 1, 1, 3, 2, 4, 4, 7, 6, 11, 9, 16, 16, 23, 22, 35, 33, 48, 50, 69, 70, 99, 99, 136, 142, 187, 194, 261, 267, 346, 367, 468, 489, 626, 650, 824, 870, 1081, 1135, 1421, 1485, 1833, 1942, 2374, 2501, 3062, 3220, 3915, 4145, 4987, 5274, 6363, 6709, 8027
Offset: 0
3 cannot be written as a nonnegative linear combination of 2 and 5, so (5,2,2) is counted under a(9).
The a(2) = 1 through a(10) = 7 partitions:
(2) (3) (4) (5) (6) (7) (8) (9) (10)
(3,3) (4,3) (4,4) (5,4) (5,5)
(2,2,2) (5,3) (6,3) (6,4)
(4,2,2) (5,2,2) (7,3)
(4,4,2)
(6,2,2)
(2,2,2,2,2)
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.
-
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],combs[Length[#],Union[#]]=={}&]],{n,0,15}]
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}]
A367223
Number of subsets of {1..n} whose cardinality cannot be written as a nonnegative linear combination of the elements.
Original entry on oeis.org
0, 0, 1, 2, 4, 8, 15, 27, 49, 90, 165, 301, 548, 998, 1819, 3316, 6040, 10986, 19959, 36253, 65904, 119986, 218796, 399461, 729752, 1333162, 2434411, 4441954, 8097478, 14746715, 26830230, 48773790, 88605927, 160900978, 292140427, 530487359, 963610200, 1751171679, 3183997509
Offset: 0
3 cannot be written as a nonnegative linear combination of 2, 4, and 5, so {2,4,5} is counted under a(6).
The a(2) = 1 through a(6) = 15 subsets:
{2} {2} {2} {2} {2}
{3} {3} {3} {3}
{4} {4} {4}
{3,4} {5} {5}
{3,4} {6}
{3,5} {3,4}
{4,5} {3,5}
{2,4,5} {3,6}
{4,5}
{4,6}
{5,6}
{2,4,5}
{2,4,6}
{2,5,6}
{4,5,6}
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:
A116861 counts positive linear combinations of strict partitions of k.
A364916 counts linear combinations of strict partitions of k.
Cf.
A068911,
A088314,
A103580,
A237667,
A326020,
A326080,
A364350,
A365073,
A365312,
A365377,
A365380.
-
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 A367223(n):
c, mlist = 0, []
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:
break
else:
c += 1
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[#]]]=={}&]
A365311
Number of strict integer partitions with sum <= n that can be linearly combined using nonnegative coefficients to obtain n.
Original entry on oeis.org
0, 1, 2, 3, 5, 6, 11, 12, 20, 24, 35, 38, 63, 63, 92, 112, 148, 160, 230, 244, 339, 383, 478, 533, 726, 781, 978, 1123, 1394, 1526, 1960, 2112, 2630, 2945, 3518, 3964, 4856, 5261, 6307, 7099, 8464, 9258, 11140, 12155, 14419, 16093, 18589, 20565, 24342, 26597, 30948
Offset: 0
The strict partition (6,3) cannot be linearly combined to obtain 10, so is not counted under a(10).
The strict partition (4,2) has 6 = 1*4 + 1*2 so is counted under a(6), but (4,2) cannot be linearly combined to obtain 7 so is not counted under a(7).
The a(1) = 1 through a(7) = 12 strict partitions:
(1) (1) (1) (1) (1) (1) (1)
(2) (3) (2) (5) (2) (7)
(2,1) (4) (2,1) (3) (2,1)
(2,1) (3,1) (6) (3,1)
(3,1) (3,2) (2,1) (3,2)
(4,1) (3,1) (4,1)
(3,2) (4,3)
(4,1) (5,1)
(4,2) (5,2)
(5,1) (6,1)
(3,2,1) (3,2,1)
(4,2,1)
For positive coefficients we have
A088314.
The positive complement is counted by
A088528.
The version for subsets is
A365073.
The complement is counted by
A365312.
For non-strict partitions we have
A365379.
A364350 counts combination-free strict partitions, non-strict
A364915.
A364839 counts combination-full strict partitions, non-strict
A364913.
Cf.
A093971,
A237113,
A237668,
A326080,
A363225,
A364272,
A364534,
A364914,
A365043,
A365314,
A365320.
-
combs[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,0,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[Select[Join@@Array[IntegerPartitions,n],UnsameQ@@#&],combs[n,#]!={}&]],{n,10}]
-
from math import isqrt
from sympy.utilities.iterables import partitions
def A365311(n):
a = {tuple(sorted(set(p))) for p in partitions(n)}
return sum(1 for m in range(1,n+1) for b in partitions(m,m=isqrt(1+(n<<3))>>1) if max(b.values()) == 1 and any(set(d).issubset(set(b)) for d in a)) # Chai Wah Wu, Sep 13 2023
A365320
Number of pairs of distinct positive integers <= n that cannot be linearly combined with nonnegative coefficients to obtain n.
Original entry on oeis.org
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
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)
The case of positive coefficients is
A365321, for all subsets
A365322.
For all subsets instead of just pairs we have
A365380, complement
A365073.
A004526 counts partitions of length 2, shift right for strict.
A364350 counts combination-free strict partitions.
-
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}]
-
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
A088528
Let m = number of ways of partitioning n into parts using all the parts of a subset of {1, 2, ..., n-1} whose sum of all parts of a subset is less than n; a(n) gives number of different subsets of {1, 2, ..., n-1} whose m is 0.
Original entry on oeis.org
0, 0, 1, 1, 3, 3, 6, 6, 10, 12, 17, 18, 26, 30, 40, 44, 58, 66, 84, 95, 120, 135, 166, 186, 230, 257, 314, 350, 421, 476, 561, 626, 749, 831, 986, 1095, 1276, 1424, 1666, 1849, 2138, 2388, 2741, 3042, 3522, 3879, 4441, 4928, 5617, 6222, 7084, 7802, 8852, 9800
Offset: 1
a(5)=3 because there are three different subsets, {2}, {3} & {4}; a(6)=3 because there are three different subsets, {4}, {5} & {2,3}.
From _Gus Wiseman_, Sep 10 2023: (Start)
The set {3,5} is not counted under a(8) because 1*3 + 1*5 = 8, but it is counted under a(9) and a(10), and it is not counted under a(11) because 2*3 + 1*5 = 11.
The a(3) = 1 through a(11) = 17 subsets:
{2} {3} {2} {4} {2} {3} {2} {3} {2}
{3} {5} {3} {5} {4} {4} {3}
{4} {2,3} {4} {6} {5} {6} {4}
{5} {7} {6} {7} {5}
{6} {2,5} {7} {8} {6}
{2,4} {3,4} {8} {9} {7}
{2,4} {2,5} {8}
{2,6} {2,7} {9}
{3,4} {3,5} {10}
{3,5} {3,6} {2,4}
{4,5} {2,6}
{2,3,4} {2,8}
{3,6}
{3,7}
{4,5}
{4,6}
{2,3,5}
(End)
For sets with max < n instead of sum < n we have
A365045, nonempty
A070880.
For sets with max <= n we have
A365322.
-
combp[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,1,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[Select[Subsets[Range[n]],0Gus Wiseman, Sep 12 2023 *)
Showing 1-10 of 17 results.
Comments