A371830 -id:A371830 - cp's OEIS frontend

A052265 Triangle giving T(n,r) = number of equivalence classes of Boolean functions of n variables and range r=0..2^n under action of symmetric group.

1, 1, 1, 2, 1, 1, 3, 4, 3, 1, 1, 4, 9, 16, 20, 16, 9, 4, 1, 1, 5, 17, 52, 136, 284, 477, 655, 730, 655, 477, 284, 136, 52, 17, 5, 1, 1, 6, 28, 134, 625, 2674, 10195, 34230, 100577, 258092, 579208, 1140090, 1974438, 3016994, 4077077, 4881092, 5182326, 4881092

Offset: 0

Vladeta Jovovic, Feb 04 2000

Also, T(n,k) is the number of unlabeled n-vertex hypergraphs (or set systems) with k hyperedges. - Pontus von Brömssen, Apr 10 2024

			Triangle begins:
   1, 1;
   1, 2, 1;
   1, 3, 4, 3, 1;
   1, 4, 9, 16, 20, 16, 9, 4, 1;
   1, 5, 17, 52, 136, 284, 477, 655, 730, 655, 477, 284, 136, 52, 17, 5, 1;
   ...

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

Andrew Howroyd, Table of n, a(n) for n = 0..2057
Index entries for sequences related to Boolean functions

Row sums give A003180.

Cf. A028657, A371830 (empty hyperedge not permitted).

Table[rl = Table[Tuples[{0, 1}, nn][[i]] -> i, {i, 1, 2^nn}];
 f[permutation_] := PermutationCycles[Map[Permute[#, permutation] &, Tuples[{0, 1}, nn]] /. rl];CoefficientList[(Map[CycleIndexPolynomial[#, Array[Subscript[x, ##] &, 2^nn],2^nn] &, Map[f, Permutations[Range[nn]]]] // Total)/nn! /.
Table[Subscript[x, i] -> 1 + x^i, {i, 1, nn!}], x], {nn, 0, 8}] (* Geoffrey Critzer, Jun 22 2021 *)

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)); 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, Mar 26 2020

T(n,k) = A371830(n,k-1) + A371830(n,k) (with A371830(n,k) = 0 if k < 0 or k >= 2^n). - Pontus von Brömssen, Apr 10 2024

A380610 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 nonempty clauses up to permutations of the variables and clauses, 0 <= k < 3^n.

Original entry on oeis.org

1, 1, 2, 1, 1, 5, 16, 31, 38, 31, 16, 5, 1, 1, 9, 73, 500, 2676, 11390, 39256, 111252, 263014, 524677, 890602, 1294240, 1617050, 1741208, 1617050, 1294240, 890602, 524677, 263014, 111252, 39256, 11390, 2676, 500, 73, 9, 1, 1, 14, 238, 4320, 72225, 1039086, 12712546, 133231940, 1211353657

Offset: 0

Frank Schwidom, Jan 28 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-1 distinct nonempty clauses. This sequence counts sets of clauses up to permutations of the variables.
Equivalently, T(n,k) is the number of k X n matrices with distinct rows, entries in 0..2 and no all zero row 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, 2,  1;
  2 | 1, 5, 16,  31,   38,    31,    16,  5,  1;
  3 | 1, 9, 73, 500, 2676, 11390, 39256, 111252, 263014, 524677, 890602, 1294240, 1617050, 1741208, 1617050, 1294240, 890602, 524677, 263014, 111252, 39256, 11390, 2676, 500, 73, 9, 1;
  ...
The T(2,1) = 5 representative formulas with 2 variables and 1 clause are:
  [[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) = 16 representative formulas with 2 variables and 2 clauses are:
  [[1,2],[2,1]] => (a) /\ (b)
  [[1,1],[1,2]] => (a \/ b) /\ (a)
  [[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,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],[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..1092 (rows 0..6)
Frank Schwidom, Prolog code to prove the sequence.

Cf. A000244 (row lengths), A371830, A380518, A380630 (row sums).

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!/(1 + x))}
{ for(n=0, 4, print(Row(n))) } \\ Andrew Howroyd, Jan 30 2025

More terms from Andrew Howroyd, Jan 30 2025

cp's OEIS Frontend

A052265 Triangle giving T(n,r) = number of equivalence classes of Boolean functions of n variables and range r=0..2^n under action of symmetric group.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula