A052265 -id:A052265 - cp's OEIS frontend

A028657 Triangle read by rows: T(n,k) = number of n-node graphs with k nodes in distinguished bipartite block, k = 0..n.

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 7, 4, 1, 1, 5, 13, 13, 5, 1, 1, 6, 22, 36, 22, 6, 1, 1, 7, 34, 87, 87, 34, 7, 1, 1, 8, 50, 190, 317, 190, 50, 8, 1, 1, 9, 70, 386, 1053, 1053, 386, 70, 9, 1, 1, 10, 95, 734, 3250, 5624, 3250, 734, 95, 10, 1, 1, 11, 125, 1324, 9343, 28576, 28576, 9343, 1324, 125, 11, 1

Offset: 0

Vladeta Jovovic, Jun 16 2000

Also, row n gives the number of unlabeled bicolored graphs having k nodes of one color and n-k nodes of the other color; the color classes are not interchangeable.
Also the number of principal transversal matroids (also known as fundamental transversal matroids) of size n and rank k (originally enumerated by Brylawski). - Gordon F. Royle, Oct 30 2007
This sequence is also obtained if we read the array A(m,n) = number of inequivalent m X n binary matrices by antidiagonals, where equivalence means permutations of rows or columns (m>=0, n>=0) [Kerber]. - N. J. A. Sloane, Sep 01 2013

			The triangle T(n,k) begins:
  1;
  1,  1;
  1,  2,  1;
  1,  3,  3,  1;
  1,  4,  7,  4,  1;
  1,  5, 13, 13,  5,  1;
  1,  6, 22, 36, 22,  6,  1;
  ...
For example, there are 36 graphs on 6 nodes with a distinguished bipartite block with 3 nodes.
The array A(m,n) (m>=0, n>=0) (see Comments) begins:
  1 1  1    1     1      1        1         1           1 ...
  1 2  3    4     5      6        7         8           9 ...
  1 3  7   13    22     34       50        70          95 ...
  1 4 13   36    87    190      386       734        1324 ...
  1 5 22   87   317   1053     3250      9343       25207 ...
  1 6 34  190  1053   5624    28576    136758      613894 ...
  1 7 50  386  3250  28576   251610   2141733    17256831 ...
  1 8 70  734  9343 136758  2141733  33642660   508147108 ...
  1 9 95 1324 25207 613894 17256831 508147108 14685630688 ...
... - _N. J. A. Sloane_, Sep 01 2013

R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.

Alois P. Heinz, Rows n = 0..45, flattened (first 20 rows from R. W. Robinson)
Thomas H. Brylawski, An affine representation for transversal geometries, Studies in Appl. Math. 54 (1975), no. 2, 143-160.
F. Harary, L. March and R. W. Robinson, On enumerating certain design problems in terms of bicolored graphs with no isolates, Environment and Planning, B 5 (1978), 31-43. See Table 1.
F. Harary, L. March and R. W. Robinson, On enumerating certain design problems in terms of bicolored graphs with no isolates, Environment and Planning B: Urban Analytics and City Science, 5 (1978), 31-43. [Annotated scanned copy] See Table 1.
M. A. Harrison, On the number of classes of binary matrices, IEEE Trans. Computers, 22 (1973), 1048-1051.
Vladeta Jovovic, Binary matrices up to row and column permutations
A. Kerber, Experimentelle Mathematik, Séminaire Lotharingien de Combinatoire. Institut de Recherche Math. Avancée, Université Louis Pasteur, Strasbourg, Actes 19 (1988), 77-83. [Annotated scanned copy]
B. Misek, On the number of classes of strongly equivalent incidence matrices, (Czech with English summary) Casopis Pest. Mat. 89 1964 211-218.
Carlos Simpson, Learning proofs for the classification of nilpotent semigroups, arXiv:2106.03015 [cs.LG], 2021.
Index to OEIS entries related to number of inequivalent matrices modulo permutation of row and columns.

Row sums give A049312.
A246106 is a very similar array.
Cf. A055080, A049312, A052265, A242093.
Diagonals of the array A(m,n) give A002724, A002725, A002728.
Rows (or columns) give A002623, A002727, A006148, A052264.
A(n,k) = A353585(2, n, k).

b:= proc(n, i) option remember; `if`(n=0, {0}, `if`(i<1, {},
      {seq(map(p-> p+j*x^i, b(n-i*j, i-1) )[], j=0..n/i)}))
    end:
g:= proc(n, k) option remember; add(add(2^add(add(igcd(i, j)*
      coeff(s, x, i)* coeff(t, x, j), j=1..degree(t)),
      i=1..degree(s))/mul(i^coeff(s, x, i)*coeff(s, x, i)!,
      i=1..degree(s))/mul(i^coeff(t, x, i)*coeff(t, x, i)!,
      i=1..degree(t)), t=b(n+k$2)), s=b(n$2))
    end:
A:= (n, k)-> g(min(n, k), abs(n-k)):
seq(seq(A(n, d-n), n=0..d), d=0..14); # Alois P. Heinz, Aug 01 2014

b[n_, i_] := b[n, i] = If[n == 0, {0}, If[i<1, {}, Union[ Flatten[ Table[ Function[ {p}, p + j*x^i] /@ b[n - i*j, i-1], {j, 0, n/i}]]]]];
g[n_, k_] := g[n, k] = Sum[ Sum[ 2^Sum[ Sum[GCD[i, j] * Coefficient[s, x, i] * Coefficient[t, x, j], {j, 1, Exponent[t, x]}], {i, 1, Exponent[s, x]}] / Product[i^Coefficient[s, x, i] * Coefficient[s, x, i]!, {i, 1, Exponent[s, x]}] / Product[i^Coefficient[t, x, i] * Coefficient[t, x, i]!, {i, 1, Exponent[t, x]}], {t, b[n+k, n+k]}], {s, b[n, n]}];
A[n_, k_] := g[Min[n, k], Abs[n-k]];
Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 14}] // Flatten (* Jean-François Alcover, Jan 28 2015, after Alois P. Heinz *)

permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
K(q, t)={sum(j=1, #q, gcd(t, q[j]))}
A(n, m)={my(s=0); forpart(q=m, s+=permcount(q)*polcoef(exp(sum(t=1, n, 2^K(q, t)/t*x^t) + O(x*x^n)), n)); s/m!}
{ for(r=0, 10, for(k=0, r, print1(A(r-k,k), ", ")); print) } \\ Andrew Howroyd, Mar 25 2020

\\ G(k,x) gives k-th column as rational function (see Jovovic link).
permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
Fix(q,x)={my(v=divisors(lcm(Vec(q))), u=apply(t->2^sum(j=1, #q, gcd(t, q[j])), v)); 1/prod(i=1, #v, my(t=v[i]); (1-x^t)^(sum(j=1, i, my(d=t/v[j]); if(!frac(d), moebius(d)*u[j]))/t))}
G(m,x)={my(s=0); forpart(q=m, s+=permcount(q)*Fix(q,x)); s/m!}
T(n,k)={my(m=max(k, n-k)); polcoef(G(n-m, x + O(x*x^m)), m)} \\ Andrew Howroyd, Mar 26 2020

A028657(n,k)=A353585(2, n, k) \\ M. F. Hasler, May 01 2022

A(m,n) = Sum_{p in P(m), q in P(n)} 2^Sum_{i in p, j in q} gcd(i,j) / (N(p) N(q)) where P(m) are the partition of m (see e.g., A036036), N(p) = Product_{distinct parts x in p} x^m(x)*m(x)!, m(x) = multiplicity of x in p. [corrected by Anders Kaseorg, Oct 04 2024]

A003180 Number of equivalence classes of Boolean functions of n variables under action of symmetric group.

Original entry on oeis.org

2, 4, 12, 80, 3984, 37333248, 25626412338274304, 67516342973185974328175690087661568, 2871827610052485009904013737758920847669809829897636746529411152822140928

Offset: 0

N. J. A. Sloane

A003180(n-1) is the number of equivalence classes of Boolean functions of n variables from Post class F(8,inf) under action of symmetric group.
Also number of nonisomorphic sets of subsets of an n-set.
Also the number of unlabeled hypergraphs on n nodes [Qian]. - N. J. A. Sloane, May 12 2014
The number of unlabeled hypergraphs with empty hyperedges allowed on n nodes. Compare with A000612 where empty hyperedges are not allowed. - Michael Somos, Feb 15 2019
In the 1995 Encyclopedia of Integer Sequences this sequence appears twice, as both M1265 and M3458 (one entry began at n=0, the other at n=1).

			From _Gus Wiseman_, Aug 05 2019: (Start)
Non-isomorphic representatives of the a(0) = 2 through a(2) = 12 sets of subsets:
  {}    {}        {}
  {{}}  {{}}      {{}}
        {{1}}     {{1}}
        {{},{1}}  {{1,2}}
                  {{},{1}}
                  {{1},{2}}
                  {{},{1,2}}
                  {{2},{1,2}}
                  {{},{1},{2}}
                  {{},{2},{1,2}}
                  {{1},{2},{1,2}}
                  {{},{1},{2},{1,2}}
(End)

M. A. Harrison, Introduction to Switching and Automata Theory. McGraw Hill, NY, 1965, p. 147.
D. E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.1.1, p. 79.
S. Muroga, Threshold Logic and Its Applications. Wiley, NY, 1971, p. 38, Table 2.3.2. - Row 5.
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).

Vladeta Jovovic, Table of n, a(n) for n = 0..11
Steven R. Finch, Mathematical Constants II, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018.
Toru Ishihara, Enumeration of hypergraphs, European Journal of Combinatorics, Volume 22, Issue 4, May 2001.
S. Muroga, Threshold Logic and Its Applications, Wiley, NY, 1971. [Annotated scans of a few pages]
Jianguo Qian, Enumeration of unlabeled uniform hypergraphs, Discrete Math. 326 (2014), 66--74. MR3188989. See Table 1, p. 71. - _N. J. A. Sloane_, May 12 2014
Marko Riedel, Cycle indices for the enumeration of non-isomorphic hypergraphs, Mathematics Stack Exchange, 2018.
Marko Riedel, Implementation of the Ishihara algorithm for cycle indices of the action of the symmetric group S_n on sets of subsets of an n-set.
Index entries for sequences related to Boolean functions

Twice A000612. Cf. A001146. Row sums of A052265.

Cf. A003181, A055621.

with(numtheory):with(combinat):
for n from 1 to 10 do
p:=partition(n): s:=0: for k from 1 to nops(p) do q:=convert(p[k],multiset): for i from 0 to n do a(i):=0: od:
  for i from 1 to nops(q) do a(q[i][1]):=q[i][2]: od:
  c:=1: ord:=1: for i from 1 to n do c:=c*a(i)!*i^a(i):ord:=lcm(ord,i): od: ss:=0:
  for i from 1 to ord do if ord mod i=0 then ss:=ss+phi(ord/i)*2^add(gcd(j,i)*a(j),j=1..n): fi: od:
  s:=s+2^(ss/ord)/c:
od:
printf(`%d `,n):
printf("%d ",s):
od: # Vladeta Jovovic, Sep 19 2006

a[n_] := Sum[1/Function[p, Product[Function[c, j^c*c!][Coefficient[p, x, j]], {j, 1, Exponent[p, x]}]][Total[x^l]]*2^(Function[w, Sum[Product[ 2^GCD[t, l[[i]]], {i, 1, Length[l]}], {t, 1, w}]/w][If[l == {}, 1, LCM @@ l]]), {l, IntegerPartitions[n]}];
a /@ Range[0, 11] (* Jean-François Alcover, Feb 19 2020, after Alois P. Heinz in A000612 *)
fix[s_] := 2^Sum[Sum[MoebiusMu[i/d] 2^Sum[GCD[j, d] s[j], {j, Keys[s]}], {d, Divisors[i]}]/i, {i, LCM @@ Keys[s]}];
a[0] = 2;
a[n_] := Sum[fix[s]/Product[j^s[j] s[j]!, {j, Keys[s]}], {s, Counts /@ IntegerPartitions[n]}];
Table[a[n], {n, 0, 8}]
(* Andrey Zabolotskiy, Mar 24 2020, after Christian G. Bower's formula; requires Mathematica 10+ *)

a(n) = Sum_{1*s_1+2*s_2+...=n} (fixA[s_1, s_2, ...]/(1^s_1*s_1!*2^s_2*s_2!*...)) where fixA[s_1, s_2, ...] = 2^Sum_{i>=1} ( Sum_{d|i} ( mu(i/d)*( 2^Sum_{j>=1} ( gcd(j, d)*s_j))))/i.

a(n) = 2 * A000612(n).

More terms from Vladeta Jovovic, Sep 19 2006

Edited with formula by Christian G. Bower, Jan 08 2004

A039754 Irregular triangle read by rows: T(n,k) = number of binary codes of length n with k words (n >= 0, 0 <= k <= 2^n); also number of 0/1-polytopes with vertices from the unit n-cube; also number of inequivalent Boolean functions of n variables with exactly k nonzero values under action of Jevons group.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 3, 3, 6, 3, 3, 1, 1, 1, 1, 4, 6, 19, 27, 50, 56, 74, 56, 50, 27, 19, 6, 4, 1, 1, 1, 1, 5, 10, 47, 131, 472, 1326, 3779, 9013, 19963, 38073, 65664, 98804, 133576, 158658, 169112, 158658, 133576, 98804, 65664, 38073, 19963, 9013, 3779, 1326, 472, 131, 47, 10, 5, 1, 1

Offset: 0

N. J. A. Sloane

For N=1 through N=5, the first 2^(N-1) terms of row N are also found in triangle A171871, which is related to A005646. This was shown for all N by Andrew Weimholt, Dec 30 2009. [Robert Munafo, Jan 25 2010]

			Triangle begins:
  k  0  1  2  3   4   5   6   7   8   9  10  11  12 13 14 15 16   sums
n
0    1  1                                                            2
1    1  1  1                                                         3
2    1  1  2  1   1                                                  6
3    1  1  3  3   6   3   3   1   1                                 22
4    1  1  4  6  19  27  50  56  74  56  50  27  19  6  4  1  1    402

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 112.
M. A. Harrison, Introduction to Switching and Automata Theory. McGraw Hill, NY, 1965, p. 150.

Jan Brandts, A. Cihangir, Enumeration and investigation of acute 0/1-simplices modulo the action of the hyperoctahedral group, arXiv preprint arXiv:1512.03044 [math.CO], 2015. See Fig. 13.
D. Condon, S. Coskey, L. Serafin, and C. Stockdale, On generalizations of separating and splitting families, arXiv preprint arXiv:1412.4683 [math.CO], 2014-2015.
Jacob Feldman, A catalog of Boolean concepts, Journal of Mathematical Psychology, Volume 47, Issue 1, 2003, 75-89.
Harald Fripertinger, Enumeration, construction and random generation of block codes, Designs, Codes, Crypt., 14 (1998), 213-219.
Harald Fripertinger, Isometry Classes of Codes
Harald Fripertinger, Enumeration of block codes
Tilman Piesk, Illustration of row 3
Index entries for sequences related to Boolean functions

Row sums give A000616. Cf. A052265.
Rows give A034188, A034189, A034190, etc.
Columns are A034198, A034199, A034200, etc.
Diagonal is A276412.
For other versions of this triangle see A171876, A039754, A276777.
Cf. A171871.

P = IntegerPartitions;
AC[d_Integer] := Module[{C, M, p},(* from W. Y. C. Chen algorithm *) M[p_List] := Plus @@ p!/(Times @@ p * Times @@ (Length /@ Split[p]!)); C[p_List, q_List] := Module[{r, m, k, x}, r = If[0 == Length[q], 1, 2*2^IntegerExponent[LCM @@ q, 2]]; m = LCM @@ Join[p/GCD[r, p], q/GCD[r, q]]; CoefficientList[Expand[Product[(1 + x^(k *r))^((Plus @@ Map[MoebiusMu[k/#]*2^Plus @@ GCD[#*r, Join[p, q]]&, Divisors[k]])/(k*r)), {k, 1, m}]], x]]; Sum[Binomial[d, p]*Plus @@ Plus @@ Outer[M[#1] M[#2] C[#1, #2]*2^(d - Length[#1] - Length[#2]) &, P[p], P[d - p], 1], {p, 0, d}]/(d! 2^d)]; AC[0]  = {1, 1};
AC /@ Range[0, 5] // Flatten (* Jean-François Alcover, Dec 15 2019, after Robert A. Russell in A034189 *)
Table[ CoefficientList[ CycleIndexPolynomial[ GraphData[ {"Hypercube", n}, "AutomorphismGroup"], Array[Subscript[x, ##] &, 2^n]] /. Table[ Subscript[x, i] -> 1 + x^i, {i, 1, 2^n}], x], {n, 1,8}] // Grid (* Geoffrey Critzer, Jan 10 2020 *)

Reference gives g.f.

Fripertinger gives g.f. for the number of classes of (n, m) nonlinear codes over an alphabet of size A.

Corrected and extended by Vladeta Jovovic, Apr 20 2000
Entry revised by N. J. A. Sloane, Sep 19 2016
T(0, 1) = 1 inserted. (There are two 0-ary functions.) - Tilman Piesk, Jan 10 2023

A005744 Expansion of x(1+x-x^2)/((1-x)^4(1+x)).

Original entry on oeis.org

0, 1, 4, 9, 17, 28, 43, 62, 86, 115, 150, 191, 239, 294, 357, 428, 508, 597, 696, 805, 925, 1056, 1199, 1354, 1522, 1703, 1898, 2107, 2331, 2570, 2825, 3096, 3384, 3689, 4012, 4353, 4713, 5092, 5491, 5910, 6350, 6811, 7294, 7799, 8327, 8878, 9453, 10052

Offset: 0

N. J. A. Sloane, Simon Plouffe

Number of n-covers of a 2-set.
Boolean switching functions a(n,s) for s = 2.
Without the initial 0, this is row 1 of the convolution array A213778. - Clark Kimberling, Jun 21 2012
a(n) equals the second column of the triangle A355754. - Eric W. Weisstein, Mar 12 2024

R. J. Clarke, Covering a set by subsets, Discrete Math., 81 (1990), 147-152.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..1000
Milan Janjić, Hessenberg Matrices and Integer Sequences, J. Int. Seq. 13 (2010) # 10.7.8.
A. V. Jayanthan, S. A. Seyed Fakhari, I. Swanson, and S. Yassemi, Induced matching, ordered matching and Castelnuovo-Mumford regularity of bipartite graphs, arXiv:2405.06781 [math.AC], 2024. See p. 17.
Vladeta Jovovic, Binary matrices up to row and column permutations.
Index entries for sequences related to Boolean functions
Index entries for linear recurrences with constant coefficients, signature (3,-2,-2,3,-1).

John W. Layman observes that A003453 appears to be the alternating sum transform (PSumSIGN) of A005744.
Cf. A002623, A005745, A005746, A005747, A005748, A005771, A003180, A008778, A052265.
Cf. A181971, A213778.
Cf. A355754.

CoefficientList[Series[x (1+x-x^2)/((1-x)^4(1+x)),{x,0,50}],x] (* or *) LinearRecurrence[{3,-2,-2,3,-1},{0,1,4,9,17},50] (* Harvey P. Dale, Apr 10 2012 *)

a(n)=([0,1,0,0,0; 0,0,1,0,0; 0,0,0,1,0; 0,0,0,0,1; -1,3,-2,-2,3]^n*[0;1;4;9;17])[1,1] \\ Charles R Greathouse IV, Feb 06 2017

a(n) = A002623(n) - (n+1).
a(n) = n*(n-1)/2 + Sum_{j=1..floor((n+1)/2)} (n-2*j+1)*(n-2*j)/2. - N. J. A. Sloane, Nov 28 2003
From R. J. Mathar, Apr 01 2010: (Start)
a(n) = 5*n/12 - 1/16 + 5*n^2/8 + n^3/12 + (-1)^n/16.
a(n) = 3*a(n-1) - 2*a(n-2) - 2*a(n-3) + 3*a(n-4) - a(n-5). (End)
a(n) = A181971(n+1, n-1) for n > 0. - Reinhard Zumkeller, Jul 09 2012
a(n) + a(n+1) = A008778(n). - R. J. Mathar, Mar 13 2021
E.g.f.: (x*(2*x^2 + 21*x + 27)*cosh(x) + (2*x^3 + 21*x^2 + 27*x - 3)*sinh(x))/24. - Stefano Spezia, Jul 27 2022

Additional comments from Alford Arnold

A054724 Triangle of numbers of inequivalent Boolean functions of n variables with exactly k nonzero values (atoms) under action of complementing group.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 7, 7, 14, 7, 7, 1, 1, 1, 1, 15, 35, 140, 273, 553, 715, 870, 715, 553, 273, 140, 35, 15, 1, 1, 1, 1, 31, 155, 1240, 6293, 28861, 105183, 330460, 876525, 2020239, 4032015, 7063784, 10855425, 14743445, 17678835, 18796230

Offset: 0

Vladeta Jovovic, Apr 20 2000

			Triangle begins:
  k    0  1  2  3   4   5   6   7   8   9  10  11  12 13 14 15 16      sums
n
0      1  1                                                              2
1      1  1  1                                                           3
2      1  1  3  1   1                                                    7
3      1  1  7  7  14   7   7   1   1                                   46
4      1  1 15 35 140 273 553 715 870 715 553 273 140 35 15  1  1     4336
...

M. A. Harrison, Introduction to Switching and Automata Theory. McGraw Hill, NY, 1965, p. 143.

G. C. Greubel, Rows n = 0..10, flattened
Index entries for sequences related to Boolean functions

Row sums give A000231. Cf. A052265.

T:= (n, k)-> (binomial(2^n, k)+`if`(k::odd, 0,
             (2^n-1)*binomial(2^(n-1), k/2)))/2^n:
seq(seq(T(n, k), k=0..2^n), n=0..5);  # Alois P. Heinz, Jan 27 2023

rows = 5; t[n_, k_?OddQ] := 2^-n*Binomial[2^n, k]; t[n_, k_?EvenQ] := 2^-n*(Binomial[2^n, k] + (2^n-1)*Binomial[2^(n-1), k/2]); Flatten[ Table[ t[n, k], {n, 1, rows}, {k, 0, 2^n}]] (* Jean-François Alcover, Nov 21 2011, after Vladeta Jovovic *)
T[n_, k_]:= If[OddQ[k], Binomial[2^n, k]/2^n, 2^(-n)*(Binomial[2^n, k] + (2^n - 1)*Binomial[2^(n - 1), k/2])]; Table[T[n,k], {n,1,5}, {k,0,2^n}] //Flatten  (* G. C. Greubel, Feb 15 2018 *)

T(n,k) = 2^(-n)*C(2^n, k) if k is odd and 2^(-n)*(C(2^n, k) + (2^n-1)*C(2^(n-1), k/2)) if k is even.

Two terms for row n=0 prepended by Alois P. Heinz, Jan 27 2023

A055130 Triangle T(n,k) of numbers of k-covers of an unlabeled n-set, k=1..2^n-1.

Original entry on oeis.org

1, 1, 2, 1, 1, 4, 9, 10, 6, 3, 1, 1, 7, 29, 87, 181, 287, 364, 365, 290, 187, 97, 39, 13, 4, 1, 1, 10, 72, 417, 1973, 7745, 25830, 74017, 183420, 395311, 744495, 1229807, 1787135, 2289925, 2591162, 2591163, 2289929, 1787148, 1229846, 744592, 395498

Offset: 1

Vladeta Jovovic, Jun 14 2000

			Triangle begins:
[1] 1;
[2] 1, 2,  1;
[3] 1, 4,  9, 10,   6,   3,   1;
[4] 1, 7, 29, 87, 181, 287, 364, 365, 290, 187, 97, 39, 13, 4, 1;
  ...
There are 9 3-covers of an unlabeled 3-set: {{1,2},{2,3},{1,2,3}}, {{1,2},{2,3},{1,3}}, {{1,2},{3},{1,2,3}}, {{1},{1,2},{1,2,3}}, {{1,2},{2,3},{3}}, {{1,2},{2},{2,3}}, {{1},{2},{1,2,3}}, {{1},{2},{1,3}} and {{1},{2},{3}}.

Andrew Howroyd, Table of n, a(n) for n = 1..2036 (rows 1..10)

Row sums give A055621.
Columns k=1..3 are A000012, A014616(n-1), A055195.
Cf. A052265, A368186.

\\ G(n,m) defined in A368186.
row(n)={my(m=2^n-1); Vec(G(n,m) - G(n-1,m))} \\ Andrew Howroyd, Jan 03 2024

T(n,n) = A368186(n). - Andrew Howroyd, Jan 03 2024

A371830 Irregular triangle read by rows: T(n,k) is the number of unlabeled n-vertex hypergraphs (or set systems) with k hyperedges (none of which is empty), 0 <= k <= 2^n-1.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 1, 1, 3, 6, 10, 10, 6, 3, 1, 1, 4, 13, 39, 97, 187, 290, 365, 365, 290, 187, 97, 39, 13, 4, 1, 1, 5, 23, 111, 514, 2160, 8035, 26195, 74382, 183710, 395498, 744592, 1229846, 1787148, 2289929, 2591163, 2591163, 2289929, 1787148, 1229846, 744592, 395498, 183710, 74382, 26195, 8035, 2160, 514, 111, 23, 5, 1

Offset: 0

Pontus von Brömssen, Apr 07 2024

			Triangle begins:
  n\k| 0  1  2  3  4   5   6   7   8   9  10 11 12 13 14 15
  ---+-----------------------------------------------------
  0  | 1
  1  | 1  1
  2  | 1  2  2  1
  3  | 1  3  6 10 10   6   3   1
  4  | 1  4 13 39 97 187 290 365 365 290 187 97 39 13  4  1

Pontus von Brömssen, Table of n, a(n) for n = 0..2046
Peter H. van der Kamp, Hypergraphs and homogeneous Lotka-Volterra systems with linear Darboux polynomials, arXiv:2411.18264 [nlin.SI], 2024. See p. 4.

Cf. A000612 (row sums), A008406, A052265 (empty hyperedge allowed).

def A371830(n,k):
    return sum(1 for G in hypergraphs.nauty(k,n,set_min_size=1))

T(n,k) = Sum_{j=0..k} (-1)^(k-j)*A052265(n,j).

A380518 Irregular triangle read by rows: T(n,k) is the number of non-isomorphic formulas in conjunctive normal form (CNF) with n variables and k distinct clauses up to permutations of the variables and clauses, 0 <= k <= 3^n.

Original entry on oeis.org

1, 1, 1, 3, 3, 1, 1, 6, 21, 47, 69, 69, 47, 21, 6, 1, 1, 10, 82, 573, 3176, 14066, 50646, 150508, 374266, 787691, 1415279, 2184842, 2911290, 3358258, 3358258, 2911290, 2184842, 1415279, 787691, 374266, 150508, 50646, 14066, 3176, 573, 82, 10, 1

Offset: 0

Frank Schwidom, Jan 26 2025

Each clause is a disjunction of zero or more literals where each literal is a variable or its negation. A variable and its negation cannot appear in the same clause.
In total there are 3^n distinct clauses. This sequence counts sets of clauses up to permutation of the variables.
Equivalently, T(n,k) is the number of k X n matrices with distinct rows and entries in 0..2 up to permutations of rows and columns. Each row of the matrix corresponds with a clause and columns correspond with variables.

			Triangle begins:
 0 | 1,  1;
 1 | 1,  3,  3,   1;
 2 | 1,  6, 21,  47,   69,    69,    47,     21,      6,      1;
 3 | 1, 10, 82, 573, 3176, 14066, 50646, 150508, 374266, 787691, 1415279, 2184842,  2911290, 3358258, 3358258, 2911290, 2184842, 1415279, 787691, 374266, 150508, 50646, 14066, 3176, 573, 82, 10, 1;
     ...
The enumeration scheme:
The positions of the numbers 0, 1, 2 represent the literals.
The numbers represent: 0 for an inverted literal, 1 for a set literal and 2 for a not used literal.
A list of lists written in brackets ([]) represents a conjunction of disjunctions.
Let's treat the first and second position as literal a and b.
The empty clause is denoted false, prefix operator ~ is not, infix operator \/ is or , infix operator /\ is and.
The T(2,1) = 6 representative formulas with 2 variables and 1 clause are:
[[2,2]] => false
[[1,2]] => (a)
[[1,1]] => (a \/ b)
[[0,2]] => (~a)
[[0,1]] => (~a \/ b)
[[0,0]] => (~a \/ ~b)
In the above, (b), (~b) and (a \/ ~b) do not appear because they are essentially the same as another after swapping the a and b variables.
The T(2,2) = 21 representative formulas with 2 variables and 2 clauses are:
[[1,2],[2,2]] => (a) /\ false
[[1,2],[2,1]] => (a) /\ (b)
[[1,1],[2,2]] => (a \/ b) /\ false
[[1,1],[1,2]] => (a \/ b) /\ (a)
[[0,2],[2,2]] => (~a) /\ false
[[0,2],[2,1]] => (~a) /\ (b)
[[0,2],[2,0]] => (~a) /\ (~b)
[[0,2],[1,2]] => (~a) /\ (a)
[[0,2],[1,1]] => (~a) /\ (a \/ b)
[[0,1],[2,2]] => (~a \/ b) /\ false
[[0,1],[2,1]] => (~a \/ b) /\ (b)
[[0,1],[2,0]] => (~a \/ b) /\ (~b)
[[0,1],[1,2]] => (~a \/ b) /\ (a)
[[0,1],[1,1]] => (~a \/ b) /\ (a \/ b)
[[0,1],[1,0]] => (~a \/ b) /\ (a \/ ~b)
[[0,1],[0,2]] => (~a \/ b) /\ (~a)
[[0,0],[2,2]] => (~a \/ ~b) /\ false
[[0,0],[1,2]] => (~a \/ ~b) /\ (a)
[[0,0],[1,1]] => (~a \/ ~b) /\ (a \/ b)
[[0,0],[0,2]] => (~a \/ ~b) /\ (~a)
[[0,0],[0,1]] => (~a \/ ~b) /\ (~a \/ b)

Andrew Howroyd, Table of n, a(n) for n = 0..1099 (rows 0..6)
Frank Schwidom, Prolog code to prove the sequence.
Wikipedia, Conjunctive normal form.

Row sums are 2*A380630.
Row lengths give A034472.
Column k=1 gives the nonzero terms of A000217.
Cf. A052265, A380610.

\\ compare A052265.
permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
Fix(q, x)={my(v=divisors(lcm(Vec(q))), u=apply(t->3^sum(j=1, #q, gcd(t, q[j])), v)); prod(i=1, #v, my(t=v[i]); (1+x^t)^(sum(j=1, i, my(d=t/v[j]); if(!frac(d), moebius(d)*u[j]))/t))}
Row(n)={my(s=0); forpart(q=n, s+=permcount(q)*Fix(q, x)); Vecrev(s/n!)}
{ for(n=0, 4, print(Row(n))) } \\ Andrew Howroyd, Jan 26 2025

T(n,0) = T(n,3^n) = 1.
T(n,k) = T(n,3^n-k).
T(n,k) = A380610(n,k-1) + A380610(n,k) for 0 < k < 3^n.

cp's OEIS Frontend

A028657 Triangle read by rows: T(n,k) = number of n-node graphs with k nodes in distinguished bipartite block, k = 0..n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

Formula

A003180 Number of equivalence classes of Boolean functions of n variables under action of symmetric group.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A005744 Expansion of x*(1+x-x^2)/((1-x)^4*(1+x)).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A054724 Triangle of numbers of inequivalent Boolean functions of n variables with exactly k nonzero values (atoms) under action of complementing group.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A055130 Triangle T(n,k) of numbers of k-covers of an unlabeled n-set, k=1..2^n-1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A371830 Irregular triangle read by rows: T(n,k) is the number of unlabeled n-vertex hypergraphs (or set systems) with k hyperedges (none of which is empty), 0 <= k <= 2^n-1.

A005744 Expansion of x(1+x-x^2)/((1-x)^4(1+x)).