login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
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).

LINKS

Max Alekseyev, Table of n, a(n) for n = 1..97

Mathoverflow, A question about certain sets of permutations of the ordered pairs (1,1), (1,2), ..., (n,n)

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: A072037 A076703 A305372 * A265733 A266146 A329503

Adjacent sequences:  A261599 A261600 A261601 * A261603 A261604 A261605

KEYWORD

nonn,tabf

AUTHOR

Max Alekseyev, Aug 25 2015

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 24 00:08 EDT 2021. Contains 345403 sequences. (Running on oeis4.)