login
Number of polynomial symmetric functions of matrix of order n under separate row and column permutations.
455

%I #55 Mar 29 2020 19:35:31

%S 1,1,4,10,33,91,298,910,3017,9945,34207,119369,429250,1574224,5916148,

%T 22699830,89003059,356058540,1453080087,6044132794,25612598436,

%U 110503627621,485161348047,2166488899642,9835209912767,45370059225318,212582817739535,1011306624512711

%N Number of polynomial symmetric functions of matrix of order n under separate row and column permutations.

%C Also, the number of nonnegative integer n X n matrices with sum of elements equal to n, under row and column permutations (cf. A120733).

%C This is a two-dimensional generalization of the partition function (A000041), which equals the number of length n vectors of nonnegative integers with sum n, equivalent under permutations. - _Franklin T. Adams-Watters_, Sep 19 2011

%C Also number of non-isomorphic multiset partitions of weight n. - _Gus Wiseman_, Sep 19 2011

%H Andrew Howroyd, <a href="/A007716/b007716.txt">Table of n, a(n) for n = 0..50</a> (terms 0..30 from Seiichi Manyama)

%F a(n) is the coefficient of x^n in the cycle index Z(S_n X S_n; x_1, x_2, ...) if we replace x_i with 1+x^i+x^(2*i)+x^(3*i)+x^(4*i)+..., where S_n X S_n is the Cartesian product of symmetric groups S_n of degree n. - _Vladeta Jovovic_, Mar 09 2000

%e The 10 non-isomorphic multiset partitions of weight 3 are {{1, 1, 1}}, {{1, 1, 2}}, {{1, 2, 3}}, {{1}, {1, 1}}, {{1}, {1, 2}}, {{1}, {2, 2}}, {{1}, {2, 3}}, {{1}, {1}, {1}}, {{1}, {1}, {2}}, {{1}, {2}, {3}}.

%t permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i>1 && t == v[[i-1]], k+1, 1]; m *= t*k; s += t]; s!/m];

%t c[p_, q_, k_] := SeriesCoefficient[1/Product[(1-x^LCM[p[[i]], q[[j]]])^GCD[ p[[i]], q[[j]]], {j, 1, Length[q]}, {i, 1, Length[p]}], {x, 0, k}];

%t M[m_, n_, k_] := Module[{s=0}, Do[Do[s += permcount[p]*permcount[q]*c[p, q, k], {q, IntegerPartitions[n]}], {p, IntegerPartitions[m]}]; s/(m!*n!)];

%t a[n_] := a[n] = M[n, n, n];

%t Table[Print[n, " ", a[n]]; a[n], {n, 0, 18}] (* _Jean-François Alcover_, May 03 2019, after _Andrew Howroyd_ *)

%o (PARI) \\ See A318795

%o a(n) = M(n,n,n); \\ _Andrew Howroyd_, Sep 03 2018

%o (PARI)

%o EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,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)={EulerT(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_, Mar 29 2020

%Y Main diagonal of A318795.

%Y Cf. A053307, A052365, A052366, A052367, A052372, A052373, A049311, A054688, A000041.

%K nice,nonn

%O 0,3

%A _Colin Mallows_

%E More terms from _Vladeta Jovovic_, Jun 28 2000

%E a(19)-a(25) from _Max Alekseyev_, Jan 22 2010

%E a(0)=1 prepended by _Alois P. Heinz_, Feb 03 2019

%E a(26)-a(27) from _Seiichi Manyama_, Nov 23 2019