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
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 *)
A365322
Number of subsets of {1..n} that cannot be linearly combined using positive coefficients to obtain n.
Original entry on oeis.org
0, 1, 2, 5, 11, 26, 54, 116, 238, 490, 994, 2011, 4045, 8131, 16305, 32672, 65412, 130924, 261958, 524066, 1048301, 2096826, 4193904, 8388135, 16776641, 33553759, 67108053, 134216782, 268434324, 536869595, 1073740266, 2147481835, 4294965158, 8589932129
Offset: 0
The set {1,3} has 4 = 1 + 3 so is not counted under a(4). However, 3 cannot be written as a linear combination of {1,3} using all positive coefficients, so it is counted under a(3).
The a(1) = 1 through a(4) = 11 subsets:
{} {} {} {}
{1,2} {2} {3}
{1,3} {1,4}
{2,3} {2,3}
{1,2,3} {2,4}
{3,4}
{1,2,3}
{1,2,4}
{1,3,4}
{2,3,4}
{1,2,3,4}
The complement is counted by
A088314.
The version for strict partitions is
A088528.
For nonnegative coefficients we have
A365380.
A085489 and
A364755 count subsets without the sum of two distinct elements.
A124506 appears to count combination-free subsets, differences of
A326083.
A364350 counts combination-free strict partitions, non-strict
A364915.
A365046 counts combination-full subsets, first differences of
A364914.
-
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-> 2^n-nops(b(n$2)):
seq(a(n), n=0..33); # Alois P. Heinz, Sep 04 2023
-
cpu[n_,y_]:=With[{s=Table[{k,i},{k,Union[y]},{i,1,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[Subsets[Range[n]],cpu[n,#]=={}&]],{n,0,10}]
-
from sympy.utilities.iterables import partitions
def A365322(n): return (1<Chai Wah Wu, Sep 14 2023
A365045
Number of subsets of {1..n} containing n such that no element can be written as a positive linear combination of the others.
Original entry on oeis.org
0, 1, 1, 2, 4, 11, 23, 53, 111, 235, 483, 988, 1998, 4036, 8114, 16289, 32645, 65389, 130887, 261923, 524014, 1048251, 2096753, 4193832, 8388034, 16776544, 33553622, 67107919, 134216597, 268434140, 536869355, 1073740012, 2147481511, 4294964834, 8589931700
Offset: 0
The subset {3,4,10} has 10 = 2*3 + 1*4 so is not counted under a(10).
The a(0) = 0 through a(5) = 11 subsets:
. {1} {2} {3} {4} {5}
{2,3} {3,4} {2,5}
{2,3,4} {3,5}
{1,2,3,4} {4,5}
{2,4,5}
{3,4,5}
{1,2,3,5}
{1,2,4,5}
{1,3,4,5}
{2,3,4,5}
{1,2,3,4,5}
Without re-usable parts we have
A365071, first differences of
A151897.
A085489 and
A364755 count subsets w/o the sum of two distinct elements.
A088809 and
A364756 count subsets with the 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[Subsets[Range[n]],MemberQ[#,n]&&And@@Table[combp[#[[k]],Union[Delete[#,k]]]=={},{k,Length[#]}]&]],{n,0,10}]
A365314
Number of unordered pairs of distinct positive integers <= n that can be linearly combined using nonnegative coefficients to obtain n.
Original entry on oeis.org
0, 0, 1, 3, 6, 8, 14, 14, 23, 24, 33, 28, 52, 36, 55, 58, 73, 53, 95, 62, 110, 94, 105, 81, 165, 105, 133, 132, 176, 112, 225, 123, 210, 174, 192, 186, 306, 157, 223, 218, 328, 180, 354, 192, 324, 315, 288, 216, 474, 260, 383, 311, 404, 254, 491, 338, 511, 360
Offset: 0
We have 19 = 4*3 + 1*7, so the pair (3,7) is counted under a(19).
The a(2) = 1 through a(7) = 14 pairs:
(1,2) (1,2) (1,2) (1,2) (1,2) (1,2)
(1,3) (1,3) (1,3) (1,3) (1,3)
(2,3) (1,4) (1,4) (1,4) (1,4)
(2,3) (1,5) (1,5) (1,5)
(2,4) (2,3) (1,6) (1,6)
(3,4) (2,5) (2,3) (1,7)
(3,5) (2,4) (2,3)
(4,5) (2,5) (2,5)
(2,6) (2,7)
(3,4) (3,4)
(3,5) (3,7)
(3,6) (4,7)
(4,6) (5,7)
(5,6) (6,7)
For all subsets instead of just pairs we have
A365073, complement
A365380.
The case of positive coefficients is
A365315, for all subsets
A088314.
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 A365314(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 len(a) # Chai Wah Wu, Sep 12 2023
A365321
Number of pairs of distinct positive integers <= n that cannot be linearly combined with positive coefficients to obtain n.
Original entry on oeis.org
0, 0, 1, 2, 4, 6, 10, 13, 18, 24, 30, 37, 46, 54, 63, 77, 85, 99, 111, 127, 141, 161, 171, 194, 210, 235, 246, 277, 293, 322, 342, 372, 389, 428, 441, 491, 504, 545, 561, 612, 635, 680, 701, 753, 773, 836, 846, 911, 932, 1000, 1017, 1082, 1103, 1176, 1193
Offset: 0
For the pair p = (2,3) we have 4 = 2*2 + 0*3, so p is not counted under A365320(4), but it is not possible to write 4 as a positive linear combination of 2 and 3, so p is counted under a(4).
The a(2) = 1 through a(7) = 13 pairs:
(1,2) (1,3) (1,4) (1,5) (1,6) (1,7)
(2,3) (2,3) (2,4) (2,3) (2,4)
(2,4) (2,5) (2,5) (2,6)
(3,4) (3,4) (2,6) (2,7)
(3,5) (3,4) (3,5)
(4,5) (3,5) (3,6)
(3,6) (3,7)
(4,5) (4,5)
(4,6) (4,6)
(5,6) (4,7)
(5,6)
(5,7)
(6,7)
For all subsets instead of just pairs we have
A365322, complement
A088314.
A004526 counts partitions of length 2, shift right for strict.
A364350 counts combination-free strict partitions.
Cf.
A070880,
A088571,
A088809,
A151897,
A326020,
A365043,
A365073,
A365311,
A365312,
A365378,
A365380.
-
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 A365321(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 (n*(n-1)>>1)-len(a) # Chai Wah Wu, Sep 12 2023
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
Showing 1-8 of 8 results.
Comments