login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

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

%I #16 Nov 16 2024 02:02:24

%S 1,1,4,8,10,8,4,216,648,1188,1668,1944,1944,1668,1188,648,216,331776,

%T 1327104,3151872,5695488,8608896,11446272,13791744,15326208,15858432,

%U 15326208,13791744,11446272,8608896,5695488,3151872,1327104,331776,24883200000,124416000000,360806400000,787138560000,1426595328000,2262299258880,3240594432000,4283587584000,5304730521600,6222411878400,6968709089280,7493189990400,7763310604800

%N 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.

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

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

%H Max Alekseyev, <a href="/A261602/b261602.txt">Table of n, a(n) for n = 1..395</a>

%H Mathoverflow, <a href="https://mathoverflow.net/q/214941">A question about certain sets of permutations of the ordered pairs (1,1), (1,2), ..., (n,n)</a>

%F 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.

%e The array starts with

%e n=1: 1, 1

%e n=2: 4, 8, 10, 8, 4

%e n=3: 216, 648, 1188, 1668, 1944, 1944, 1668, 1188, 648, 216

%e ...

%o (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] }

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

%K nonn,tabf

%O 1,3

%A _Max Alekseyev_, Aug 25 2015