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,4

Comments

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

References

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

Links

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

Index entries for sequences related to Boolean functions

Formula

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

Example

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

Mathematica

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

Prog

(PARI)
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

Crossrefs

Row sums give A003180.

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

Sequence in context: A305431 A128314 A025564 * A306565 A055068 A237498

Adjacent sequences: A052262 A052263 A052264 * A052266 A052267 A052268

Keyword

nonn,tabf,nice

Author

Vladeta Jovovic, Feb 04 2000

Status

approved