|
|
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.
|
|
9
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
FORMULA
|
|
|
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!)}
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,tabf,nice
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|