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

Author

Vladeta Jovovic, Feb 04 2000

Keywords

• nonn
• tabf
• nice

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

Examples

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

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

Crossrefs

Row sums give A003180.

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

Programs

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

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

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