A005703 -id:A005703 - cp's OEIS frontend

A368834 Number of unlabeled simple graphs covering n vertices such that it is possible to choose a different vertex from each edge (choosable).

1, 0, 1, 2, 5, 10, 27, 62, 165, 423, 1140, 3060, 8427, 23218, 64782, 181370, 511004, 1444285, 4097996, 11656644, 33243265, 94992847, 271953126, 779790166, 2239187466, 6438039076, 18532004323, 53400606823, 154024168401, 444646510812, 1284682242777

Offset: 0

Gus Wiseman, Jan 23 2024

nonn

			Representatives of the a(2) = 1 through a(5) = 10 simple graphs:
  {12}  {12}{13}      {12}{34}          {12}{13}{45}
        {12}{13}{23}  {12}{13}{14}      {12}{13}{14}{15}
                      {12}{13}{24}      {12}{13}{14}{25}
                      {12}{13}{14}{23}  {12}{13}{23}{45}
                      {12}{13}{24}{34}  {12}{13}{24}{35}
                                        {12}{13}{14}{15}{23}
                                        {12}{13}{14}{23}{25}
                                        {12}{13}{14}{23}{45}
                                        {12}{13}{14}{25}{35}
                                        {12}{13}{24}{35}{45}

Andrew Howroyd, Table of n, a(n) for n = 0..500

Without the choice condition we have A002494, labeled A006129.
The connected case is A005703, labeled A129271.
This is the covering case of A134964, complement A140637.
The labeled version is A367869, complement A367868.
The version with loops is A369200, complement A369147.
The complement is counted by A369202.
A007716 counts unlabeled multiset partitions, connected A007718.
A054548 counts graphs covering n vertices with k edges, with loops A369199.
A283877 counts unlabeled set-systems, connected A300913.
Cf. A000088, A006649, A001434, A055621, A116508, A133686, A137916, A137917, A368984, A369146.

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}]],Union@@#==Range[n] && Length[Select[Tuples[#],UnsameQ@@#&]]!=0&]]],{n,0,5}]

Euler transform of A005703 with A005703(1) = 0.
First differences of A134964.
a(n) = A002494(n) - A369202(n).

A387113 Numbers whose prime indices do not have (strictly) choosable initial intervals.

Original entry on oeis.org

4, 8, 12, 16, 18, 20, 24, 27, 28, 32, 36, 40, 44, 48, 52, 54, 56, 60, 64, 68, 72, 76, 80, 81, 84, 88, 90, 92, 96, 100, 104, 108, 112, 116, 120, 124, 126, 128, 132, 135, 136, 140, 144, 148, 150, 152, 156, 160, 162, 164, 168, 172, 176, 180, 184, 188, 189, 192

Offset: 1

Gus Wiseman, Aug 24 2025

The initial interval of a nonnegative integer x is the set {1,...,x}.
A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.
We say that a set or sequence of nonempty sets is choosable iff it is possible to choose a different element from each set. For example, ({1,2},{1},{1,3}) is choosable because we have the choice (2,1,3), but ({1,2,3},{1},{1,3},{2}) is not.
This sequence lists all numbers k such that if the prime indices of k are (x1,x2,...,xz), then the sequence of sets (initial intervals) ({1,...,x1},{1,...,x2},...,{1,...,xz}) is not choosable.

			The prime indices of 18 are {1,2,2}, with initial intervals ({1},{1,2},{1,2}), which have choices (1,1,1), (1,1,2), (1,2,1), (1,2,2), and since none of these are strict, 18 is in the sequence.
The prime indices of 85 are {3,7}, with initial intervals {{1,2,3},{1,2,3,4,5,6,7}}, which are choosable, so 85 is in not the sequence.
The prime indices of 90 are {1,2,2,3}, with initial intervals {{1},{1,2},{1,2},{1,2,3}}, which are not choosable, so 90 is in the sequence.
The terms together with their prime indices begin:
    4: {1,1}
    8: {1,1,1}
   12: {1,1,2}
   16: {1,1,1,1}
   18: {1,2,2}
   20: {1,1,3}
   24: {1,1,1,2}
   27: {2,2,2}
   28: {1,1,4}
   32: {1,1,1,1,1}
   36: {1,1,2,2}
   40: {1,1,1,3}
   44: {1,1,5}
   48: {1,1,1,1,2}
   52: {1,1,6}
   54: {1,2,2,2}
   56: {1,1,1,4}
   60: {1,1,2,3}
   64: {1,1,1,1,1,1}

For partitions instead of initial intervals we have A276079, complement A276078.
For prime factors instead of initial intervals we have A355529, complement A368100.
For divisors instead of initial intervals we have A355740, complement A368110.
These are the positions of 0 in A387111, complement A387134.
The complement is A387112.
Partitions of this type are counted by A387118, complement A238873.
For strict partitions instead of initial intervals we have A387137, complement A387176.
A061395 gives greatest prime index, least A055396.
A112798 lists prime indices, row sums A056239 or A066328, lengths A001222.
A120383 lists numbers divisible by all of their prime indices.
A367902 counts choosable set-systems, complement A367903.
A370582 counts sets with choosable prime factors, complement A370583.
A370585 counts maximal subsets with choosable prime factors.
Cf. A003963, A005703, A052335, A239312, A335433, A335448, A355739, A355747, A370592, A383706, A387110.

prix[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100],Select[Tuples[Range/@prix[#]],UnsameQ@@#&]=={}&]

A387178 Number of integer partitions of n whose parts have choosable sets of strict integer partitions.

Original entry on oeis.org

1, 1, 1, 2, 2, 3, 5, 6, 8, 10, 13, 17, 21, 27, 34, 42, 53, 65, 80, 98, 119, 146, 177, 213, 258, 309, 370, 443, 528, 628, 745, 882, 1043, 1229, 1447, 1700, 1993, 2333, 2727, 3182, 3707, 4311, 5008, 5808, 6727, 7782, 8990, 10371, 11952, 13756, 15815, 18161

Offset: 0

Gus Wiseman, Sep 02 2025

First differs from A052337 in having 745 instead of 746.
We say that a sequence of nonempty sets is choosable iff it is possible to choose a different element from each set. For example, ({1,2},{1},{1,3}) is choosable because we have the choice (2,1,3), but ({1},{2},{1,3},{2,3}) is not.
a(n) is the number of integer partitions of n such that it is possible to choose a sequence of distinct strict integer partitions of each part.
Also the number of integer partitions of n with no part k whose multiplicity exceeds A000009(k).

			The partition y = (3,3,2) has sets of strict integer partitions ({(2,1),(3)},{(2,1),(3)},{(2)}), and we have the choice ((2,1),(3),(2)) or ((3),(2,1),(2)), so y is counted under a(8).
The a(1) = 1 through a(9) = 10 partitions:
  (1)  (2)  (3)    (4)    (5)    (6)      (7)      (8)      (9)
            (2,1)  (3,1)  (3,2)  (3,3)    (4,3)    (4,4)    (5,4)
                          (4,1)  (4,2)    (5,2)    (5,3)    (6,3)
                                 (5,1)    (6,1)    (6,2)    (7,2)
                                 (3,2,1)  (3,3,1)  (7,1)    (8,1)
                                          (4,2,1)  (3,3,2)  (4,3,2)
                                                   (4,3,1)  (4,4,1)
                                                   (5,2,1)  (5,3,1)
                                                            (6,2,1)
                                                            (3,3,2,1)

For initial intervals instead of strict partitions we have A238873, ranks A387112.
For divisors instead of strict partitions we have A239312, ranks A368110.
The complement for divisors is A370320, ranks A355740.
For prime factors instead of strict partitions we have A370592, ranks A368100.
The complement for prime factors is A370593, ranks A355529.
The complement for initial intervals is A387118, ranks A387113.
The complement for all partitions is A387134, ranks A387577.
The complement is counted by A387137, ranks A387176.
These partitions are ranked by A387177.
For all partitions instead of just strict partitions we have A387328, ranks A387576.
The complement for constant partitions is A387329, ranks A387180.
For constant partitions instead of strict partitions we have A387330, ranks A387181.
A000041 counts integer partitions, strict A000009.
A358914 counts twice-partitions into distinct strict partitions.
A367902 counts choosable set-systems, complement A367903.
Cf. A005703, A052335, A261049, A270995, A276078, A335448, A367867, A367901, A387115.

strptns[n_]:=Select[IntegerPartitions[n],UnsameQ@@#&];
Table[Length[Select[IntegerPartitions[n],Select[Tuples[strptns/@#],UnsameQ@@#&]!={}&]],{n,0,15}]

cp's OEIS Frontend

A368834 Number of unlabeled simple graphs covering n vertices such that it is possible to choose a different vertex from each edge (choosable).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A387113 Numbers whose prime indices do not have (strictly) choosable initial intervals.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A387178 Number of integer partitions of n whose parts have choosable sets of strict integer partitions.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica