cp's OEIS Frontend

A062528 Number of ways to fill an n X n matrix with numbers 1, 2, ..., n*n such that each row and each column is decreasing or increasing.

%I A062528 #11 Jul 06 2019 16:53:05
%S A062528 1,24,736,486200,15717093608,41301356272912040,
%T A062528 12775545227876350768099688,645382645785863222088428068265093848,
%U A062528 6899505383250315051751361998008633233501722290328
%N A062528 Number of ways to fill an n X n matrix with numbers 1, 2, ..., n*n such that each row and each column is decreasing or increasing.
%C A062528 From _Jon E. Schoenfield_, Aug 16 2009: (Start)
%C A062528 Number the rows of the matrix as 1..n from bottom to top, and the columns as 1..n from left to right. For i=1..n, let r(i)=1 if the i-th row increases toward the right, -1 if it decreases; let R be the number of runs of consecutive rows having the same r value, and let LR(k) be the length of the k-th run, for k=1..R. Similarly, for i=1..n, let c(i)=1 if the i-th column increases toward the top, -1 if it decreases; let C be the number of runs of consecutive columns having the same c value, and let LC(k) be the length of the k-th run, for k=1..C.
%C A062528 For each of the 4 possible combinations of the vectors r and c in which R=C=1, the number of solutions is A039622(n). In any combination where R=1 and C > 1, the matrix can be partitioned into C rectangular sections (the k-th one being LC(k) columns wide and n rows high); the numbers 1 through LC(1)*n must be placed in the first section, the next LC(2)*n numbers in the second section, etc., so the total number of solutions is Product_{k=1..C} T(LC(k),n), where T(m,n) is as defined at A060854; similarly, if C=1 and R > 1, the number of solutions is Product_{k=1..R} T(LR(k),n).
%C A062528 In any combination where R=2, C=2, and r(1)=c(1), the matrix can be partitioned into 4 rectangular sections, with the lower left and lower right sections covering rows 1..LR(1), the upper left and upper right covering the remaining rows, the lower and upper left covering columns 1..LC(1), and the lower and upper right covering the remaining columns. Then, if r(1)=c(1)=1, the numbers 1 through LR(1)*LC(1) + LR(2)*LC(2) must be apportioned between the lower left and upper right sections; if r(1)=c(1)=-1, they must be apportioned between the other two sections. Either way, the number of solutions for such a combination of the vectors r and c is binomial(LR(1)*LC(1) + LR(2)*LC(2), LR(1)*LC(1)) * binomial(LR(1)*LC(2) + LR(2)*LC(1), LR(1)*LC(2)) * T(LR(1), LC(1)) * T(LR(1), LC(2)) * T(LR(2), LC(1)) * T(LR(2), LC(2)).
%C A062528 No solutions exist where R=C=2 and r(1) != c(1), nor are there any solutions where R=2 and C > 2, R > 2 and C=2, or R > 2 and C > 2. (End)
%e A062528 a(2) = 4! = 24 because every arrangement of the four elements of a 2 X 2 matrix satisfies the conditions.
%Y A062528 Cf. A039622.
%K A062528 nonn,nice
%O A062528 1,2
%A A062528 _Floor van Lamoen_, Jul 10 2001
%E A062528 a(3) changed from 5320 to 736 by _R. H. Hardin_, Feb 17 2002
%E A062528 More terms from _Jon E. Schoenfield_, Aug 15 2009