|
%I #11 Jul 06 2019 16:53:05
%S 1,24,736,486200,15717093608,41301356272912040,
%T 12775545227876350768099688,645382645785863222088428068265093848,
%U 6899505383250315051751361998008633233501722290328
%N 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 From _Jon E. Schoenfield_, Aug 16 2009: (Start)
%C 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 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 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 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 a(2) = 4! = 24 because every arrangement of the four elements of a 2 X 2 matrix satisfies the conditions.
%Y Cf. A039622.
%K nonn,nice
%O 1,2
%A _Floor van Lamoen_, Jul 10 2001
%E a(3) changed from 5320 to 736 by _R. H. Hardin_, Feb 17 2002
%E More terms from _Jon E. Schoenfield_, Aug 15 2009
|
