|
%I #59 Jan 26 2024 00:57:54
%S 1,3,6,16,34,90,211,558,1430,3908,10725,30825,90156,273234,848355,
%T 2714399,8909057,30042866,103859678,368075596,1335537312,4958599228,
%U 18820993913,72980867400,288885080660,1166541823566,4802259167367,20141650236664
%N Number of (0,1) matrices with n ones and no zero rows or columns, up to row and column permutations.
%C Also the number of bipartite graphs with n edges, no isolated vertices and a distinguished bipartite block, up to isomorphism.
%C The EULERi transform (A056156) is also interesting.
%C a(n) is also the number of non-isomorphic set multipartitions (multisets of sets) of weight n. - _Gus Wiseman_, Mar 17 2017
%H Aliaksandr Siarhei, <a href="/A049311/b049311.txt">Table of n, a(n) for n = 1..102</a>
%H Peter J. Cameron, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
%H Peter J. Cameron, D. A. Gewurz and F. Merola, <a href="http://www.maths.qmw.ac.uk/~pjc/preprints/product.pdf">Product action</a>, Discrete Math., 308 (2008), 386-394.
%H Peter J. Cameron, <a href="http://www.maths.qmw.ac.uk/~pjc/pgprob.html">Problems on Permutation Groups</a>, see Problem 3
%H <a href="/index/Mat#binmat">Index entries for sequences related to binary matrices</a>.
%F Calculate number of connected bipartite graphs + number of connected bipartite graphs with no duality automorphism, then apply EULER transform.
%F a(n) is the coefficient of x^n in the cycle index Z(S_n X S_n; 1+x, 1+x^2, ...), where S_n X S_n is Cartesian product of symmetric groups S_n of degree n.
%e E.g. a(2) = 3: two ones in same row, two ones in same column, or neither.
%e a(3) = 6 is coefficient of x^3 in (1/36)*((1 + x)^9 + 6*(1 + x)^3*(1 + x^2)^3 + 8*(1 + x^3)^3 + 9*(1 + x)*(1 + x^2)^4 + 12*(1 + x^3)*(1 + x^6))=1 + x + 3*x^2 + 6*x^3 + 7*x^4 + 7*x^5 + 6*x^6 + 3*x^7 + x^8 + x^9.
%e There are a(3) = 6 binary matrices with 3 ones, with no zero rows or columns, up to row and column permutation:
%e [1 0 0] [1 1 0] [1 0] [1 1] [1 1 1] [1]
%e [0 1 0] [0 0 1] [1 0] [1 0] ....... [1].
%e [0 0 1] ....... [0 1] ............. [1]
%e Non-isomorphic representatives of the a(3)=6 set multipartitions are: ((123)), ((1)(23)), ((2)(12)), ((1)(1)(1)), ((1)(2)(2)), ((1)(2)(3)). - _Gus Wiseman_, Mar 17 2017
%o (PARI)
%o WeighT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v,n,(-1)^(n-1)/n))))-1,-#v)}
%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 K(q, t, k)={WeighT(Vec(sum(j=1, #q, gcd(t, q[j])*x^lcm(t, q[j])) + O(x*x^k), -k))}
%o a(n)={my(s=0); forpart(q=n, s+=permcount(q)*polcoef(exp(x*Ser(sum(t=1, n, K(q, t, n)/t))), n)); s/n!} \\ _Andrew Howroyd_, Jan 16 2023
%Y Main diagonal of A321609.
%Y Cf. A049312, A048194, A028657, A055192, A055599, A052371, A052370, A053304, A053305, A007716, A002724.
%Y Cf. A057149, A057150, A057151, A057152.
%Y Cf. A034691, A056156, A089259, A116540, A283877.
%K nonn,nice
%O 1,2
%A _Peter J. Cameron_
%E More terms and formula from _Vladeta Jovovic_, Jul 29 2000
%E a(19)-a(28) from _Max Alekseyev_, Jul 22 2009
%E a(29)-a(102) from _Aliaksandr Siarhei_, Dec 13 2013
%E Name edited by _Gus Wiseman_, Dec 18 2018
|
