A261602 Triangular array of A(n,k) for n>=1 and 0<=k<=n^2 equal the number of permutations of the set {1,2,...,n}^2 such that first coordinates of first k elements are nondecreasing and second coordinates of the remaining n^2-k elements are nondecreasing.

1, 1, 4, 8, 10, 8, 4, 216, 648, 1188, 1668, 1944, 1944, 1668, 1188, 648, 216, 331776, 1327104, 3151872, 5695488, 8608896, 11446272, 13791744, 15326208, 15858432, 15326208, 13791744, 11446272, 8608896, 5695488, 3151872, 1327104, 331776, 24883200000, 124416000000, 360806400000, 787138560000, 1426595328000, 2262299258880, 3240594432000, 4283587584000, 5304730521600, 6222411878400, 6968709089280, 7493189990400, 7763310604800

Offset: 1

Author

Max Alekseyev, Aug 25 2015

Keywords

• nonn
• tabf

Comments

A(n,k) = A(n,n^2-k)

It is conjectured that A(n,k)>A(n,k-1) for k<=floor(n^2/2) (see Mathoverflow link).

Examples

			The array starts with
n=1: 1, 1
n=2: 4, 8, 10, 8, 4
n=3: 216, 648, 1188, 1668, 1944, 1944, 1668, 1188, 648, 216
...
		

Links

• Max Alekseyev, Table of n, a(n) for n = 1..395
• Mathoverflow, A question about certain sets of permutations of the ordered pairs (1,1), (1,2), ..., (n,n)

Crossrefs

Cf. A036740 (A(n,0)), A261603 (A(n,[n^2/2])).

Programs

PARI

{ A(n,k) = my(r,rw,rs,s,t,p); r=vector(n^2+1); rw=[]; forvec(v=vector(n,i,[0,1]),rw=concat(rw,[v])); rs=vector(#rw,i,sum(j=1,n,rw[i][j])); forvec(v=vector(n,i,[1,#rw]), s=sum(j=1,#v,rs[v[j]]); t=n!; p=1; for(i=2,#v,if(v[i]==v[i-1],p++,t/=p!;p=1)); t/=p!; r[s+1]+=t*prod(i=1,n,rs[v[i]]!)*prod(j=1,n,(n-sum(i=1,n,rw[v[i]][j]))!); ,1); r[k] }

Formula

A(n,k) = SUM rs(M,1)!*...*rs(M,n)*(n-cs(M,1))!*...*(n-cs(M,n))!, where the sum is taken over n X n (0,1)-matrices with exactly k ones, rs(M,i) and cs(M,j) are the i-th row sum and the j-th column sum of M, respectively.