A368413 -id:A368413

Search: a368413 -id:a368413

Displaying 1-10 of 41 results found.

page 1 2 3 4 5

A367903

Number of sets of nonempty subsets of {1..n} contradicting a strict version of the axiom of choice.

+10
66

0, 0, 1, 67, 30997, 2147296425, 9223372036784737528, 170141183460469231731687303625772608225, 57896044618658097711785492504343953926634992332820282019728791606173188627779

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,4

COMMENTS

The axiom of choice says that, given any set of nonempty sets Y, it is possible to choose a set containing an element from each. The strict version requires this set to have the same cardinality as Y, meaning no element is chosen more than once.

LINKS

Table of n, a(n) for n=0..8.

Wikipedia, Axiom of choice.

FORMULA

a(n) + A367904(n) + A367772(n) = A058891(n+1) = 2^(2^n-1).

EXAMPLE

The a(2) = 1 set-system is {{1},{2},{1,2}}.

The a(3) = 67 set-systems have following 21 non-isomorphic representatives:

{{1},{2},{1,2}}

{{1},{2},{3},{1,2}}

{{1},{2},{3},{1,2,3}}

{{1},{2},{1,2},{1,3}}

{{1},{2},{1,2},{1,2,3}}

{{1},{2},{1,3},{2,3}}

{{1},{2},{1,3},{1,2,3}}

{{1},{1,2},{1,3},{2,3}}

{{1},{1,2},{1,3},{1,2,3}}

{{1},{1,2},{2,3},{1,2,3}}

{{1,2},{1,3},{2,3},{1,2,3}}

{{1},{2},{3},{1,2},{1,3}}

{{1},{2},{3},{1,2},{1,2,3}}

{{1},{2},{1,2},{1,3},{2,3}}

{{1},{2},{1,2},{1,3},{1,2,3}}

{{1},{2},{1,3},{2,3},{1,2,3}}

{{1},{1,2},{1,3},{2,3},{1,2,3}}

{{1},{2},{3},{1,2},{1,3},{2,3}}

{{1},{2},{3},{1,2},{1,3},{1,2,3}}

{{1},{2},{1,2},{1,3},{2,3},{1,2,3}}

{{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}

MATHEMATICA

Table[Length[Select[Subsets[Rest[Subsets[Range[n]]]], Select[Tuples[#], UnsameQ@@#&]=={}&]], {n, 0, 3}]

CROSSREFS

Multisets of multisets of this type are ranked by A355529.

The version without singletons is A367769.

The version for simple graphs is A367867, covering A367868.

The version allowing empty edges is A367901.

The complement is A367902, without singletons A367770, ranks A367906.

For a unique choice (instead of none) we have A367904, ranks A367908.

These set-systems have ranks A367907.

An unlabeled version is A368094, for multiset partitions A368097.

A000372 counts antichains, covering A006126, nonempty A014466.

A003465 counts covering set-systems, unlabeled A055621.

A058891 counts set-systems, unlabeled A000612.

A059201 counts covering T_0 set-systems.

A323818 counts covering connected set-systems.

A326031 gives weight of the set-system with BII-number n.

Cf. A007716, A083323, A092918, A102896, A283877, A306445, A355739, A355740, A367862, A367905, A368409, A368413.

KEYWORD

nonn,more

AUTHOR

Gus Wiseman, Dec 05 2023

EXTENSIONS

a(5)-a(8) from Christian Sievers, Jul 26 2024

STATUS

approved

A368097

Number of non-isomorphic multiset partitions of weight n contradicting a strict version of the axiom of choice.

+10
39

0, 0, 1, 3, 12, 37, 133, 433, 1516, 5209, 18555

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,4

COMMENTS

A multiset partition is a finite multiset of finite nonempty multisets. The weight of a multiset partition is the sum of cardinalities of its elements. Weight is generally not the same as number of vertices.

LINKS

Table of n, a(n) for n=0..10.

Wikipedia, Axiom of choice.

EXAMPLE

Non-isomorphic representatives of the a(2) = 1 through a(4) = 12 multiset partitions:

{{1},{1}} {{1},{1,1}} {{1},{1,1,1}}

{{1},{1},{1}} {{1,1},{1,1}}

{{1},{2},{2}} {{1},{1},{1,1}}

{{1},{1},{2,2}}

{{1},{1},{2,3}}

{{1},{2},{1,2}}

{{1},{2},{2,2}}

{{2},{2},{1,2}}

{{1},{1},{1},{1}}

{{1},{1},{2},{2}}

{{1},{2},{2},{2}}

{{1},{2},{3},{3}}

MATHEMATICA

sps[{}]:={{}}; sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]& /@ sps[Complement[set, s]]] /@ Cases[Subsets[set], {i, ___}];

mpm[n_]:=Join@@Table[Union[Sort[Sort/@(#/.x_Integer:>s[[x]])]& /@ sps[Range[n]]], {s, Flatten[MapIndexed[Table[#2, {#1}]&, #]]& /@ IntegerPartitions[n]}];

brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{i, p[[i]]}, {i, Length[p]}])], {p, Permutations[Union@@m]}]]];

Table[Length[Union[brute/@Select[mpm[n], Select[Tuples[#], UnsameQ@@#&]=={}&]]], {n, 0, 6}]

CROSSREFS

The case of unlabeled graphs appears to be A140637, complement A134964.

These multiset partitions have ranks A355529.

The case of labeled graphs is A367867, complement A133686.

Set-systems not of this type are A367902, ranks A367906.

Set-systems of this type are A367903, ranks A367907.

For set-systems we have A368094, complement A368095.

The complement is A368098, ranks A368100, connected case A368412.

Minimal multiset partitions of this type are ranked by A368187.

The connected case is A368411.

Factorizations of this type are counted by A368413, complement A368414.

For set multipartitions we have A368421, complement A368422.

A000110 counts set partitions, non-isomorphic A000041.

A003465 counts covering set-systems, unlabeled A055621.

A007716 counts non-isomorphic multiset partitions, connected A007718.

A058891 counts set-systems, unlabeled A000612, connected A323818.

A283877 counts non-isomorphic set-systems, connected A300913.

Cf. A302545, A316983, A317533, A319616, A321405, A367905, A368409, A368410.

KEYWORD

nonn,more

AUTHOR

Gus Wiseman, Dec 25 2023

STATUS

approved

A140637

Number of unlabeled graphs of positive excess with n nodes.

+10
37

0, 0, 0, 2, 15, 110, 936, 12073, 273972, 12003332, 1018992968, 165091159269, 50502031331411, 29054155657134165, 31426485969804026075, 64001015704527557101231, 245935864153532932681481794, 1787577725145611700547871854870, 24637809253125004524383007473440146

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,4

COMMENTS

We can find in "The Birth of the Giant Component" p. 53, see the link, the following: "The excess of a graph or multigraph is the number of edges plus the number of acyclic components, minus the number of vertices."

If G has just one complex component with 4 nodes, the "non-complex part" of G can be,

a) One forest of order 4. There are 6 forests, so 2*6=12 graphs.

b) One triangle and one isolated vertex, or 2*1=2 graphs.

c) One unicyclic graph of order 4, so 2*2=4 graphs.

Also the number of unchoosable unlabeled graphs with up to n vertices, where a graph is choosable iff it is possible to choose a different vertex from each edge. The labeled version is A367867, covering A367868, connected A140638. - Gus Wiseman, Feb 13 2024

LINKS

Table of n, a(n) for n=1..19.

Svante Janson, Donald E. Knuth, Tomasz Luczak and Boris Pittel, The Birth of the Giant Component.

FORMULA

a(n) = A000088(n) - A134964(n).

EXAMPLE

Below we show that a(8) = 12073. Note that A140636(n) is the number of connected graphs of positive excess with n nodes.

Let G be a disconnected graph of positive excess with 8 nodes. In this case, G has one or two complex components. We have 3 graphs of order 8 with two complex components. One of those graphs is depicted in the figure below:

O---O...O---O

|\..|...|\./|

|.\.|...|.X.|

|..\|...|/.\|

O---O...O---O

If G has one complex component with 5 nodes, the non-complex part of G can be,

a) One forest of order 3. There are 3 forests, so A140636(5) * 3 = 39 graphs.

b) One triangle, so A140636(5) = 13 graphs.

If G has one complex component with 6 nodes, the non-complex part of G is a forest of order 2. There are 2 forests. We have A140636(6) * 2, or 186 graphs.

If G has one complex component with 7 nodes, the non-complex part of G is one isolated vertex. We have A140636(7), or 809 graphs.

Finally if G is connected, we have A140636(8), or 11005 graphs.

The total is 3 + 12 + 2 + 4 + 39 + 13 + 186 + 809 + 11005 = 12073.

MATHEMATICA

brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{(Union@@m)[[i]], p[[i]]}, {i, Length[p]}])], {p, Permutations[Range[Length[Union@@m]]]}]]];

Table[Length[Union[brute /@ Select[Subsets[Subsets[Range[n], {2}]], Select[Tuples[#], UnsameQ@@#&]=={}&]]], {n, 0, 5}] (* Gus Wiseman, Feb 14 2024 *)

CROSSREFS

Cf. A000088, A005195, A001429.

The labeled complement is A133686, covering A367869, connected A129271.

The complement is A134964, connected A005703.

The connected covering case is A140636.

The labeled version is A367867, covering A367868, connected A140638.

Set-systems not of this type are A367902, ranks A367906.

Set-systems of this type are A367903, ranks A367907.

For set-systems we have A368094, complement A368095.

For multiset partitions we have A368097, complement A368098.

Factorizations of this type are A368413, complement A368414.

Cf. A001349, A002494, A006125, A055621, A367769, A367770, A367901.

KEYWORD

nonn

AUTHOR

Washington Bomfim, May 21 2008

STATUS

approved

A368414

Number of factorizations of n into positive integers > 1 such that it is possible to choose a different prime factor of each factor.

+10
37

1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 3, 1, 2, 2, 1, 1, 3, 1, 3, 2, 2, 1, 4, 1, 2, 1, 3, 1, 5, 1, 1, 2, 2, 2, 5, 1, 2, 2, 4, 1, 5, 1, 3, 3, 2, 1, 5, 1, 3, 2, 3, 1, 4, 2, 4, 2, 2, 1, 9, 1, 2, 3, 1, 2, 5, 1, 3, 2, 5, 1, 6, 1, 2, 3, 3, 2, 5, 1, 5, 1, 2, 1, 9, 2, 2, 2

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,6

COMMENTS

For example, the factorization f = 2*3*6 has two ways to choose a prime factor of each factor, namely (2,3,2) and (2,3,3), but neither of these has all different elements, so f is not counted under a(36).

LINKS

Table of n, a(n) for n=1..87.

FORMULA

a(n) = A001055(n) - A368413(n).

EXAMPLE

The a(n) factorizations for selected n:

1 6 12 24 30 60 72 120

2*3 2*6 2*12 2*15 2*30 2*36 2*60

3*4 3*8 3*10 3*20 3*24 3*40

4*6 5*6 4*15 4*18 4*30

2*3*5 5*12 6*12 5*24

6*10 8*9 6*20

2*3*10 8*15

2*5*6 10*12

3*4*5 2*3*20

2*5*12

2*6*10

3*4*10

3*5*8

4*5*6

MATHEMATICA

facs[n_]:=If[n<=1, {{}}, Join @@ Table[Map[Prepend[#, d]&, Select[facs[n/d], Min@@#>=d&]], {d, Rest[Divisors[n]]}]];

Table[Length[Select[facs[n], Select[Tuples[First/@FactorInteger[#]&/@#], UnsameQ@@#&]!={}&]], {n, 100}]

CROSSREFS

For labeled graphs: A133686, complement A367867, A367868, A140638.

For unlabeled graphs: A134964, complement A140637.

For set-systems: A367902, ranks A367906, complement A367903, ranks A367907.

For non-isomorphic set-systems: A368095, complement A368094, A368409.

Complementary non-isomorphic multiset partitions: A368097, A355529, A368411.

For non-isomorphic multiset partitions: A368098, A368100.

The complement is counted by A368413.

For non-isomorphic set multipartitions: A368422, complement A368421.

For divisors instead of prime factors: A370813, complement A370814.

A001055 counts factorizations, strict A045778.

A007716 counts non-isomorphic multiset partitions, connected A007718.

A058891 counts set-systems, unlabeled A000612, connected A323818.

A283877 counts non-isomorphic set-systems, connected A300913.

Cf. A340596, A340653, A367769, A367901, A368187, A368412, A368413.

KEYWORD

nonn

AUTHOR

Gus Wiseman, Dec 29 2023

STATUS

approved

A370592

Number of integer partitions of n such that it is possible to choose a different prime factor of each part.

+10
36

1, 0, 1, 1, 1, 2, 1, 3, 3, 4, 4, 5, 6, 7, 9, 11, 12, 12, 16, 18, 22, 26, 29, 29, 37, 41, 49, 55, 61, 68, 72, 88, 98, 110, 120, 135, 146, 166, 190, 209, 227, 252, 277, 309, 346, 379, 413, 447, 500, 548, 606, 665, 727, 785, 857, 949, 1033, 1132, 1228, 1328, 1440

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,6

LINKS

Table of n, a(n) for n=0..60.

FORMULA

a(n) = A000041(n) - A370593(n).

EXAMPLE

The partition (10,6,4) has choice (5,3,2) so is counted under a(20).

The a(0) = 1 through a(10) = 4 partitions:

() . (2) (3) (4) (5) (6) (7) (8) (9) (10)

(3,2) (4,3) (5,3) (5,4) (6,4)

(5,2) (6,2) (6,3) (7,3)

(7,2) (5,3,2)

The a(0) = 1 through a(17) = 12 partitions (0 = {}, A..H = 10..17):

0 . 2 3 4 5 6 7 8 9 A B C D E F G H

32 43 53 54 64 65 66 76 86 87 97 98

52 62 63 73 74 75 85 95 96 A6 A7

72 532 83 A2 94 A4 A5 B5 B6

92 543 A3 B3 B4 C4 C5

732 B2 C2 C3 D3 D4

652 653 D2 E2 E3

743 654 754 F2

752 753 763 665

762 853 764

A32 952 A43

B32 7532

MATHEMATICA

Table[Length[Select[IntegerPartitions[n], Length[Select[Tuples[If[#==1, {}, First/@FactorInteger[#]]&/@#], UnsameQ@@#&]]>0&]], {n, 0, 30}]

CROSSREFS

The version for divisors instead of factors is A239312, ranks A368110.

The version for set-systems is A367902, ranks A367906, unlabeled A368095.

The complement for set-systems is A367903, ranks A367907, unlabeled A368094.

For unlabeled multiset partitions we have A368098, complement A368097.

These partitions have ranks A368100.

The version for factorizations is A368414, complement A368413.

The complement is counted by A370593, ranks A355529.

For a unique choice we have A370594, ranks A370647.

A006530 gives greatest prime factor, least A020639.

A027746 lists prime factors, A112798 indices, length A001222.

A355741 counts choices of a prime factor of each prime index.

Cf. A000040, A000720, A133686, A355739, A355740, A355745, A367771, A367905, A370585, A370586, A370636.

KEYWORD

nonn

AUTHOR

Gus Wiseman, Feb 29 2024

STATUS

approved

A368094

Number of non-isomorphic set-systems of weight n contradicting a strict version of the axiom of choice.

+10
35

0, 0, 0, 0, 1, 1, 5, 12, 36, 97, 291

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,7

COMMENTS

A set-system is a finite set of finite nonempty sets. The weight of a set-system is the sum of cardinalities of its elements. Weight is generally not the same as number of vertices.

LINKS

Table of n, a(n) for n=0..10.

Wikipedia, Axiom of choice.

EXAMPLE

Non-isomorphic representatives of the a(5) = 1 through a(7) = 12 set-systems:

{{1},{2},{3},{2,3}} {{1},{2},{1,3},{2,3}} {{1},{2},{1,2},{3,4,5}}

{{1},{2},{3},{1,2,3}} {{1},{3},{2,3},{1,2,3}}

{{2},{3},{1,3},{2,3}} {{1},{4},{1,4},{2,3,4}}

{{3},{4},{1,2},{3,4}} {{2},{3},{2,3},{1,2,3}}

{{1},{2},{3},{4},{3,4}} {{3},{1,2},{1,3},{2,3}}

{{1},{2},{3},{1,3},{2,3}}

{{1},{2},{3},{2,4},{3,4}}

{{1},{2},{3},{4},{2,3,4}}

{{1},{3},{4},{2,4},{3,4}}

{{1},{4},{5},{2,3},{4,5}}

{{2},{3},{4},{1,2},{3,4}}

{{1},{2},{3},{4},{5},{4,5}}

MATHEMATICA

sps[{}]:={{}}; sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]& /@ sps[Complement[set, s]]] /@ Cases[Subsets[set], {i, ___}];

mpm[n_]:=Join@@Table[Union[Sort[Sort/@(#/.x_Integer:>s[[x]])]& /@ sps[Range[n]]], {s, Flatten[MapIndexed[Table[#2, {#1}]&, #]]& /@ IntegerPartitions[n]}];

brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{i, p[[i]]}, {i, Length[p]}])], {p, Permutations[Union@@m]}]]];

Table[Length[Union[brute/@Select[mpm[n], UnsameQ@@#&&And@@UnsameQ@@@# && Select[Tuples[#], UnsameQ@@#&]=={}&]]], {n, 0, 8}]

CROSSREFS

The case of unlabeled graphs is A140637, complement A134964.

The case of labeled graphs is A367867, complement A133686.

The labeled version is A367903, ranks A367907.

The complement is counted by A368095, connected A368410.

Repeats allowed: A368097, ranks A355529, complement A368098, ranks A368100.

Minimal multiset partitions of this type are ranked by A368187.

The connected case is A368409.

Factorizations of this type are counted by A368413, complement A368414.

Allowing repeated edges gives A368421, complement A368422.

A000110 counts set partitions, non-isomorphic A000041.

A003465 counts covering set-systems, unlabeled A055621.

A007716 counts non-isomorphic multiset partitions, connected A007718.

A058891 counts set-systems, unlabeled A000612, connected A323818.

A283877 counts non-isomorphic set-systems, connected A300913.

Cf. A302545, A306005, A316983, A317533, A319616, A321155, A321405, A326031, A330223, A330227, A367905.

KEYWORD

nonn,more

AUTHOR

Gus Wiseman, Dec 23 2023

STATUS

approved

A370593

Number of integer partitions of n such that it is not possible to choose a different prime factor of each part.

+10
33

0, 1, 1, 2, 4, 5, 10, 12, 19, 26, 38, 51, 71, 94, 126, 165, 219, 285, 369, 472, 605, 766, 973, 1226, 1538, 1917, 2387, 2955, 3657, 4497, 5532, 6754, 8251, 10033, 12190, 14748, 17831, 21471, 25825, 30976, 37111, 44331, 52897, 62952, 74829, 88755, 105145, 124307

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,4

LINKS

Table of n, a(n) for n=0..47.

FORMULA

a(n) = A000041(n) - A370592(n).

EXAMPLE

The a(0) = 0 through a(7) = 12 partitions:

. (1) (11) (21) (22) (41) (33) (61)

(111) (31) (221) (42) (322)

(211) (311) (51) (331)

(1111) (2111) (222) (421)

(11111) (321) (511)

(411) (2221)

(2211) (3211)

(3111) (4111)

(21111) (22111)

(111111) (31111)

(211111)

(1111111)

MATHEMATICA

Table[Length[Select[IntegerPartitions[n], Length[Select[Tuples[If[#==1, {}, First/@FactorInteger[#]]&/@#], UnsameQ@@#&]]==0&]], {n, 0, 30}]

CROSSREFS

The complement for divisors instead of factors is A239312, ranks A368110.

These partitions have ranks A355529, complement A368100.

The complement for set-systems is A367902, ranks A367906, unlabeled A368095.

The version for set-systems is A367903, ranks A367907, unlabeled A368094.

For unlabeled multiset partitions we have A368097, complement A368098.

The version for factorizations is A368413, complement A368414.

The complement is counted by A370592.

For a unique choice we have A370594, ranks A370647.

A006530 gives greatest prime factor, least A020639.

A027746 lists prime factors, A112798 indices, length A001222.

A355741 counts choices of a prime factor of each prime index.

Cf. A000040, A000720, A133686, A355739, A355740, A367771, A367867, A367905, A370583, A370585, A370586, A370636.

KEYWORD

nonn

AUTHOR

Gus Wiseman, Feb 29 2024

STATUS

approved

A368095

Number of non-isomorphic set-systems of weight n satisfying a strict version of the axiom of choice.

+10
32

1, 1, 2, 4, 8, 17, 39, 86, 208, 508, 1304

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

COMMENTS

A set-system is a finite set of finite nonempty sets. The weight of a set-system is the sum of cardinalities of its elements.

LINKS

Table of n, a(n) for n=0..10.

EXAMPLE

Non-isomorphic representatives of the a(1) = 1 through a(5) = 17 set-systems:

{1} {12} {123} {1234} {12345}

{1}{2} {1}{23} {1}{234} {1}{2345}

{2}{12} {12}{34} {12}{345}

{1}{2}{3} {13}{23} {14}{234}

{3}{123} {23}{123}

{1}{2}{34} {4}{1234}

{1}{3}{23} {1}{2}{345}

{1}{2}{3}{4} {1}{23}{45}

{1}{24}{34}

{1}{4}{234}

{2}{13}{23}

{2}{3}{123}

{3}{13}{23}

{4}{12}{34}

{1}{2}{3}{45}

{1}{2}{4}{34}

{1}{2}{3}{4}{5}

MATHEMATICA

Table[Length[Select[bmp[n], UnsameQ@@#&&And@@UnsameQ@@@#&&Select[Tuples[#], UnsameQ@@#&]!={}&]], {n, 0, 10}]

CROSSREFS

For labeled graphs we have A133686, complement A367867.

For unlabeled graphs we have A134964, complement A140637.

For set-systems we have A367902, complement A367903.

These set-systems have BII-numbers A367906, complement A367907.

The complement is A368094, connected A368409.

Repeats allowed: A368098, ranks A368100, complement A368097, ranks A355529.

Minimal multiset partitions not of this type are counted by A368187.

The connected case is A368410.

Factorizations of this type are counted by A368414, complement A368413.

Allowing repeated edges gives A368422, complement A368421.

A000110 counts set-partitions, non-isomorphic A000041.

A003465 counts covering set-systems, unlabeled A055621.

A007716 counts non-isomorphic multiset partitions, connected A007718.

A058891 counts set-systems, unlabeled A000612, connected A323818.

A283877 counts non-isomorphic set-systems, connected A300913.

Cf. A001055, A007717, A302545, A306005, A316983, A319560, A321194, A321405, A330223, A367769, A367901.

KEYWORD

nonn,more

AUTHOR

Gus Wiseman, Dec 24 2023

STATUS

approved

A368098

Number of non-isomorphic multiset partitions of weight n satisfying a strict version of the axiom of choice.

+10
31

1, 1, 3, 7, 21, 54, 165, 477, 1501, 4736, 15652

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

COMMENTS

LINKS

Table of n, a(n) for n=0..10.

Wikipedia, Axiom of choice.

EXAMPLE

Non-isomorphic representatives of the a(1) = 1 through a(4) = 21 multiset partitions:

{{1},{2}} {{1,2,3}} {{1,2,2,2}}

{{1},{2,2}} {{1,2,3,3}}

{{1},{2,3}} {{1,2,3,4}}

{{2},{1,2}} {{1},{1,2,2}}

{{1},{2},{3}} {{1,1},{2,2}}

{{1,2},{1,2}}

{{1},{2,2,2}}

{{1,2},{2,2}}

{{1},{2,3,3}}

{{1,2},{3,3}}

{{1},{2,3,4}}

{{1,2},{3,4}}

{{1,3},{2,3}}

{{2},{1,2,2}}

{{3},{1,2,3}}

{{1},{2},{3,3}}

{{1},{2},{3,4}}

{{1},{3},{2,3}}

{{1},{2},{3},{4}}

MATHEMATICA

sps[{}]:={{}}; sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]& /@ sps[Complement[set, s]]] /@ Cases[Subsets[set], {i, ___}];

mpm[n_]:=Join@@Table[Union[Sort[Sort/@(#/.x_Integer:>s[[x]])]& /@ sps[Range[n]]], {s, Flatten[MapIndexed[Table[#2, {#1}]&, #]]& /@ IntegerPartitions[n]}];

brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{i, p[[i]]}, {i, Length[p]}])], {p, Permutations[Union@@m]}]]];

Table[Length[Union[brute/@Select[mpm[n], Select[Tuples[#], UnsameQ@@#&]!={}&]]], {n, 0, 6}]

CROSSREFS

The case of labeled graphs is A133686, complement A367867.

The case of unlabeled graphs is A134964, complement A140637 (apparently).

Set-systems of this type are A367902, ranks A367906, connected A368410.

The complimentary set-systems are A367903, ranks A367907, connected A368409.

For set-systems we have A368095, complement A368094.

The complement is A368097, ranks A355529.

These multiset partitions have ranks A368100.

The connected case is A368412, complement A368411.

Factorizations of this type are counted by A368414, complement A368413.

For set multipartitions we have A368422, complement A368421.

A000110 counts set partitions, non-isomorphic A000041.

A003465 counts covering set-systems, unlabeled A055621.

A007716 counts non-isomorphic multiset partitions, connected A007718.

A058891 counts set-systems, unlabeled A000612, connected A323818.

A283877 counts non-isomorphic set-systems, connected A300913.

Cf. A302545, A306005, A316983, A317533, A319616, A330223, A330227, A368187.

KEYWORD

nonn,more

AUTHOR

Gus Wiseman, Dec 25 2023

STATUS

approved

A370813

Number of non-condensed integer factorizations of n into unordered factors > 1.

+10
31

0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 2, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0, 0, 0, 0, 0, 0

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,32

COMMENTS

A multiset is condensed iff it is possible to choose a different divisor of each element.

LINKS

Table of n, a(n) for n=1..87.

EXAMPLE

The a(96) = 4 factorizations: (2*2*2*2*2*3), (2*2*2*2*6), (2*2*2*3*4), (2*2*2*12).

MATHEMATICA

facs[n_]:=If[n<=1, {{}}, Join @@ Table[Map[Prepend[#, d]&, Select[facs[n/d], Min @@ #>=d&]], {d, Rest[Divisors[n]]}]];

Table[Length[Select[facs[n], Length[Select[Tuples[Divisors /@ #], UnsameQ@@#&]]==0&]], {n, 100}]

CROSSREFS

Partitions not of this type are counted by A239312, ranks A368110.

Factors instead of divisors: A368413, complement A368414, unique A370645.

Partitions of this type are counted by A370320, ranks A355740.

Subsets of this type: A370583 and A370637, complement A370582 and A370636.

The complement is counted by A370814, partitions A370592, ranks A368100.

For a unique choice we have A370815, partitions A370595, ranks A370810.

A000005 counts divisors.

A001055 counts factorizations, strict A045778.

A355731 counts choices of a divisor of each prime index, firsts A355732.

Cf. A340596, A340653, A355529, A355739, A355741, A370804, A370807.

KEYWORD

nonn

AUTHOR

Gus Wiseman, Mar 04 2024

STATUS

approved

page 1 2 3 4 5

Search completed in 0.027 seconds