A323818 -id:A323818 - cp's OEIS frontend

A007297 Number of connected graphs on n labeled nodes on a circle with straight-line edges that don't cross.

1, 1, 4, 23, 156, 1162, 9192, 75819, 644908, 5616182, 49826712, 448771622, 4092553752, 37714212564, 350658882768, 3285490743987, 30989950019532, 294031964658430, 2804331954047160, 26870823304476690, 258548658860327880

Offset: 1

N. J. A. Sloane, Mira Bernstein

Apart from the initial 1, reversion of g.f. for A162395 (squares with signs): see A263843.

			G.f. = x*(1 + x + 4*x^2 + 23*x^3 + 156*x^4 + 1162*x^5 + 9192*x^6 + 75819*x^7 + ...).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

N. J. A. Sloane, Table of n, a(n) for n = 1..999 (first 101 terms from T. D. Noe)
M. Aguiar and J.-L. Loday, Quadri-algebras, J. Pure Appl. Algebra, 191 (2004), 205-221.
R. Bacher, On generating series of complementary plane trees arXiv:math/0409050 [math.CO], 2004.
P. Barry and A. Hennessy, Four-term Recurrences, Orthogonal Polynomials and Riordan Arrays, Journal of Integer Sequences, 2012, article 12.4.2. - From _N. J. A. Sloane_, Sep 21 2012
F. R. Bernhart & N. J. A. Sloane, Emails, April-May 1994
F. Cazals, Combinatorics of Non-Crossing Configurations, Studies in Automatic Combinatorics, Volume II (1997).
E. Deutsch and B. E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, arXiv:math/0407326 [math.CO], 2004; J. Num. Theory 117 (2006), 191-215.
C. Domb and A. J. Barrett, Enumeration of ladder graphs, Discrete Math. 9 (1974), 341-358 (column sums in Table 2).
Michael Drmota, Anna de Mier, Marc Noy, Extremal statistics on non-crossing configurations, Discrete Math. 327 (2014), 103--117. MR3192420. See Eq. (3). - N. J. A. Sloane, May 18 2014
Guillermo Esteban, Clemens Huemer, Rodrigo I. Silveira, New production matrices for geometric graphs, arXiv:2003.00524 [math.CO], 2020.
Sen-Peng Eu, Shu-Chung Liu and Yeong-Nan Yeh, On the congruences of some combinatorial numbers, Stud. Appl. Math. vol. 116 (2006) pp. 135-144.
P. Flajolet and M. Noy, Analytic Combinatorics of Non-crossing Configurations
P. Flajolet and M. Noy, Analytic combinatorics of non-crossing configurations, Discrete Math., 204, 203-229, 1999.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 486.
Loïc Foissy, Free quadri-algebras and dual quadri-algebras, arXiv:1504.06056 [math.CO], 2015.
I. M. Gessel, A short proof of the Deutsch-Sagan congruence for connected non crossing graphs, arXiv preprint arXiv:1403.7656 [math.CO], 2014.
Marco Kuhlmann, Tabulation of Noncrossing Acyclic Digraphs, arXiv:1504.04993 [cs.DS], 2015.
M. Kuhlmann, P. Jonsson, Parsing to Noncrossing Dependency Graphs, Transactions of the Association for Computational Linguistics, vol. 3, pp. 559-570, 2015.
Sara Madariaga, Gröbner-Shirshov bases for the non-symmetric operads of dendriform algebras and quadri-algebras, arXiv:1304.5184 [math.RA], 2013.
B. Vallette, Manin products, Koszul duality, Loday algebras and Deligne conjecture, arXiv:math/0609002 [math.QA], 2006-2007; J. Reine Angew. Math. 620 (2008), 105-164.
Gus Wiseman, The a(5) = 156 connected non-crossing graphs.
Gus Wiseman, Constructive Mathematica program for A007297.
Anssi Yli-Jyrä and Carlos Gómez-Rodríguez, Generic Axiomatization of Families of Noncrossing Graphs in Dependency Parsing, arXiv:1706.03357 [cs.CL], 2017.
Index entries for reversions of series

Cf. A162395, A000290. 4th row of A107111. Row sums of A089434.
See A263843 for a variant.
Cf. A000108 (non-crossing set partitions), A001006, A001187, A054726 (non-crossing graphs), A054921, A099947, A194560, A293510, A323818, A324167, A324169, A324173.

A007297:=proc(n) if n = 1 then 1 else add(binomial(3*n - 3, n + j)*binomial(j - 1, j - n + 1), j = n - 1 .. 2*n - 3)/(n - 1); fi; end;

CoefficientList[ InverseSeries[ Series[(x-x^2)/(1+x)^3, {x, 0, 20}], x], x] // Rest (* From Jean-François Alcover, May 19 2011, after PARI prog. *)
Table[Binomial[3n, 2n+1] Hypergeometric2F1[1-n, n, 2n+2, -1]/n, {n, 1, 20}] (* Vladimir Reshetnikov, Oct 25 2015 *)

a(n)=if(n<0,0,polcoeff(serreverse((x-x^2)/(1+x)^3+O(x^(n+2))),n+1)) /* Ralf Stephan */

Apart from initial term, g.f. is the series reversion of (x-x^2)/(1+x)^3 (A162395). See A263843. - Vladimir Kruchinin, Feb 08 2013
G.f.: (g-z)/z, where g=-1/3+(2/3)*sqrt(1+9z)*sin((1/3)*arcsin((2+27z+54z^2)/2/(1+9*z)^(3/2))). - Emeric Deutsch, Dec 02 2002
a(n) = (1/n)*Sum_{k=0..n} binomial(3n, n-k-1)*binomial(n+k-1, k). - Paul Barry, May 11 2005
a(n) = 4^(n-1)*(Gamma(3*n/2-1)/Gamma(n/2+1)/Gamma(n) -Gamma((3*n-1)/2)/ Gamma( (n+1)/2)/Gamma(n+1)). - Mark van Hoeij, Aug 27 2005, adapted to offset Feb 21 2020 by R. J. Mathar
a(n) = 4^n * binomial(3*n/2, n/2) / (9*n-6) - 4^(n-1) * binomial(3*(n-1)/2, (n-1)/2 ) / n. - Mark van Hoeij, Aug 27 2005, adapted to offset Feb 21 2020 by R. J. Mathar
D-finite with recurrence: n*(n-1)*(3*n-4)*a(n) +36*(n-1)*a(n-1) -12*(3*n-8)*(3*n-1)*(3*n-7)*a(n-2)=0. - Mark van Hoeij, Aug 27 2005, adapted to offset Feb 21 2020 by R. J. Mathar
a(n) = (1/n)*Sum_{k=0..n} C(3n, k)*C(2n-k-2, n-1). - Paul Barry, Sep 27 2005
a(n) ~ (2-sqrt(3)) * 6^n * 3^(n/2) / (sqrt(2*Pi) * n^(3/2)). - Vaclav Kotesovec, Mar 17 2014
a(n) = binomial(3*n,2*n+1)*hypergeom([1-n,n], [2*n+2], -1)/n. - Vladimir Reshetnikov, Oct 25 2015
a(n) = 2*A078531(n) - A085614(n+1). - Vladimir Reshetnikov, Apr 24 2016

Better description from Philippe Flajolet, Apr 20 2000
More terms from James Sellers, Aug 21 2000
Definition revised and initial a(1)=1 added by N. J. A. Sloane, Nov 05 2015 at the suggestion of Axel Boldt. Some of the formulas may now need to be adjusted slightly.

A326749 BII-numbers of connected set-systems.

Original entry on oeis.org

0, 1, 2, 4, 5, 6, 7, 8, 16, 17, 20, 21, 22, 23, 24, 25, 28, 29, 30, 31, 32, 34, 36, 37, 38, 39, 40, 42, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82

Offset: 1

Gus Wiseman, Jul 23 2019

A binary index of n is any position of a 1 in its reversed binary expansion. We define the set-system with BII-number n to be obtained by taking the binary indices of each binary index of n. Every finite set of finite nonempty sets has a different BII-number. For example, 18 has reversed binary expansion (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. Elements of a set-system are sometimes called edges.

			The sequence of all connected set-systems together with their BII-numbers begins:
   0: {}
   1: {{1}}
   2: {{2}}
   4: {{1,2}}
   5: {{1},{1,2}}
   6: {{2},{1,2}}
   7: {{1},{2},{1,2}}
   8: {{3}}
  16: {{1,3}}
  17: {{1},{1,3}}
  20: {{1,2},{1,3}}
  21: {{1},{1,2},{1,3}}
  22: {{2},{1,2},{1,3}}
  23: {{1},{2},{1,2},{1,3}}
  24: {{3},{1,3}}
  25: {{1},{3},{1,3}}
  28: {{1,2},{3},{1,3}}
  29: {{1},{1,2},{3},{1,3}}
  30: {{2},{1,2},{3},{1,3}}
  31: {{1},{2},{1,2},{3},{1,3}}

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

Positions of 0's and 1's in A326753.
Cf. A000120, A001187, A029931, A048143, A048793, A070939, A072639, A323818, A326031, A326702.
Other BII-numbers: A309314 (hyperforests), A326701 (set partitions), A326703 (chains), A326704 (antichains), A326750 (clutters), A326751 (blobs), A326752 (hypertrees), A326754 (covers).

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Select[Range[0,100],Length[csm[bpe/@bpe[#]]]<=1&]

from itertools import count, islice
from sympy.utilities.iterables import connected_components
def bin_i(n): #binary indices
    return([(i+1) for i, x in enumerate(bin(n)[2:][::-1]) if x =='1'])
def a_gen():
    yield 0
    for n in count(1):
        a, E = [bin_i(k) for k in bin_i(n)], []
        m = len(a)
        for i in range(m):
            for j in a[i]:
                for k in range(m):
                    if j in a[k]:
                        E.append((i, k))
        for v in connected_components((list(range(m)), E)):
            if len(v) == m:
                yield n
A326749_list = list(islice(a_gen(), 100)) # John Tyler Rascoe, Jul 25 2024

A129271 Number of labeled n-node connected graphs with at most one cycle.

Original entry on oeis.org

1, 1, 1, 4, 31, 347, 4956, 85102, 1698712, 38562309, 980107840, 27559801736, 849285938304, 28459975589311, 1030366840792576, 40079074477640850, 1666985134587145216, 73827334760713500233, 3468746291121007607808, 172335499299097826575564, 9027150377126199463936000

Offset: 0

Washington Bomfim, May 10 2008

The majority of those graphs of order 4 are trees since we have 16 trees and only 9 unicycles. See example.

Also connected graphs covering n vertices with at most n edges. The unlabeled version is A005703. - Gus Wiseman, Feb 19 2024

			a(4) = 16 + 3*3 = 31.
From _Gus Wiseman_, Feb 19 2024: (Start)
The a(0) = 1 through a(3) = 4 graph edge sets:
  {}  .  {{1,2}}  {{1,2},{1,3}}
                  {{1,2},{2,3}}
                  {{1,3},{2,3}}
                  {{1,2},{1,3},{2,3}}
(End)

J. Riordan, An Introduction to Combinatorial Analysis, Dover, 2002, p. 2.

Andrew Howroyd, Table of n, a(n) for n = 0..100
Wikipedia, PseudoForest.

Cf. A129137, A000272.
For any number of edges we have A001187, unlabeled A001349.
The unlabeled version is A005703.
The case of equality is A057500, covering A370317, cf. A370318.
The non-connected non-covering version is A133686.
The connected complement is A140638, unlabeled A140636, covering A367868.
The non-connected covering version is A367869 or A369191.
The version with loops is A369197, non-connected A369194.
A006125 counts graphs, A000088 unlabeled.
A006129 counts covering graphs, A002494 unlabeled.
A062734 counts connected graphs by number of edges.
Cf. A006649, A116508, A134964, A143543, A323818, A367862, A367863, A367867, A367916, A367917, A368951.

a := n -> `if`(n=0,1,((n-1)*exp(n)*GAMMA(n-1,n)+n^(n-2)*(3-n))/2):
seq(simplify(a(n)),n=0..16); # Peter Luschny, Jan 18 2016

nn=20;t=Sum[n^(n-1)x^n/n!,{n,1,nn}];Range[0,nn]!CoefficientList[Series[ Log[1/(1-t)]/2+t/2-3t^2/4+1,{x,0,nn}],x]  (* Geoffrey Critzer, Mar 23 2013 *)

seq(n)={my(t=-lambertw(-x + O(x*x^n))); Vec(serlaplace(log(1/(1-t))/2 + t/2 - 3*t^2/4 + 1))} \\ Andrew Howroyd, Nov 07 2019

a(0) = 1, for n >=1, a(n) = A000272(n) + A057500(n) = n^{n-2} + (n-1)(n-2)/2Sum_{r=1..n-2}( (n-3)!/(n-2-r)! )n^(n-2-r)
E.g.f.: log(1/(1-T(x)))/2 + T(x)/2 - 3*T(x)^2/4 + 1, where T(x) is the e.g.f. for A000169. - Geoffrey Critzer, Mar 23 2013
a(n) = ((n-1)*e^n*GAMMA(n-1,n)+n^(n-2)*(3-n))/2 for n>=1. - Peter Luschny, Jan 18 2016

Terms a(17) and beyond from Andrew Howroyd, Nov 07 2019

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

Original entry on oeis.org

0, 0, 0, 1, 0, 0, 0, 2, 1, 0, 0, 1, 0, 0, 0, 4, 0, 1, 0, 1, 0, 0, 0, 3, 1, 0, 2, 1, 0, 0, 0, 6, 0, 0, 0, 4, 0, 0, 0, 3, 0, 0, 0, 1, 1, 0, 0, 7, 1, 1, 0, 1, 0, 3, 0, 3, 0, 0, 0, 2, 0, 0, 1, 10, 0, 0, 0, 1, 0, 0, 0, 10, 0, 0, 1, 1, 0, 0, 0, 7, 4, 0, 0, 2, 0, 0

Offset: 1

Gus Wiseman, Dec 27 2023

nonn

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 counted under a(36).

			The a(1) = 0 through a(24) = 3 factorizations:
 ... 2*2 ... 2*4   3*3 .. 2*2*3 ... 2*8     . 2*3*3 . 2*2*5 ... 2*2*6
             2*2*2                  4*4                         2*3*4
                                    2*2*4                       2*2*2*3
                                    2*2*2*2

For unlabeled graphs: A140637, complement A134964.
For labeled graphs: A367867, A367868, A140638, complement A133686.
For set-systems: A367903, ranks A367907, complement A367902, ranks A367906.
For non-isomorphic set-systems: A368094, A368409, complement A368095.
For non-isomorphic multiset partitions: A368097, A355529, A368411.
Complement for non-isomorphic multiset partitions: A368098, A368100.
The complement is counted by A368414.
For non-isomorphic set multipartitions: A368421, complement A368422.
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.

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

a(n) + A368414(n) = A001055(n).

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

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

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Dec 29 2023

nonn

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).

			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

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.

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

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

A099947 Number of topologically connected set partitions of {1,...,n}.

Original entry on oeis.org

1, 1, 1, 1, 2, 6, 21, 85, 385, 1907, 10205, 58455, 355884, 2290536, 15518391, 110283179, 819675482, 6355429550, 51293023347, 430062712439, 3739408304962, 33665192703946, 313354708842791, 3011545611755271, 29847401178719637, 304713973031878687, 3201007359886598431

Offset: 0

N. J. A. Sloane, Nov 12 2004

A set partition of {1,...,n} is topologically connected if the graph whose vertices are the blocks and whose edges are crossing pairs of blocks is connected, where two blocks cross each other if they are of the form {{...x...y...}, {...z...t...}} for some x < z < y < t or z < x < t < y. - Gus Wiseman, Feb 19 2019

			O.g.f.: A(x) = 1 + x + x^2 + x^3 + 2*x^4 + 6*x^5 + 21*x^6 + 85*x^7 +...
From _Paul D. Hanna_, Apr 16 2013: (Start)
The o.g.f. satisfies
(1) A(x) = 1 + x/A(x) + 2*x^2/A(x)^2 + 5*x^3/A(x)^3 + 15*x^4/A(x)^4 + 52*x^5/A(x)^5 + 203*x^6/A(x)^6 + ... + A000110(n)*x^n/A(x)^n + ...
(2) A(x) = 1 + x/(A(x)-x) + x^2/((A(x)-x)*(A(x)-2*x)) + x^3/((A(x)-x)*(A(x)-2*x)*(A(x)-3*x)) + x^4/((A(x)-x)*(A(x)-2*x)*(A(x)-3*x)*(A(x)-4*x)) + ... (End)
From _Gus Wiseman_, Feb 19 2019: (Start)
The a(1) = 1 through a(6) = 21 topologically connected set partitions:
  {{1}}  {{12}}  {{123}}  {{1234}}    {{12345}}    {{123456}}
                          {{13}{24}}  {{124}{35}}  {{1235}{46}}
                                      {{13}{245}}  {{124}{356}}
                                      {{134}{25}}  {{1245}{36}}
                                      {{135}{24}}  {{1246}{35}}
                                      {{14}{235}}  {{125}{346}}
                                                   {{13}{2456}}
                                                   {{134}{256}}
                                                   {{1345}{26}}
                                                   {{1346}{25}}
                                                   {{135}{246}}
                                                   {{1356}{24}}
                                                   {{136}{245}}
                                                   {{14}{2356}}
                                                   {{145}{236}}
                                                   {{146}{235}}
                                                   {{15}{2346}}
                                                   {{13}{25}{46}}
                                                   {{14}{25}{36}}
                                                   {{14}{26}{35}}
                                                   {{15}{24}{36}}
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..222
Janet Simpson Beissinger, The enumeration of irreducible combinatorial objects, J. Comb. Theory, Ser. A, 38 (1985), pp. 143-169. (Example 6.2)
Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, A family of Bell transformations, arXiv:1803.07727 [math.CO], 2018.
Kenneth J. Dykema, Generating functions for purely crossing partitions, arXiv:1602.03469 [math.CO], 2016. See column NIS in Table 2 p. 8.
FindStat, The number of topologically connected components of a set partition.
Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.
Martin Klazar, Bell numbers, their relatives and algebraic differential equations
Martin Klazar, Bell numbers, their relatives and algebraic differential equations, J. Combin. Theory, A 102 (2003), 63-87.

Cf. A000108, A000110, A001187, A007297, A016098, A092918, A268814, A268815, A305078, A306438, A323818, A324166, A324172, A324173.

a[0] = 1; a[n_] := Module[{A = 1 + x}, For[i = 1, i <= n, i++, A = Sum[x^m/Product[A - k*x + x*O[x]^n, {k, 1, m}], {m, 0, n}]]; Coefficient[A, x^n]]; Table[a[n], {n, 0, 24}] (* Jean-François Alcover, Sep 13 2013, after Paul D. Hanna *)
nn=8;
nonXQ[stn_]:=!MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;x_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
Solve[Table[BellB[n]==Sum[Product[a[Length[s]],{s,stn}],{stn,Select[sps[Range[n]],nonXQ]}],{n,nn}],Array[a,nn]] (* Gus Wiseman, Feb 19 2019 *)

{a(n)=if(n<0, 0, polcoeff( x/serreverse(x*serlaplace(exp(exp(x+x*O(x^n))-1))), n))} /* Michael Somos, Sep 22 2005 */

{a(n)=local(A=1+x); for(i=1, n, A=sum(m=0, n, x^m/prod(k=1, m, A - k*x +x*O(x^n)) )); polcoeff(A, n)} \\ Paul D. Hanna, Apr 16 2013

From Paul D. Hanna, Apr 16 2013: (Start)
O.g.f. A(x) satisfies
(1) A(x) = Sum_{n>=0} A000110(n)*x^n/A(x)^n, where A000110 are the Bell numbers.
(2) A(x) = Sum_{n>=0} x^n / Product_{k=1..n} (A(x) - k*x).
(3) A(x) = 1/(1 - x/(A(x) - 1*x/(1 - x/(A(x) - 2*x/(1 - x/(A(x) - 3*x/(1 - x/(A(x) - 4*x/(1 - x/(A(x) - ... )))))))))), a continued fraction. (End)
B(n) = Sum_p Product_{s in p} a(|s|) where p is a non-crossing set partition of {1,...,n} and B = A000110. In words, every set partition of {1,...,n} can be uniquely decomposed as a non-crossing set partition together with a topologically connected set partition of each block. - Gus Wiseman, Feb 19 2019

Name edited by Gus Wiseman, Feb 19 2019

A326753 Number of connected components of the set-system with BII-number n.

Original entry on oeis.org

0, 1, 1, 2, 1, 1, 1, 1, 1, 2, 2, 3, 2, 2, 2, 2, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

Offset: 0

Gus Wiseman, Jul 23 2019

A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793. We define the set-system with BII-number n to be obtained by taking the binary indices of each binary index of n. Every finite set of finite nonempty sets has a different BII-number. For example, 18 has reversed binary expansion (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. Elements of a set-system are sometimes called edges.

			The set-system {{1,2},{1,4},{3}} with BII-number 268 has two connected components, so a(268) = 2.

John Tyler Rascoe, Table of n, a(n) for n = 0..10000
John Tyler Rascoe, Log scatterplot of a(n), n=0..32906.

Positions of 0's and 1's are A326749.
Cf. A000120, A001187, A029931, A048143, A048793, A070939, A072639, A304716, A305078, A305079 (same for MM-numbers), A323818, A326031, A326702.
Ranking sequences using BII-numbers: A309314 (hyperforests), A326701 (set partitions), A326703 (chains), A326704 (antichains), A326750 (clutters), A326751 (blobs), A326752 (hypertrees), A326754 (covers).

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Length[csm[bpe/@bpe[n]]],{n,0,100}]

from sympy.utilities.iterables import connected_components
def bin_i(n): #binary indices
    return([(i+1) for i, x in enumerate(bin(n)[2:][::-1]) if x =='1'])
def A326753(n):
    E,a = [],[bin_i(k) for k in bin_i(n)]
    m = len(a)
    for i in range(m):
        for j in a[i]:
            for k in range(m):
                if j in a[k]:
                    E.append((i,k))
    return(len(connected_components((list(range(m)),E)))) # John Tyler Rascoe, Jul 16 2024

a(A072639(n)) = n. - John Tyler Rascoe, Jul 15 2024

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.

			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).

cp's OEIS Frontend

A007297 Number of connected graphs on n labeled nodes on a circle with straight-line edges that don't cross.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A326749 BII-numbers of connected set-systems.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

A129271 Number of labeled n-node connected graphs with at most one cycle.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

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

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A099947 Number of topologically connected set partitions of {1,...,n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs