|
%I #18 Apr 13 2024 09:08:33
%S 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,
%T 730,655,477,284,136,52,17,5,1,1,6,28,134,625,2674,10195,34230,100577,
%U 258092,579208,1140090,1974438,3016994,4077077,4881092,5182326,4881092
%N 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.
%C 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
%D M. A. Harrison, Introduction to Switching and Automata Theory. McGraw Hill, NY, 1965, p. 147.
%H Andrew Howroyd, <a href="/A052265/b052265.txt">Table of n, a(n) for n = 0..2057</a>
%H <a href="/index/Bo#Boolean">Index entries for sequences related to Boolean functions</a>
%F 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
%e Triangle begins:
%e 1, 1;
%e 1, 2, 1;
%e 1, 3, 4, 3, 1;
%e 1, 4, 9, 16, 20, 16, 9, 4, 1;
%e 1, 5, 17, 52, 136, 284, 477, 655, 730, 655, 477, 284, 136, 52, 17, 5, 1;
%e ...
%t Table[rl = Table[Tuples[{0, 1}, nn][[i]] -> i, {i, 1, 2^nn}];
%t 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! /.
%t Table[Subscript[x, i] -> 1 + x^i, {i, 1, nn!}], x], {nn, 0, 8}] (* _Geoffrey Critzer_, Jun 22 2021 *)
%o (PARI)
%o 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}
%o 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))}
%o Row(n)={my(s=0); forpart(q=n, s+=permcount(q)*Fix(q,x)); Vecrev(s/n!)}
%o { for(n=0, 4, print(Row(n))) } \\ _Andrew Howroyd_, Mar 26 2020
%Y Row sums give A003180.
%Y Cf. A028657, A371830 (empty hyperedge not permitted).
%K nonn,tabf,nice,changed
%O 0,4
%A _Vladeta Jovovic_, Feb 04 2000
|
