A370586
Number of subsets of {1..n} containing n such that it is possible to choose a different prime factor of each element (choosable).
Original entry on oeis.org
0, 0, 1, 2, 2, 6, 8, 20, 12, 20, 44, 116, 88, 320, 380, 508, 264, 1792, 968, 4552, 3136, 5600, 10056, 27896, 11792, 16384, 46688, 19584, 48288, 198528, 110928, 507984, 99648, 463552, 859376, 821136, 470688, 3730368, 4033920, 4651296, 2932512, 19078464
Offset: 0
The a(0) = 0 through a(7) = 20 subsets:
. . {2} {3} {4} {5} {6} {7}
{2,3} {3,4} {2,5} {2,6} {2,7}
{3,5} {3,6} {3,7}
{4,5} {4,6} {4,7}
{2,3,5} {5,6} {5,7}
{3,4,5} {2,5,6} {6,7}
{3,5,6} {2,3,7}
{4,5,6} {2,5,7}
{2,6,7}
{3,4,7}
{3,5,7}
{3,6,7}
{4,5,7}
{4,6,7}
{5,6,7}
{2,3,5,7}
{2,5,6,7}
{3,4,5,7}
{3,5,6,7}
{4,5,6,7}
Maximal choosable sets are counted by
A370585.
The complement is counted by
A370587.
For a unique choice we have
A370588.
For binary indices instead of prime factors we have
A370639.
A355741 counts choices of a prime factor of each prime index.
A368098 counts choosable unlabeled multiset partitions, complement
A368097.
Cf.
A000040,
A000720,
A005117,
A045778,
A133686,
A355739,
A355744,
A355745,
A367771,
A367905,
A370636.
-
Table[Length[Select[Subsets[Range[n]], MemberQ[#,n]&&Length[Select[Tuples[If[#==1, {},First/@FactorInteger[#]]&/@#], UnsameQ@@#&]]>0&]],{n,0,10}]
A370594
Number of integer partitions of n such that only one set can be obtained by choosing a different prime factor of each part.
Original entry on oeis.org
1, 0, 1, 1, 1, 2, 0, 3, 3, 4, 3, 4, 5, 5, 8, 10, 11, 7, 14, 13, 19, 23, 24, 20, 30, 33, 40, 47, 49, 55, 53, 72, 80, 90, 92, 110, 110, 132, 154, 169, 180, 201, 218, 246, 281, 302, 323, 348, 396, 433, 482, 530, 584, 618, 670, 754, 823, 903, 980, 1047, 1137
Offset: 0
The partition (10,6,4) has unique choice (5,3,2) so is counted under a(20).
The a(0) = 1 through a(12) = 5 partitions:
() . (2) (3) (4) (5) . (7) (8) (9) (6,4) (11) (6,6)
(3,2) (4,3) (5,3) (5,4) (7,3) (7,4) (7,5)
(5,2) (6,2) (6,3) (5,3,2) (8,3) (10,2)
(7,2) (9,2) (5,4,3)
(7,3,2)
Maximal sets of this type are counted by
A370585.
For divisors instead of factors we have
A370595.
These partitions have ranks
A370647.
A355741 counts ways to choose a prime factor of each prime index.
-
Table[Length[Select[IntegerPartitions[n], Length[Union[Sort/@Select[Tuples[If[#==1, {},First/@FactorInteger[#]]&/@#], UnsameQ@@#&]]]==1&]],{n,0,30}]
A368600
Number of ways to choose a set of n nonempty subsets of {1..n} such that it is not possible to choose a different element from each.
Original entry on oeis.org
0, 0, 0, 3, 164, 18625, 5491851, 4649088885, 12219849683346
Offset: 0
The a(3) = 3 set-systems:
{{1},{2},{1,2}}
{{1},{3},{1,3}}
{{2},{3},{2,3}}
Sets of n nonempty subsets of {1..n} are counted by
A136556.
A059201 counts covering T_0 set-systems.
Cf.
A003025,
A088957,
A133686,
A334282,
A355529,
A355740,
A367862,
A367867,
A367868,
A367901,
A368094,
A368097.
-
Table[Length[Select[Subsets[Rest[Subsets[Range[n]]], {n}],Length[Select[Tuples[#], UnsameQ@@#&]]==0&]],{n,0,3}]
-
from itertools import combinations, product, chain
from scipy.special import comb
def v(c):
for elements in product(*c):
if len(set(elements)) == len(elements):
return True
return False
def a(n):
if n == 0:
return 1
subsets = list(chain.from_iterable(combinations(range(1, n + 1), r) for r in range(1, n + 1)))
cs = combinations(subsets, n)
c = sum(1 for c in cs if v(c))
return c
[print(int(comb(2**n-1,n) - a(n))) for n in range(7)] # Robert P. P. McKone, Jan 02 2024
A368601
Number of ways to choose a set of n nonempty subsets of {1..n} such that it is possible to choose a different element from each.
Original entry on oeis.org
1, 1, 3, 32, 1201, 151286, 62453670, 84707326890, 384641855115279
Offset: 0
The a(2) = 3 set-systems:
{{1},{2}}
{{1},{1,2}}
{{2},{1,2}}
Non-isomorphic representatives of the a(3) = 32 set-systems:
{{1},{2},{3}}
{{1},{2},{1,3}}
{{1},{2},{1,2,3}}
{{1},{1,2},{1,3}}
{{1},{1,2},{2,3}}
{{1},{1,2},{1,2,3}}
{{1},{2,3},{1,2,3}}
{{1,2},{1,3},{2,3}}
{{1,2},{1,3},{1,2,3}}
Sets of n nonempty subsets of {1..n} are counted by
A136556.
A059201 counts covering T_0 set-systems.
Cf.
A003025,
A088957,
A133686,
A334282,
A355529,
A355740,
A367862,
A367867,
A367901,
A367905,
A368094,
A368097.
-
Table[Length[Select[Subsets[Rest[Subsets[Range[n]]], {n}],Length[Select[Tuples[#], UnsameQ@@#&]]>0&]],{n,0,3}]
-
from itertools import combinations, product, chain
def v(c):
for elements in product(*c):
if len(set(elements)) == len(elements):
return True
return False
def a(n):
if n == 0:
return 1
subsets = list(chain.from_iterable(combinations(range(1, n + 1), r) for r in
range(1, n + 1)))
cs = combinations(subsets, n)
c = sum(1 for c in cs if v(c))
return c
[print(a(n)) for n in range(7)] # Robert P. P. McKone, Jan 02 2024
A371171
Number of integer partitions of n with more parts than distinct divisors of parts.
Original entry on oeis.org
0, 0, 1, 1, 2, 4, 5, 9, 12, 18, 26, 34, 50, 65, 92, 121, 161, 209, 274, 353, 456, 590, 745, 950, 1195, 1507, 1885, 2350, 2923, 3611, 4465, 5485, 6735, 8223, 10050, 12195, 14822, 17909, 21653, 26047, 31340, 37557, 44990, 53708, 64068, 76241, 90583, 107418
Offset: 1
The partition (3,2,1,1) has 4 parts {1,2,3,4} and 3 distinct divisors of parts {1,2,3}, so is counted under a(7).
The a(0) = 0 through a(8) = 12 partitions:
. . (11) (111) (211) (221) (222) (331) (2222)
(1111) (311) (2211) (511) (3221)
(2111) (3111) (2221) (3311)
(11111) (21111) (3211) (4211)
(111111) (4111) (5111)
(22111) (22211)
(31111) (32111)
(211111) (41111)
(1111111) (221111)
(311111)
(2111111)
(11111111)
The partitions are ranked by
A370348.
For submultisets instead of parts on the LHS we get ranks
A371167.
-
Table[Length[Select[IntegerPartitions[n],Length[#] > Length[Union@@Divisors/@#]&]],{n,0,30}]
A371177
Positive integers whose prime indices include all distinct divisors of all prime indices.
Original entry on oeis.org
1, 2, 4, 6, 8, 10, 12, 16, 18, 20, 22, 24, 30, 32, 34, 36, 40, 42, 44, 48, 50, 54, 60, 62, 64, 66, 68, 72, 80, 82, 84, 88, 90, 96, 100, 102, 108, 110, 118, 120, 124, 126, 128, 132, 134, 136, 144, 150, 160, 162, 164, 166, 168, 170, 176, 180, 186, 192, 198, 200
Offset: 1
The terms together with their prime indices begin:
1: {}
2: {1}
4: {1,1}
6: {1,2}
8: {1,1,1}
10: {1,3}
12: {1,1,2}
16: {1,1,1,1}
18: {1,2,2}
20: {1,1,3}
22: {1,5}
24: {1,1,1,2}
30: {1,2,3}
32: {1,1,1,1,1}
34: {1,7}
36: {1,1,2,2}
40: {1,1,1,3}
42: {1,2,4}
44: {1,1,5}
48: {1,1,1,1,2}
A008284 counts partitions by length.
-
Select[Range[100],PrimeNu[#]==Length[Union @@ Divisors/@PrimePi/@First/@If[#==1,{},FactorInteger[#]]]&]
A355535
Odd numbers of which it is not possible to choose a different prime factor of each prime index.
Original entry on oeis.org
9, 21, 25, 27, 45, 49, 57, 63, 75, 81, 99, 105, 115, 117, 121, 125, 133, 135, 147, 153, 159, 171, 175, 189, 195, 207, 225, 231, 243, 245, 261, 273, 275, 279, 285, 289, 297, 315, 325, 333, 343, 345, 351, 357, 361, 363, 369, 371, 375, 387, 393, 399, 405, 423
Offset: 1
The terms together with their prime indices begin:
9: {2,2}
21: {2,4}
25: {3,3}
27: {2,2,2}
45: {2,2,3}
49: {4,4}
57: {2,8}
63: {2,2,4}
75: {2,3,3}
81: {2,2,2,2}
99: {2,2,5}
105: {2,3,4}
For example, the prime indices of 897 are {2,6,9}, of which we can choose prime factors in two ways: (2,2,3) or (2,3,3); but neither of these has all distinct elements, so 897 is in the sequence.
The version for all divisors including evens is
A355740, zeros of
A355739.
Choices of a prime factor of each prime index:
A355741, unordered
A355744.
A001222 counts prime factors with multiplicity.
A003963 multiplies together the prime indices of n.
A120383 lists numbers divisible by all of their prime indices.
-
primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100],OddQ[#]&&Select[Tuples[primeMS/@primeMS[#]],UnsameQ@@#&]=={}&]
A370595
Number of integer partitions of n such that only one set can be obtained by choosing a different divisor of each part.
Original entry on oeis.org
1, 1, 0, 1, 2, 0, 3, 2, 4, 3, 4, 5, 8, 9, 8, 13, 12, 17, 16, 27, 28, 33, 36, 39, 50, 58, 65, 75, 93, 94, 112, 125, 148, 170, 190, 209, 250, 273, 305, 341, 403, 432, 484, 561, 623, 708, 765, 873, 977, 1109, 1178, 1367, 1493, 1669, 1824, 2054, 2265, 2521, 2770
Offset: 0
The a(1) = 1 through a(15) = 13 partitions (A = 10, B = 11, C = 12, D = 13):
1 . 21 22 . 33 322 71 441 55 533 B1 553 77 933
31 51 421 332 522 442 722 444 733 D1 B22
321 422 531 721 731 552 751 B21 B31
521 4321 4322 4332 931 4433 4443
5321 4431 4432 5441 5442
5322 5332 6332 5532
5421 5422 7322 6621
6321 6322 7421 7332
7321 7422
7521
8421
9321
54321
The version for prime factors (not all divisors) is
A370594, ranks
A370647.
These partitions have ranks
A370810.
A355731 counts choices of a divisor of each prime index, firsts
A355732.
A370592 counts partitions with choosable prime factors, ranks
A368100.
A370593 counts partitions without choosable prime factors, ranks
A355529.
A370804 counts non-condensed partitions with no ones, complement
A370805.
A370814 counts factorizations with choosable divisors, complement
A370813.
-
Table[Length[Select[IntegerPartitions[n],Length[Union[Sort /@ Select[Tuples[Divisors/@#],UnsameQ@@#&]]]==1&]],{n,0,30}]
A371165
Positive integers with as many divisors (A000005) as distinct divisors of prime indices (A370820).
Original entry on oeis.org
3, 5, 11, 17, 26, 31, 35, 38, 39, 41, 49, 57, 58, 59, 65, 67, 69, 77, 83, 86, 87, 94, 109, 119, 127, 129, 133, 146, 148, 157, 158, 179, 191, 202, 206, 211, 217, 235, 237, 241, 244, 253, 274, 277, 278, 283, 284, 287, 291, 298, 303, 319, 326, 331, 333, 334, 353
Offset: 1
The terms together with their prime indices begin:
3: {2} 67: {19} 158: {1,22}
5: {3} 69: {2,9} 179: {41}
11: {5} 77: {4,5} 191: {43}
17: {7} 83: {23} 202: {1,26}
26: {1,6} 86: {1,14} 206: {1,27}
31: {11} 87: {2,10} 211: {47}
35: {3,4} 94: {1,15} 217: {4,11}
38: {1,8} 109: {29} 235: {3,15}
39: {2,6} 119: {4,7} 237: {2,22}
41: {13} 127: {31} 241: {53}
49: {4,4} 129: {2,14} 244: {1,1,18}
57: {2,8} 133: {4,8} 253: {5,9}
58: {1,10} 146: {1,21} 274: {1,33}
59: {17} 148: {1,1,12} 277: {59}
65: {3,6} 157: {37} 278: {1,34}
For prime factors instead of divisors on both sides we get
A319899.
For prime factors on LHS we get
A370802, for distinct prime factors
A371177.
For (greater than) instead of (equal) we get
A371166.
For (less than) instead of (equal) we get
A371167.
Partitions of this type are counted by
A371172.
A001221 counts distinct prime factors.
A355731 counts choices of a divisor of each prime index, firsts
A355732.
-
Select[Range[100],Length[Divisors[#]] == Length[Union@@Divisors/@PrimePi/@First/@If[#==1,{},FactorInteger[#]]]&]
A371168
Positive integers with fewer prime factors (A001222) than distinct divisors of prime indices (A370820).
Original entry on oeis.org
3, 5, 7, 11, 13, 14, 15, 17, 19, 21, 23, 26, 29, 31, 33, 35, 37, 38, 39, 41, 43, 46, 47, 49, 51, 52, 53, 55, 57, 58, 59, 61, 65, 67, 69, 70, 71, 73, 74, 76, 77, 78, 79, 83, 85, 86, 87, 89, 91, 93, 94, 95, 97, 101, 103, 105, 106, 107, 109, 111, 113, 114, 115
Offset: 1
The prime indices of 105 are {2,3,4}, and there are 3 prime factors (3,5,7) and 4 distinct divisors of prime indices (1,2,3,4), so 105 is in the sequence.
The terms together with their prime indices begin:
3: {2} 35: {3,4} 59: {17} 86: {1,14}
5: {3} 37: {12} 61: {18} 87: {2,10}
7: {4} 38: {1,8} 65: {3,6} 89: {24}
11: {5} 39: {2,6} 67: {19} 91: {4,6}
13: {6} 41: {13} 69: {2,9} 93: {2,11}
14: {1,4} 43: {14} 70: {1,3,4} 94: {1,15}
15: {2,3} 46: {1,9} 71: {20} 95: {3,8}
17: {7} 47: {15} 73: {21} 97: {25}
19: {8} 49: {4,4} 74: {1,12} 101: {26}
21: {2,4} 51: {2,7} 76: {1,1,8} 103: {27}
23: {9} 52: {1,1,6} 77: {4,5} 105: {2,3,4}
26: {1,6} 53: {16} 78: {1,2,6} 106: {1,16}
29: {10} 55: {3,5} 79: {22} 107: {28}
31: {11} 57: {2,8} 83: {23} 109: {29}
33: {2,5} 58: {1,10} 85: {3,7} 111: {2,12}
For divisors instead of prime factors on the LHS we get
A371166.
The complement is counted by
A371169.
Partitions of this type are counted by
A371173.
A001221 counts distinct prime factors.
A355731 counts choices of a divisor of each prime index, firsts
A355732.
Comments