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

1, 1, 4, 10, 33, 91, 298, 910, 3017, 9945, 34207, 119369, 429250, 1574224, 5916148, 22699830, 89003059, 356058540, 1453080087, 6044132794, 25612598436, 110503627621, 485161348047, 2166488899642, 9835209912767, 45370059225318, 212582817739535, 1011306624512711

Offset: 0

Author

Colin Mallows

Keywords

• nice
• nonn

Comments

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

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

Also number of non-isomorphic multiset partitions of weight n. - Gus Wiseman, Sep 19 2011

Examples

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

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..50 (terms 0..30 from Seiichi Manyama)

Crossrefs

Main diagonal of A318795.

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

Programs

Mathematica

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];
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}];
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!)];
a[n_] := a[n] = M[n, n, n];
Table[Print[n, " ", a[n]]; a[n], {n, 0, 18}] (* Jean-François Alcover, May 03 2019, after Andrew Howroyd *)

PARI

\\ See A318795
a(n) = M(n,n,n); \\ Andrew Howroyd, Sep 03 2018

PARI

EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
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}
K(q, t, k)={EulerT(Vec(sum(j=1, #q, gcd(t, q[j])*x^lcm(t,q[j])) + O(x*x^k), -k))}
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

Formula

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

Extensions

More terms from Vladeta Jovovic, Jun 28 2000

a(19)-a(25) from Max Alekseyev, Jan 22 2010

a(0)=1 prepended by Alois P. Heinz, Feb 03 2019

a(26)-a(27) from Seiichi Manyama, Nov 23 2019