login
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.
2
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,3
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).
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.
EXAMPLE
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
...
PROG
(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] }
CROSSREFS
Cf. A036740 (A(n,0)), A261603 (A(n,[n^2/2])).
Sequence in context: A076703 A360900 A305372 * A377034 A265733 A266146
KEYWORD
nonn,tabf,changed
AUTHOR
Max Alekseyev, Aug 25 2015
STATUS
approved