A003465 -id:A003465 - cp's OEIS frontend

A016031 De Bruijn's sequence: 2^(2^(n-1) - n): number of ways of arranging 2^n bits in circle so all 2^n consecutive strings of length n are distinct.

1, 1, 2, 16, 2048, 67108864, 144115188075855872, 1329227995784915872903807060280344576, 226156424291633194186662080095093570025917938800079226639565593765455331328

Offset: 1

N. J. A. Sloane, Robert G. Wilson v

Sequence corresponds also to the largest number that may be determined by asking no more than 2^(n-1) - 1 questions("Yes"-or-"No" answerable) with lying allowed at most once. - Lekraj Beedassy, Jul 15 2002
Number of Ouroborean rings for binary n-tuplets. - Lekraj Beedassy, May 06 2004
Also the number of games of Nim that are wins for the second player when the starting position is either the empty heap or heaps of sizes 1 <= t_1 < t_2 < ... < t_k < 2^(n-1) (if n is 1, the only starting position is the empty heap). E.g.: a(4) = 16: the winning positions for the second player when all the heap sizes are different and less than 2^3: (4,5,6,7), (3,5,6), (3,4,7), (2,5,7), (2,4,6), (2,3,6,7), (2,3,4,5), (1,6,7), (1,4,5), (1,3,5,7), (1,3,4,6), (1,2,5,6), (1,2,4,7), (1,2,3), (1,2,3,4,5,6,7) and the empty heap. - Kennan Shelton (kennan.shelton(AT)gmail.com), Apr 14 2006
a(n + 1) = 2^(2^n-n-1) = 2^A000295(n) is also the number of set-systems on n vertices with no singletons. The case with singletons is A058891. The unlabeled case is A317794. The spanning/covering case is A323816. The antichain case is A006126. The connected case is A323817. The uniform case is A306021(n) - 1. The graphical case is A006125. The chain case is A005840. - Gus Wiseman, Feb 01 2019
Named after the Dutch mathematician Nicolaas Govert de Bruijn (1918-2012). - Amiram Eldar, Jun 20 2021

Jonathan L. Gross and Jay Yellen, eds., Handbook of Graph Theory, CRC Press, 2004, p. 255.
Frank Harary and Edgar M. Palmer, Graphical Enumeration, 1973, p. 31.
D. J. Newman, "A variation of the Game of Twenty Question", in: Murray S. Klamkin (ed.), Problems in Applied Mathematics, Philadelphia, PA: SIAM, 1990, Problem 66-20, pp. 121-122.
Richard P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Cor. 5.6.15.
Ian Stewart, Game, Set and Math, pp. 50, Penguin 1991.

Vincenzo Librandi, Table of n, a(n) for n = 1..12
CombOS - Combinatorial Object Server, Generate de Bruijn sequences.
Robert Erra, Nik Lygeros and Nigel Stewart, On Minimal Strings Containing the Elements of S(n) by Decimation, Proceedings AA (DM-CCG), 2001, Section 5.4.
Loïc Foissy, Hopf algebraic structures on hypergraphs and multi-complexes, arXiv:2304.00810 [math.CO], 2023.
Francisco J. Muñoz and Juan Carlos Nuño, Rule-based Generation of de Bruijn Sequences: Memory and Learning, arXiv:2507.09764 [cs.FL], 2025. See p. 9.
Wikipedia, De Bruijn sequence.

Cf. A000295, A003465, A006125, A058891 (set systems), A317794 (unlabeled case), A323816 (spanning case), A323817 (connected case), A331691 (alternating signs).

[2^(2^(n-1)-n): n in [1..10]]; // Vincenzo Librandi, Aug 09 2017

Table[2^(2^(n - 1) - n), {n, 20}] (* Vincenzo Librandi, Aug 09 2017 *)

a(n) = 2^A000295(n-1). - Lekraj Beedassy, Jan 17 2007

Shifting once to the left gives the binomial transform of A323816. - Gus Wiseman, Feb 01 2019

A116508 a(n) = C( C(n,2), n).

Original entry on oeis.org

1, 0, 0, 1, 15, 252, 5005, 116280, 3108105, 94143280, 3190187286, 119653565850, 4922879481520, 220495674290430, 10682005290753420, 556608279578340080, 31044058215401404845, 1845382436487682488000, 116475817125419611477660, 7779819801401934344268210

Offset: 0

Christopher Hanusa (chanusa(AT)math.binghamton.edu), Mar 21 2006

a(n) is the number of simple labeled graphs with n nodes and n edges. - Geoffrey Critzer, Nov 02 2014

These graphs are not necessarily covering, but the covering case is A367863, unlabeled A006649, and the unlabeled version is A001434. - Gus Wiseman, Dec 22 2023

			a(5) = C(C(5,2),5) = C(10,5) = 252.

Alois P. Heinz, Table of n, a(n) for n = 0..370

Main diagonal of A084546.
The unlabeled version is A001434, covering case A006649.
The connected case is A057500, unlabeled A001429.
For set-systems we have A136556, covering case A054780.
The covering case is A367863.
A006125 counts graphs, A000088 unlabeled.
A006129 counts covering graphs, A002494 unlabeled.
A133686 counts graphs satisfying a strict AOC, connected A129271.
A367867 counts graphs contradicting a strict AOC, connected A140638.
Cf. A001187, A003465, A143543, A305000, A367916, A367917.

[0] cat [(Binomial(Binomial(n+2, n), n+2)): n in [0..20]]; // Vincenzo Librandi, Nov 03 2014

a:= n-> binomial(binomial(n, 2), n):
seq(a(n), n=0..20);

nn = 18; f[x_, y_] :=
Sum[(1 + y)^Binomial[n, 2] x^n/n!, {n, 1, nn}]; Table[
n! Coefficient[Series[f[x, y], {x, 0, nn}], x^n y^n], {n, 1, nn}] (* Geoffrey Critzer, Nov 02 2014 *)
Table[Length[Subsets[Subsets[Range[n],{2}],{n}]],{n,0,5}] (* Gus Wiseman, Dec 22 2023 *)
Table[SeriesCoefficient[(1 + x)^(n*(n-1)/2), {x, 0, n}], {n, 0, 20}] (* Vaclav Kotesovec, Aug 06 2025 *)

from math import comb
def A116508(n): return comb(n*(n-1)>>1,n) # Chai Wah Wu, Jul 02 2024

[(binomial(binomial(n+2,n),n+2)) for n in range(-1, 17)] # Zerinvary Lajos, Nov 30 2009

a(n) ~ exp(n - 2) * n^(n - 1/2) / (sqrt(Pi) * 2^(n + 1/2)). - Vaclav Kotesovec, May 19 2020

a(n) = [x^n] (1+x)^(n*(n-1)/2). - Vaclav Kotesovec, Aug 06 2025

a(0)=1 prepended by Alois P. Heinz, Feb 02 2024

A367863 Number of n-vertex labeled simple graphs with n edges and no isolated vertices.

Original entry on oeis.org

1, 0, 0, 1, 15, 222, 3760, 73755, 1657845, 42143500, 1197163134, 37613828070, 1295741321875, 48577055308320, 1969293264235635, 85852853154670693, 4005625283891276535, 199166987259400191480, 10513996906985414443720, 587316057411626070658200, 34612299496604684775762261

Offset: 0

Gus Wiseman, Dec 07 2023

nonn

			Non-isomorphic representatives of the a(4) = 15 graphs:
  {{1,2},{1,3},{1,4},{2,3}}
  {{1,2},{1,3},{2,4},{3,4}}

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

The connected case is A057500, unlabeled A001429.
The unlabeled version is A006649.
The non-covering version is A116508.
For set-systems we have A367916, ranks A367917.
A001187 counts connected graphs, A001349 unlabeled.
A006125 counts graphs, A000088 unlabeled.
A006129 counts covering graphs, A002494 unlabeled.
A058891 counts set-systems, unlabeled A000612, without singletons A016031.
A059201 counts covering T_0 set-systems, unlabeled A319637, ranks A326947.
A133686 = graphs satisfy strict AoC, connected A129271, covering A367869.
A143543 counts simple labeled graphs by number of connected components.
A323818 counts connected set-systems, unlabeled A323819, ranks A326749.
A367867 = graphs contradict strict AoC, connected A140638, covering A367868.
Cf. A003465, A006126, A305000, A316983, A319559, A323817, A326754, A367769, A367901, A367902, A367903.

Table[Length[Select[Subsets[Subsets[Range[n],{2}]], Union@@#==Range[n]&&Length[#]==n&]],{n,0,5}]

a(n) = sum(k=0, n, (-1)^(n-k) * binomial(n,k) * binomial(binomial(k,2), n)) \\ Andrew Howroyd, Dec 29 2023

Binomial transform is A367862.

a(n) = Sum_{k=0..n} (-1)^(n-k) * binomial(n,k) * binomial(binomial(k,2), n). - Andrew Howroyd, Dec 29 2023

Terms a(8) and beyond from Andrew Howroyd, Dec 29 2023

A367906 Numbers k such that it is possible to choose a different binary index of each binary index of k.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18, 19, 20, 21, 22, 24, 26, 28, 32, 33, 34, 35, 36, 37, 38, 40, 41, 44, 48, 49, 50, 52, 56, 64, 65, 66, 67, 68, 69, 70, 72, 73, 74, 76, 80, 81, 82, 84, 88, 96, 97, 98, 100, 104, 112, 128, 129, 130, 131, 132

Offset: 1

Gus Wiseman, Dec 11 2023

Also BII-numbers of set-systems (sets of nonempty sets) satisfying a strict version of the axiom of choice.
A binary index of k (row k of A048793) is any position of a 1 in its reversed binary expansion. A set-system is a finite set of finite nonempty sets. We define the set-system with BII-number k to be obtained by taking the binary indices of each binary index of k. Every finite set of finite nonempty sets has a different BII-number. For example, 18 has reversed binary digits (0,1,0,0,1), and since the binary indices of 2 and 5 are {2} and {1,3} respectively, the BII-number of {{2},{1,3}} is 18.
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.

			The set-system {{2,3},{1,2,3},{1,4}} with BII-number 352 has choices such as (2,1,4) that satisfy the axiom, so 352 is in the sequence.
The terms together with the corresponding set-systems begin:
   1: {{1}}
   2: {{2}}
   3: {{1},{2}}
   4: {{1,2}}
   5: {{1},{1,2}}
   6: {{2},{1,2}}
   8: {{3}}
   9: {{1},{3}}
  10: {{2},{3}}
  11: {{1},{2},{3}}
  12: {{1,2},{3}}
  13: {{1},{1,2},{3}}
  14: {{2},{1,2},{3}}
  16: {{1,3}}
  17: {{1},{1,3}}

John Tyler Rascoe, Table of n, a(n) for n = 1..10000
Wikipedia, Axiom of choice.

These set-systems are counted by A367902, non-isomorphic A368095.
Positions of positive terms in A367905, firsts A367910, sorted A367911.
The complement is A367907.
If there is one unique choice we get A367908, counted by A367904.
If there are multiple choices we get A367909, counted by A367772.
Unlabeled multiset partitions of this type are A368098, complement A368097.
A version for MM-numbers of multisets is A368100, complement A355529.
A048793 lists binary indices, A000120 length, A272020 reverse, A029931 sum.
A058891 counts set-systems, A003465 covering, A323818 connected.
A070939 gives length of binary expansion.
A096111 gives product of binary indices.
A326031 gives weight of the set-system with BII-number n.
Cf. A000612, A055621, A059519, A072639, A083323, A309326, A326702, A326753, A367770, A367912.
BII-numbers: A309314 (hyperforests), A326701 (set partitions), A326703 (chains), A326704 (antichains), A326749 (connected), A326750 (clutters), A326751 (blobs), A326752 (hypertrees), A326754 (covers), A326783 (uniform), A326784 (regular), A326788 (simple), A330217 (achiral).

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
Select[Range[100], Select[Tuples[bpe/@bpe[#]], UnsameQ@@#&]!={}&]

from itertools import count, islice, product
def bin_i(n): #binary indices
    return([(i+1) for i, x in enumerate(bin(n)[2:][::-1]) if x =='1'])
def a_gen(): #generator of terms
    for n in count(1):
        for j in list(product(*[bin_i(k) for k in bin_i(n)])):
            if len(set(j)) == len(j):
                yield(n); break
A367906_list = list(islice(a_gen(),100)) # John Tyler Rascoe, Dec 23 2023

A000371 a(n) = Sum_{k=0..n} (-1)^(n-k)binomial(n,k)2^(2^k).

Original entry on oeis.org

2, 2, 10, 218, 64594, 4294642034, 18446744047940725978, 340282366920938463334247399005993378250, 115792089237316195423570985008687907850547725730273056332267095982282337798562

Offset: 0

N. J. A. Sloane

Inverse binomial transform of A001146.
Number of nondegenerate Boolean functions of n variables.
Twice the number of covers of an n-set S (A003465). That is, the number of subsets of the power set of S whose union is S. [corrected by Manfred Boergens, May 02 2024]
From David P. Moulton, Nov 11 2010: (Start)
To see why the formula in the definition gives the number of covers of an n-set we use inclusion-exclusion.
The set S has n elements and T, the power set of S, has 2^n elements.
Let U be the power set of T; we want to know how many elements of U have union S.
For any element i of S, let U_i be the subset of U whose unions do not contain i, so we want to compute the size of the complement of the union of the U_i s.
Write U_I for the union of U_i for i in I. Then U_I consists of all subsets of T whose union is disjoint from I, so it consists of all subsets of the power set of S - I. The power set of S - I has 2^(n - #I) elements, so U_I has size 2^2^(n - #I).
Then the basic inclusion-exclusion formula says that our answer is
#(U - union_{i in S} U_i) = Sum_{I subseteq S} (-1)^#I #U_I = Sum_{j=0..n} (-1)^j Sum_{#I = j} #U_I = Sum_{j=0..n} (-1)^j binomial(n,j)*2^2^(n-j), as required.
(End)
Here is Comtet's proof: Let P'(S) be the power set of nonempty subsets of S. Then |P'(P'(S))| = 2^(2^n-1)-1 = Sum_k binomial(n,k)*a(k). Apply the inverse binomial transform to get a(n) = Sum_k (-1)^k*binomial(n,k)*2^(2^(n-k)-1). - N. J. A. Sloane, May 19 2011
For disjoint subsets of the power set see A186021. For disjoint nonempty subsets of the power set see A000110. - Manfred Boergens, May 02 2024 and Apr 09 2025

			Let n = 2, S = {a,b}, and P = {0,a,b,ab}. There are ten subsets of P whose union is S: {ab}, {a,b}, {a,ab}, {b,ab}, {a,b,ab}, and the empty set together with the same five. - _Marc LeBrun_, Nov 10 2010

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 165.
M. A. Harrison, Introduction to Switching and Automata Theory. McGraw Hill, NY, 1965, p. 170.
S. Muroga, Threshold Logic and Its Applications. Wiley, NY, 1971, p. 38 and 214.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
C. G. Wagner, Covers of finite sets, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 515-520.

R. Baumann and H. Strass, On the number of bipolar Boolean functions, 2014, preprint.
R. Baumann and H. Strass, On the number of bipolar Boolean functions, Journal of Logic and Computation, 27(8) (2017), 2431-2449.
Thomas M. A. Fink, Regulatory motifs: structural and functional building blocks of genetic computation, arXiv:2208.14996 [q-bio.MN], 2022.
Goto, Eiichi, and Hidetosi Takahasi, Some Theorems Useful in Threshold Logic for Enumerating Boolean Functions, in Proceedings International Federation for Information Processing (IFIP) Congress, 1962, pp. 747-752. [Annotated scans of certain pages]
R. K. Guy, Letter to N. J. A. Sloane, Mar 1974
T. Hearne and C. G. Wagner, Minimal covers of finite sets, Discr. Math. 5 (1973), 247-251.
M. Klazar, Extremal problems for ordered hypergraphs, arXiv:math/0305048 [math.CO], 2003.
A. J. Macula, Covers of a finite set, Math. Mag., 67 (1994), 141-144.
S. Muroga, Threshold Logic and Its Applications, Wiley, NY, 1971 [Annotated scans of a few pages]
N. J. A. Sloane, Transforms
Eric Weisstein's World of Mathematics, Cover
Index entries for sequences related to Boolean functions

Equals twice A003465.
Row sums of A163353.
Diagonal of A381683.
Cf. A001146, A002110, A076078, A055154.
Cf. A000110, A186021.

[&+[(-1)^(n-k)*Binomial(n, k)*2^(2^k): k in [0..n]]: n in [0..10]]; // Vincenzo Librandi, Dec 28 2015

f:=n->add((-1)^(n-k)*binomial(n,k)*2^(2^k),k=0..n);

Table[Sum[(-1)^(n-k) Binomial[n,k]2^(2^k),{k,0,n}],{n,0,10}] (* Harvey P. Dale, Oct 17 2011 *)

a(n)=sum(k=0,n,(-1)^(n-k)*binomial(n,k)<<(2^k)) \\ Charles R Greathouse IV, Jan 02 2012

a(n) = sum(k=0, n, (-1)^k*n!/k!/(n-k)!*2^(2^(n-k))); \\ Altug Alkan, Dec 29 2015

The coefficient of x^k in the polynomial p_n(x) = Sum_{j=0..n} (-1)^j binomial(n,j) * (x+1)^2^(n-j) gives the number of covers of a set of size n where the covers have k elements.  Also, there is a recurrence: f_n(k) = k, if n = 0, and f_n(k) = f_{n-1}(k^2) - f_{n-1}(k), if n > 0, that gives a(n) = f_n(2) and p_n(x) = f_n(x+1). - David W. Wilson, Nov 11 2010
E.g.f.: Sum(exp((2^n-1)*x)*log(2)^n/n!, n=0..infinity). - Vladeta Jovovic, May 30 2004
For n > 0, a(n) = A076078(A002110(n)). - Matthew Vandermast, Nov 14 2010
a(n) ~ 2^(2^n). - Charles R Greathouse IV, Jan 02 2012
a(n) = 2*A003465(n). - Maurizio De Leo, Feb 27 2015

Since this sequence arises in several different contexts, I replaced the old definition with an explicit formula. - N. J. A. Sloane, Nov 23 2010

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

Original entry on oeis.org

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

Offset: 0

Gus Wiseman, Dec 25 2023

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.

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.

			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}}

Wikipedia, Axiom of choice.

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.

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}]

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

Original entry on oeis.org

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

Offset: 0

Gus Wiseman, Dec 23 2023

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.

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.

			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}}

Wikipedia, Axiom of choice.

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.

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}]

A368109 Number of ways to choose a binary index of each binary index of n.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 2, 2, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 4, 4, 4, 4, 2, 2, 2, 2, 4, 4, 4, 4, 2, 2, 2, 2, 4, 4, 4, 4, 2, 2, 2, 2, 4, 4, 4, 4, 4, 4, 4, 4, 8, 8, 8, 8, 4, 4, 4, 4, 8, 8, 8, 8, 3, 3, 3, 3, 6, 6, 6, 6, 3, 3, 3, 3, 6, 6, 6, 6, 6, 6, 6, 6, 12, 12, 12

Offset: 0

Gus Wiseman, Dec 12 2023

nonn

First differs from A367912 at a(52) = 8, A367912(52) = 7.
A binary index of n (row n of A048793) is any position of a 1 in its reversed binary expansion. For example, 18 has reversed binary expansion (0,1,0,0,1) and binary indices {2,5}.
Run-lengths are all 4 or 8.

			The binary indices of binary indices of 20 are {{1,2},{1,3}}, with choices (1,1), (1,3), (2,1), (2,3), so a(20) = 4.
The binary indices of binary indices of 52 are {{1,2},{1,3},{2,3}}, with choices (1,1,1), (1,1,3), (1,3,2), (1,3,3), (2,1,2), (2,1,3), (2,3,2), (2,3,3), so a(52) = 8.

All entries appear to belong to A003586.
Positions of ones are A253317.
The version for prime indices is A355741, for multisets A355744.
Choosing a multiset (not sequence) gives A367912, firsts A367913.
Positions of first appearances are A368111, sorted A368112.
A048793 lists binary indices, length A000120, sum A029931.
A058891 counts set-systems, covering A003465, connected A323818.
A070939 gives length of binary expansion.
A096111 gives product of binary indices.
Cf. A072639, A309326, A326031, A326702, A326753, A355731, A355739, A367771, A367905, A367906, A367915.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n, 2]],1];
Table[Length[Tuples[bpe/@bpe[n]]], {n,0,100}]

a(n) = Product_{k in A048793(n)} A000120(k).

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

Original entry on oeis.org

1, 2, 9, 195, 63765, 4294780073, 18446744073639513336, 340282366920938463463374607341656713953, 115792089237316195423570985008687907853269984665640564039457583610129753447747

Offset: 0

Gus Wiseman, Dec 05 2023

nonn

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.

			The a(2) = 9 sets of sets:
  {{}}
  {{},{1}}
  {{},{2}}
  {{},{1,2}}
  {{},{1},{2}}
  {{},{1},{1,2}}
  {{},{2},{1,2}}
  {{1},{2},{1,2}}
  {{},{1},{2},{1,2}}

Wikipedia, Axiom of choice.

The version for simple graphs is A367867, covering A367868.
The complement is counted by A367902, no singletons A367770, ranks A367906.
The version without empty edges is A367903, ranks A367907.
For a unique choice (instead of none) we have A367904, ranks A367908.
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, unlabeled A323819.
A326031 gives weight of the set-system with BII-number n.
Cf. A007716, A083323, A092918, A102896, A283877, A306445, A355739, A355740, A367769, A367862, A367905.

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

a(n) = 2^2^n - A367902(n). - Christian Sievers, Aug 01 2024

a(5)-a(8) from Christian Sievers, Aug 01 2024

A367862 Number of n-vertex labeled simple graphs with the same number of edges as covered vertices.

Original entry on oeis.org

1, 1, 1, 2, 20, 308, 5338, 105298, 2366704, 60065072, 1702900574, 53400243419, 1836274300504, 68730359299960, 2782263907231153, 121137565273808792, 5645321914669112342, 280401845830658755142, 14788386825536445299398, 825378055206721558026931, 48604149005046792753887416

Offset: 0

Gus Wiseman, Dec 07 2023

nonn

Unlike the connected case (A057500), these graphs may have more than one cycle; for example, the graph {{1,2},{1,3},{1,4},{2,3},{2,4},{5,6}} has multiple cycles.

			Non-isomorphic representatives of the a(4) = 20 graphs:
  {}
  {{1,2},{1,3},{2,3}}
  {{1,2},{1,3},{1,4},{2,3}}
  {{1,2},{1,3},{2,4},{3,4}}

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

The connected case is A057500, unlabeled A001429.
Counting all vertices (not just covered) gives A116508.
The covering case is A367863, unlabeled A006649.
For set-systems we have A367916, ranks A367917.
A001187 counts connected graphs, A001349 unlabeled.
A003465 counts covering set-systems, unlabeled A055621, ranks A326754.
A006125 counts graphs, A000088 unlabeled.
A006129 counts covering graphs, A002494 unlabeled.
A058891 counts set-systems, unlabeled A000612, without singletons A016031.
A059201 counts covering T_0 set-systems, unlabeled A319637, ranks A326947.
A133686 = graphs satisfy strict AoC, connected A129271, covering A367869.
A143543 counts simple labeled graphs by number of connected components.
A323818 counts connected set-systems, unlabeled A323819, ranks A326749.
A367867 = graphs contradict strict AoC, connected A140638, covering A367868.
Cf. A006126, A316983, A321405, A326754, A326870, A326877, A367770, A367901, A367902, A367903.

Table[Length[Select[Subsets[Subsets[Range[n],{2}]], Length[#]==Length[Union@@#]&]],{n,0,5}]

\\ Here b(n) is A367863(n)
b(n) = sum(k=0, n, (-1)^(n-k) * binomial(n,k) * binomial(binomial(k,2), n))
a(n) = sum(k=0, n, binomial(n,k) * b(k)) \\ Andrew Howroyd, Dec 29 2023

Binomial transform of A367863.

Terms a(8) and beyond from Andrew Howroyd, Dec 29 2023

cp's OEIS Frontend

A016031 De Bruijn's sequence: 2^(2^(n-1) - n): number of ways of arranging 2^n bits in circle so all 2^n consecutive strings of length n are distinct.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

Formula

A116508 a(n) = C( C(n,2), n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Python

Sage

Formula

Extensions

A367863 Number of n-vertex labeled simple graphs with n edges and no isolated vertices.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A367906 Numbers k such that it is possible to choose a different binary index of each binary index of k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

A000371 a(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(n,k)*2^(2^k).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

A000371 a(n) = Sum_{k=0..n} (-1)^(n-k)binomial(n,k)2^(2^k).